脚本宝典收集整理的这篇文章主要介绍了javascript代码实例教程-Javascript-BinarySearchTree,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。小宝典致力于为广大程序猿(媛)提供高品质的代码服务,请大家多多光顾小站,小宝典在此谢过。
二叉搜索树融合了二分查找的高效简洁以及链式数据结构删除元素的优雅。这样一个优秀的数据结构,使用的频率很高。如常见的
LRU
缓存淘汰算法等, 几乎任何可以想到的查找算法都可以用它来替换。日常工程代码中一般对效率不高,一些常用的查找算法已经可以胜任了。这里把之前写的c语言版的实现转换过来,并扩充一些接口,实现一个完整版本的BST。
function BSTree(compare) { this.root = null; this.COMpare = compare; } function BSTreeNode(k, v, n) { this.N = n; this.key = k; this.value = v; }
BSTree.PRototyPE.get = function(k) { function travel(node) { if(!node) return null; VAR ret = self.compare(k, node.key); if(ret == 0) return node; if(ret < 0) { return travel(node.right); } else { return travel(node.left); } } var self = this; return travel(this.root); }
get
操作算是BST
最基本的操作之一,基于BST左子树小于当前节点、右子树大于当前节点的原则,可以轻易的写出相应的实现。
BSTree.prototype.size = function() { return this._size(this.root); } BSTree.prototype._size = function(root) { return root ? root.N : 0; }
计算节点直接返回根节点上
N
即可。
BSTree.prototype.put = function(k, v) { function travel(node) { if(!node) return new BSTreeNode(k, v, 1); var ret = self.compare(k, node.key); if(ret == 0) { node.value = v; return node; } else if(ret < 0) { node.left = travel(node.left); } else { node.right = travel(node.right); } node.N = self._size(node.left) + self._size(node.right) + 1; return node; } var self = this; travel(this.root); }
put实现的也比较简单,对于这类第归类型的算法考虑几个特殊用例即可。譬如说root不存在即:
node==null
,此时需要新建一个节点并返回。新节点的键值大于当前节点,所以更新当前节点的右边只树,新节点的键值小于当前节点,更新当前节点的左子树。
BSTree.prototype.min = function(root) { if(!root) root = this.root; function travel(root) { if(!root) return null; if(root.left) { return travel(root.left); } return travel(root); } return travel(root); } BSTree.prototype.max = function(root) { if(!root) root = this.root; function travel(root) { if(!root) return null; if(root.right) { return travel(root.right); } return travel(root); } return travel(root); }
n
的节点 BSTree.prototype.select = function(n) { function travel(node, n) { if(!node) return null; var size = self._size(node.left); if(size == n) return node; if(size > n) return travel(node.left, n); else { return travale(node.right, n - size - 1); } } var self = this; return travel(this.root, n); }
k
的节点排名 BSTree.prototyoe.rank = function(k) { function travel(node) { if(!node) return 0; var ret = self.compare(k, node.key); if(ret == 0) return self._size(node.left) + 1; if(ret < 0) { return travel(node.left);} else { return self._size(node.left) + 1 + travel(node.right); } } var self = this; return travel(this.root); }
BSTree.prototype.floor = function(k) { function travel(node) { if(!node) return null; var ret = self.compare(k, node.key); if(ret == 0) { return node; } if(ret < 0) { var tmp = travel(node.left); return tmp ? tmp : node; } else { return travel(node.right); } } var self = this; return travel(this.root); } BSTree.prototype.ceiling = function(k) { function travel(node) { if(!node) return null; var ret = self.compare(k, node.key); if(ret == 0) { return node; } if(ret > 0) { var tmp = travel(node.right); return tmp ? tmp : node; } else { return travel(node.left); } } var self = this; return travel(this.root); }
floor和ceiling的基本含义与js的Math对象对应的接口基本类似。floor取大于等于指定键值的最小节点。ceiling取小于等于指定节点的最大节点。
BSTree.prototype.keys = function(lo, hi) { function travel(node) { if(!node) return; var ret1 = self.compare(lo, node.key); var ret2 = self.compare(hi, node.key); if(ret1 > 0) { return travel(node.right); } else if(ret2 < 0) { return travel(node.left); } else { arr.push(node.key); } } var arr = []; var self = this; travel(this.root); return arr; }
BSTree.prototype.deleteMin = function() { this.root = this._deleteMin(this.root); } BSTree.prototype._deleteMin = function(root) { if(!root) return null; function travel(node) { if(node.left) node.left = travel(node.left); else { return node.right; } } var self = this; return travel(root); } BSTree.prototype.deleteMax = function() { this.root = this._deleteMax(this.root); } BSTree.prototype._deleteMax = function(root) { if(!root) return null; function travel(node) { if(node.left) node.right = travel(node.right); else { return node.left; } } var self = this; return travel(root); }
deleteMax和deleteMin的实现刚好相反,这里删除节点的时候只需要修改一个链接比较容易实现。
BSTree.prototype.delete = function(k) { function travel(node) { if(!node) return null; var ret = self.compare(k, node.key); if(ret > 0) return node.right = travel(node.right); if(ret < 0) return node.left = travel(node.left); if(ret == 0) { if(!node.left) return node.right; if(!node.right) return node.left; var tmp = node; node = self._min(node.right); node.left = tmp.left; node.right = self._deleteMin(node.right); } node.N = self._size(node.left) + self._size(node.right) + 1; return node; } var self = this; this.root = travel(this.root); }
删除指定节点需要考虑被删除节点
left
和right
都存在的情况。基本思路就是用该节点的后继节点来替代该节点。
觉得可用,就经常来吧! 脚本宝典 欢迎评论哦! js脚本,巧夺天工,精雕玉琢。小宝典献丑了!
以上是脚本宝典为你收集整理的javascript代码实例教程-Javascript-BinarySearchTree全部内容,希望文章能够帮你解决javascript代码实例教程-Javascript-BinarySearchTree所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。