二分搜索树

xiaoxiao2021-02-28  13

二分查找法

二分查找法是一种从有序数组中查找特定数值的方法。其JavaScript迭代实现如下:

/** * 二分查找法,通过迭代实现 * 从数据arr中,查找数据target * 如果找到了,则返回索引,未找到,则返回-1 */ function binarySearch(arr,target){ //在[lIndex,rIndex]闭区间中查找target var lIndex = 0; var rIndex = arr.length-1; while(rIndex >= lIndex){ //var midIndex = parseInt((lIndex+rIndex)/2); var midIndex = lIndex + parseInt((rIndex-lIndex)/2); if (arr[midIndex] == target) { return midIndex; } if (target < arr[midIndex]) { //target位于[lIndex,midIndex-1]范围内 rIndex = midIndex - 1; }else{ //target位于[midIndex+1,rIndex]范围内 lIndex = midIndex + 1; } } return -1; }

也可通过递归的思路实现,如下:

/** * 二分查找法的递归实现 */ function binarySearchByRecursion(arr,target,lIndex,rIndex){ if (lIndex > rIndex) { return -1; } var mid = lIndex + parseInt((rIndex-lIndex)/2); if (target == arr[mid]) { return mid; } if (target < arr[mid]) { return binarySearchByRecursion(arr,target,lIndex,mid-1); }else{ return binarySearchByRecursion(arr,target,mid+1,rIndex); } }

两种实现方法的比较:

递归实现的思维通常比较简单但递归在性能上会比迭代稍差递归法和迭代法其时间复杂度都为logn。

存在的问题:

上述二分查找法是基于数组中不存在重复元素的假设,当数组中存在重复元素时,二分查找法能找到某一个目标元素的索引,但无法确定是第几个。由此出现了二分查找法的变种:floor和ceil函数。

二分查找法变种——floor和ceil

当寻找目标target在数组中出现多次时,调用floor函数返回的是target在数组中第一次出现的位置;调用ceil函数返回的是target在数组中最后一次出现的位置。当target在数组中不存在时,floor返回的是数组中最靠后的一个比target小的元素索引。;而ceil返回的是数组中最靠前的一个比target大的元素索引。 其较为直观的实现方式如下: /* * 二分查找法的变体-floor * 当数组中存在多个target时,返回target在数组中第一次出现的位置 * 当target在数组中不存在时,floor返回的是数组中最靠后的一个比target小的元素索引。 */ function floor(arr,target){ var lIndex = -1; var rIndex = arr.length-1; //循环完毕之后,lIndex和rIndex都指向了比target小的最大索引 while(lIndex < rIndex){ var midIndex = lIndex + parseInt((rIndex-lIndex+1)/2); if (target <= arr[midIndex]) { rIndex = midIndex -1; }else{ lIndex = midIndex; } } if (arr[lIndex+1] && arr[lIndex+1] == target) { //target存在时,返回target第一次出现的索引 return lIndex+1; }else{ //target不存在时,返回比target小的最大索引 return lIndex; } } function ceil(arr,target){ var lIndex = 0; var rIndex = arr.length; while(lIndex < rIndex){ var midIndex = lIndex + parseInt((rIndex-lIndex)/2); if (target < arr[midIndex]) { rIndex = midIndex; }else{ lIndex = midIndex + 1; } } if (lIndex-1>=0 && arr[lIndex-1]==target) { return lIndex-1; }else{ return lIndex; } }

二分搜索树

二分搜索树必须满足以下特征: 1. 二叉树 2. 每个节点的键值大于左孩子 3. 每个节点的键值小于右孩子 4. 以左右孩子为根的子树任然为二分搜索树 注意,二分搜索树不一定是一棵完全二叉树。

//javascript 实现二分查找树 binarySearchTree function BST(){ this.root = null; this.count = 0; this.insert = function(key,value){ this.root = insert(this.root,key,value); } //判断二叉搜索树中是否包含键值为key的元素 this.contain = function(key){ return contain(this.root,key); } //搜索二叉树中键值为key的元素所对应的值,若不存在则返回null this.search = function(key){ return search(this.root,key); } //将nodeItem类放在BST类中,类外访问。 function nodeItem(key,value){ this.key = key; this.value = value; this.leftChild = null; this.rightChild = null; } //向以node为根节点的二分搜索树中插入新元素 //返回插入新节点的二叉搜索树的根 function insert(node,key,value){ if(node == null){ //this.count++; return new nodeItem(key,value); } if (node.key == key) { node.value == value; }else if(node.key > key){ node.leftChild = insert(node.leftChild,key,value); }else { node.rightChild = insert(node.rightChild,key,value); } return node; } //判断以node为根节点的二分搜索树中是否包含键值为key的元素 function contain(node,key){ if(node == null){ return false; } if (node.key == key) { return true; }else if(node.key > key){ return contain(node.leftChild,key); }else{ return contain(node.rightChild,key); } } //从以node为根节点的二分搜索树中查找键值为key的元素,返回该键值对应的值。如果键值不存在,则返回空 function search(node,key){ if (node == null) { return null; } if (node.key == key) { return node.value; }else if(node.key > key){ return search(node.leftChild,key); }else{ return search(node.rightChild,key); } } }

二分搜索树的遍历

前序遍历:先访问当前节点,再依次递归访问其左右子树中序遍历:先递归访问左子树,再访问自身,再递归访问右子树后续遍历:先递归访问左右子树,最后访问

上述三种遍历方式被称为深度优先遍历。

//遍历二分搜索树,并将遍历结果存在数组中 this.preOrder = function(){ return preOrder(this.root,[]); } this.inOrder = function(){ return inOrder(this.root,[]); } this.postOrder = function(){ return postOrder(this.root,[]); } //前序遍历根节点为node的二叉搜索树 function preOrder(node,resultArr){ if (node != null) { resultArr.push(node.key); preOrder(node.leftChild,resultArr); preOrder(node.rightChild,resultArr); } return resultArr; } //中序遍历根节点为node的二叉搜索树 function inOrder(node,resultArr){ if (node != null) { inOrder(node.leftChild,resultArr); resultArr.push(node.key); inOrder(node.rightChild,resultArr); } } //后序遍历根节点为node的二叉搜索树 function postOrder(node,resultArr){ if (node 1= null) { postOrder(node.leftChild,resultArr); postOrder(node.rightChild,resultArr); resultArr.push(node.key); } }

与深度优先遍历的为广度优先遍历,对应到二叉树上即为层序遍历。

this.levelOrder = function(){ return levelOrder(this.root,[]); } //层序遍历根节点为node的二叉搜索树 function levelOrder(node,resultArr){ var queue = []; if (node != null) { queue.push(node); } while(queue.length > 0){ var currentNode = queue.shift(); resultArr.push(currentNode.key); if (currentNode.leftChild != null) { queue.push(currentNode.leftChild); } if (currentNode.rightChild != null) { queue.push(currentNode.rightChild); } } return resultArr; }

获取/删除二分搜索树的最小/大值

this.getMin = function(){ return getMin(this.root); } this.getMax = function(){ return getMax(this.root); } this.deleteMin = function(){ if (this.root) { this.root = deleteMin(this.root); } } this.deleteMax = function(){ if (this.root) { this.root = deleteMax(this.root); } }

删除二分搜索树的任意值

思路: - 如果要删除的节点没有左孩子,则用其右孩子替代当前节点 - 如果要删除的节点没有右孩子,则用其左孩子替代当前节点 - 如果要删除的节点左右孩子都存在,则用其右孩子中的最小节点替代当前节点(或用其左孩子中的最大节点替代)

this.remove = function(key){ this.root = remove(this.root,key); } //删除键值为key的节点 function remove(node,key){ if (node == null) { return node; } if (key < node.key) { node.leftChild = remove(node.leftChild,key); return node; } if (key > node.key) { node.rightChild = remove(node.rightChild,key); return node; } if (node.leftChild == null) { return node.rightChild; } if (node.rightChild == null) { return node.leftChild; } var newNode = getMin(node.rightChild); newNode.rightChild = deleteMin(node.rightChild); newNode.leftChild = node.leftChild; return newNode; }

二分搜索树的顺序性

能查找二分搜索树中的最小值和最大值能找到某一元素的前驱(predecessor)和后继(successor)能找到元素的floor和ceil值判断某一元素排名第几(rank)获得排名为n的元素(select)

如何实现支持重复元素的二分搜索树

思路一:使根节点左边的元素<=根节点思路二:为节点类添加count属性,记录每一个节点出现的次数。

二分搜索树的局限性

在某些情况下构建起来的二分搜索树可能成为链表,此时,与二分搜索树所有相关的操作都将从logn级别退化为O(n)级别。

转载请注明原文地址: https://www.6miu.com/read-1250154.html

最新回复(0)