去类似美团网站做软件开发,如何搭建一个网站步骤,管理咨询行业的理解,wordpress访问子网站文章目录 一、二叉搜索树的封装1.插入数据2.遍历数据2.1.先序遍历2.2.中序遍历2.3.后续遍历 3.查找数据3.1.查找最大值最小值3.2.查找特定值 4.删除数据4.1.情况1#xff1a;没有子节点4.2.情况2#xff1a;有一个子节点4.3.情况3#xff1a;有两个子节点4.4.完整实现 … 文章目录 一、二叉搜索树的封装1.插入数据2.遍历数据2.1.先序遍历2.2.中序遍历2.3.后续遍历 3.查找数据3.1.查找最大值最小值3.2.查找特定值 4.删除数据4.1.情况1没有子节点4.2.情况2有一个子节点4.3.情况3有两个子节点4.4.完整实现 5.二叉搜索树完整封装 二、平衡树 一、二叉搜索树的封装
二叉树搜索树的基本属性
如图所示二叉搜索树有四个最基本的属性指向节点的根root节点中的键key、左指针right、右指针right。 所以二叉搜索树中除了定义root属性外还应定义一个节点内部类里面包含每个节点中的left、right和key三个属性 //封装二叉搜索树function BinarySearchTree(){//节点内部类function Node(key){this.key keythis.left nullthis.right null}//属性this.root null}二叉搜索树的常见操作
insertkey向树中插入一个新的键searchkey在树中查找一个键如果节点存在则返回true如果不存在则返回falseinOrderTraverse通过中序遍历方式遍历所有节点preOrderTraverse通过先序遍历方式遍历所有节点postOrderTraverse通过后序遍历方式遍历所有节点min返回树中最小的值/键max返回树中最大的值/键removekey从树中移除某个键
1.插入数据
实现思路
首先根据传入的key创建节点对象然后判断根节点是否存在不存在时通过this.root newNode直接把新节点作为二叉搜索树的根节点。若存在根节点则重新定义一个内部方法insertNode用于查找插入点。 //insert方法:对外向用户暴露的方法BinarySearchTree.prototype.insert function(key){//1.根据key创建节点let newNode new Node(key)//2.判断根节点是否存在if (this.root null) {this.root newNode//根节点存在时}else {this.insertNode(this.root, newNode)}}内部方法insertNode的实现思路:
根据比较传入的两个节点一直查找新节点适合插入的位置直到成功插入新节点为止。
当newNode.key node.key向左查找:
情况1当node无左子节点时直接插入情况2当node有左子节点时递归调用insertNode(),直到遇到无左子节点成功插入newNode后不再符合该情况也就不再调用insertNode()递归停止。 当newNode.key node.key向右查找与向左查找类似
情况1当node无右子节点时直接插入情况2当node有右子节点时依然递归调用insertNode(),直到遇到传入insertNode方法的node无右子节点成功插入newNode为止 insertNode()代码实现 //内部使用的insertNode方法:用于比较节点从左边插入还是右边插入BinarySearchTree.prototype.insertNode function(node, newNode){//当newNode.key node.key向左查找
/*----------------------分支1:向左查找--------------------------*/ if(newNode.key node.key){//情况1node无左子节点直接插入
/*----------------------分支1.1--------------------------*/if (node.left null) {node.left newNode//情况2node有左子节点递归调用insertNode(),直到遇到无左子节点成功插入newNode后不再符合该情况也就不再调用insertNode()递归停止。
/*----------------------分支1.2--------------------------*/}else{this.insertNode(node.left, newNode)}//当newNode.key node.key向右查找
/*-----------------------分支2:向右查找--------------------------*/ }else{//情况1node无右子节点直接插入
/*-----------------------分支2.1--------------------------*/ if(node.right null){node.right newNode//情况2node有右子节点依然递归调用insertNode(),直到遇到无右子节点成功插入newNode为止
/*-----------------------分支2.2--------------------------*/ }else{this.insertNode(node.right, newNode)}}}过程详解
为了更好理解以下列二叉搜索树为例 想要上述的二叉搜索树蓝色中插入数据10
先把key 10 传入insert方法由于存在根节点 9所以直接调用insetNode方法传入的参数node 9newNode 10由于10 9进入分支2向右查找适合插入的位置由于根节点 9 的右子节点存在且为 13 所以进入分支2.2递归调用insertNode方法传入的参数node 13newNode 10由于 10 13 进入分支1向左查找适合插入的位置由于父节点 13 的左子节点存在且为11所以进入分支1.2递归调用insertNode方法传入的参数node 11newNode 10由于 10 11进入分支1向左查找适合插入的位置由于父节点 11 的左子节点不存在所以进入分支1.1成功插入节点 10 。由于不符合分支1.2的条件所以不会继续调用insertNode方法递归停止。
测试代码 //测试代码//1.创建BinarySearchTreelet bst new BinarySearchTree()//2.插入数据bst.insert(11);bst.insert(7);bst.insert(15);bst.insert(5);bst.insert(9);console.log(bst);应得到下图所示的二叉搜索树 测试结果 2.遍历数据
这里所说的树的遍历不仅仅针对二叉搜索树而是适用于所有的二叉树。由于树结构不是线性结构所以遍历方式有多种选择常见的三种二叉树遍历方式为
先序遍历中序遍历后序遍历
还有层序遍历使用较少。
2.1.先序遍历
先序遍历的过程为
首先遍历根节点然后遍历其左子树最后遍历其右子树 如上图所示二叉树的节点遍历顺序为A - B - D - H - I - E - C - F - G。
代码实现 //先序遍历//掺入一个handler函数方便之后对得到的key进行处理BinarySearchTree.prototype.preOrderTraversal function(handler){this.preOrderTraversalNode(this.root, handler)}//封装内部方法对某个节点进行遍历BinarySearchTree.prototype.preOrderTraversalNode function(node,handler){if (node ! null) {//1.处理经过的节点handler(node.key)
/*----------------------递归1----------------------------*///2.遍历左子树中的节点this.preOrderTraversalNode(node.left, handler)
/*----------------------递归2----------------------------*///3.遍历右子树中的节点this.preOrderTraversalNode(node.right, handler)}}过程详解
以遍历以下二叉搜索树为例 首先调用preOrderTraversal方法在方法里再调用preOrderTraversalNode方法用于遍历二叉搜索树。在preOrderTraversalNode方法中递归1负责遍历左子节点递归2负责遍历右子节点。先执行递归1执行过程如下图所示 记preOrderTraversalNode() 为 A() 可以看到一共递归调用了4次方法A分别传入11、7、5、3最后遇到null不满足 node ! null 条件结束递归1注意此时只是执行完最开始的递归1并没有执行递归2并且递归1执行到null停止后要一层层地往上返回按顺序将调用的函数压出函数调用栈。
关于函数调用栈之前的四次递归共把4个函数压入了函数调用栈现在递归执行完了一层层地把函数压出栈。
值得注意的是每一层函数都只是执行完了递归1当返回到该层函数时比如A3要继续执行递归2遍历二叉搜索树中的右子节点
在执行递归2的过程中会不断调用方法A并依次执行递归1和递归2以此类推直到遇到null不满足 node ! null 条件为止才停止递归并一层层返回如此循环。同理A5层、A7层、A11层都要经历上述循环直到将二叉搜索树中的节点全部遍历完为止。
具体过程如下图所示 测试代码 //测试代码//1.创建BinarySearchTreelet bst new BinarySearchTree()//2.插入数据bst.insert(11);bst.insert(7);bst.insert(15);bst.insert(5);bst.insert(3);bst.insert(9);bst.insert(8);bst.insert(10);bst.insert(13);bst.insert(12);bst.insert(14);bst.insert(20);bst.insert(18);bst.insert(25);bst.insert(6);//3.测试遍历let resultString //掺入处理节点值的处理函数bst.preOrderTraversal(function(key){resultString key -})alert(resultString)应输出这样的顺序11 - 7 - 5 - 3 - 6 - 9 - 8 - 10 - 15 - 13 -12 - 14 - 20 - 18 - 25 。
测试结果 2.2.中序遍历
实现思路与先序遍历原理相同只不过是遍历的顺序不一样了。
首先遍历其左子树然后遍历根父节点最后遍历其右子树
代码实现 //中序遍历BinarySearchTree.prototype.midOrderTraversal function(handler){this.midOrderTraversalNode(this.root, handler)}BinarySearchTree.prototype.midOrderTraversalNode function(node, handler){if (node ! null) {//1.遍历左子树中的节点this.midOrderTraversalNode(node.left, handler)//2.处理节点handler(node.key)//3.遍历右子树中的节点this.midOrderTraversalNode(node.right, handler)}}过程详解
遍历的顺序应如下图所示 首先调用midOrderTraversal方法在方法里再调用midOrderTraversalNode方法用于遍历二叉搜索树。先使用递归1遍历左子树中的节点然后处理父节点最后遍历右子树中的节点。
测试代码 //测试代码//1.创建BinarySearchTreelet bst new BinarySearchTree()//2.插入数据bst.insert(11);bst.insert(7);bst.insert(15);bst.insert(5);bst.insert(3);bst.insert(9);bst.insert(8);bst.insert(10);bst.insert(13);bst.insert(12);bst.insert(14);bst.insert(20);bst.insert(18);bst.insert(25);bst.insert(6); //3.测试中序遍历let resultString2 bst.midOrderTraversal(function(key){resultString2 key -})alert(resultString2)输出节点的顺序应为3 - 5 - 6 - 7 - 8 - 9 - 10 - 11 - 12 - 13 - 14 - 15 - 18 - 20 - 25 。
测试结果 2.3.后续遍历
实现思路与先序遍历原理相同只不过是遍历的顺序不一样了。
首先遍历其左子树然后遍历其右子树最后遍历根父节点
代码实现 //后序遍历BinarySearchTree.prototype.postOrderTraversal function(handler){this.postOrderTraversalNode(this.root, handler)}BinarySearchTree.prototype.postOrderTraversalNode function(node, handler){if (node ! null) {//1.遍历左子树中的节点this.postOrderTraversalNode(node.left, handler)//2.遍历右子树中的节点this.postOrderTraversalNode(node.right, handler)//3.处理节点handler(node.key)}}过程详解
遍历的顺序应如下图所示 首先调用postOrderTraversal方法在方法里再调用postOrderTraversalNode方法用于遍历二叉搜索树。先使用递归1遍历左子树中的节点然后遍历右子树中的节点最后处理父节点。
测试代码 //测试代码//1.创建BinarySearchTreelet bst new BinarySearchTree()//2.插入数据bst.insert(11);bst.insert(7);bst.insert(15);bst.insert(5);bst.insert(3);bst.insert(9);bst.insert(8);bst.insert(10);bst.insert(13);bst.insert(12);bst.insert(14);bst.insert(20);bst.insert(18);bst.insert(25);bst.insert(6);//3.测试后序遍历let resultString3 bst.postOrderTraversal(function(key){resultString3 key -})alert(resultString3)输出节点的顺序应为3 - 6 - 5 - 8 - 10 - 9 - 7 - 12 - 14 - 13 - 18 - 25 - 20 - 15 - 11 。
测试结果 **总结**以遍历根父节点的顺序来区分三种遍历方式。比如先序遍历先遍历根节点、中序遍历第二遍历根节点、后续遍历最后遍历根节点。
3.查找数据
3.1.查找最大值最小值
在二叉搜索树中查找最值非常简单最小值在二叉搜索树的最左边最大值在二叉搜索树的最右边。只需要一直向左/右查找就能得到最值如下图所示 代码实现 //寻找最大值BinarySearchTree.prototype.max function () {//1.获取根节点let node this.root//2.定义key保存节点值let key null//3.依次向右不断查找直到节点为nullwhile (node ! null) {key node.keynode node.right}return key}//寻找最小值BinarySearchTree.prototype.min function(){//1.获取根节点let node this.root//2.定义key保存节点值let key null//3.依次向左不断查找直到节点为nullwhile (node ! null) {key node.keynode node.left}return key}测试代码 //测试代码//1.创建BinarySearchTreelet bst new BinarySearchTree()//2.插入数据bst.insert(11);bst.insert(7);bst.insert(15);bst.insert(5);bst.insert(3);bst.insert(9);bst.insert(8);bst.insert(10);bst.insert(13);bst.insert(12);bst.insert(14);bst.insert(20);bst.insert(18);bst.insert(25);bst.insert(6);//4.测试最值console.log(bst.max());console.log(bst.min());
测试结果 3.2.查找特定值
查找二叉搜索树当中的特定值效率也非常高。只需要从根节点开始将需要查找节点的key值与之比较若node.key root则向左查找若node.key root就向右查找直到找到或查找到null为止。这里可以使用递归实现也可以采用循环来实现。
实现代码 //查找特定的keyBinarySearchTree.prototype.search function(key){//1.获取根节点let node this.root//2.循环搜索keywhile(node ! null){if (key node.key) {//小于根(父)节点就往左边找node node.left//大于根(父)节点就往右边找}else if(key node.key){node node.right}else{return true}} return false}测试代码 //测试代码//1.创建BinarySearchTreelet bst new BinarySearchTree()//2.插入数据bst.insert(11);bst.insert(7);bst.insert(15);bst.insert(5);bst.insert(3);bst.insert(9);bst.insert(8);bst.insert(10);bst.insert(13);bst.insert(12);bst.insert(14);bst.insert(20);bst.insert(18);bst.insert(25);bst.insert(6);//3.测试搜索方法console.log(bst.search(24));//falseconsole.log(bst.search(13));//trueconsole.log(bst.search(2));//false测试结果 4.删除数据
实现思路
**第一步**先找到需要删除的节点若没找到则不需要删除
首先定义变量current用于保存需要删除的节点、变量parent用于保存它的父节点、变量isLeftChild保存current是否为parent的左节点这样方便之后删除节点时改变相关节点的指向。
实现代码 //1.1.定义变量let current this.rootlet parent nulllet isLeftChild true//1.2.开始寻找删除的节点while (current.key ! key) {parent current// 小于则往左查找if (key current.key) {isLeftChild truecurrent current.left} else{isLeftChild falsecurrent current.rigth}//找到最后依然没有找到相等的节点if (current null) {return false}}//结束while循环后current.key key**第二步**删除找到的指定节点后分3种情况
删除叶子节点删除只有一个子节点的节点删除有两个子节点的节点
4.1.情况1没有子节点
没有子节点时也有两种情况
当该叶子节点为根节点时如下图所示此时current this.root直接通过this.root null删除根节点。 当该叶子节点不为根节点时也有两种情况如下图所示 若current 8可以通过parent.left null删除节点8
若current 10可以通过parent.right null删除节点10
代码实现 //情况1删除的是叶子节点(没有子节点)if (current.left null current.right null) {if (current this.root) {this.root null}else if(isLeftChild){parent.left null}else {parent.right null}}4.2.情况2有一个子节点
有六种情况分别是
当current存在左子节点时current.right null
情况1current为根节点current this.root如节点11此时通过this.root current.left删除根节点11情况2current为父节点parent的左子节点isLeftChild true如节点5此时通过parent.left current.left删除节点5情况3current为父节点parent的右子节点isLeftChild false如节点9此时通过parent.right current.left删除节点9 当current存在右子节点时current.left null
情况4current为根节点current this.root如节点11此时通过this.root current.right删除根节点11。情况5current为父节点parent的左子节点isLeftChild true如节点5此时通过parent.left current.right删除节点5情况6current为父节点parent的右子节点isLeftChild false如节点9此时通过parent.right current.right删除节点9 实现代码 //情况2删除的节点有一个子节点//当current存在左子节点时else if(current.right null){if (current this.root) {this.root current.left} else if(isLeftChild) {parent.left current.left} else{parent.right current.left}//当current存在右子节点时} else if(current.left null){if (current this.root) {this.root current.rigth} else if(isLeftChild) {parent.left current.right} else{parent.right current.right} }4.3.情况3有两个子节点
这种情况十分复杂首先依据以下二叉搜索树讨论这样的问题 删除节点9
在保证删除节点9后原二叉树仍为二叉搜索树的前提下有两种方式
方式1从节点9的左子树中选择一合适的节点替代节点9可知节点8符合要求方式2从节点9的右子树中选择一合适的节点替代节点9可知节点10符合要求 删除节点7
在保证删除节点7后原二叉树仍为二叉搜索树的前提下也有两种方式
方式1从节点7的左子树中选择一合适的节点替代节点7可知节点5符合要求方式2从节点7的右子树中选择一合适的节点替代节点7可知节点8符合要求 删除节点15
在保证删除节点15后原树二叉树仍为二叉搜索树的前提下同样有两种方式
方式1从节点15的左子树中选择一合适的节点替代节点15可知节点14符合要求方式2从节点15的右子树中选择一合适的节点替代节点15可知节点18符合要求 相信你已经发现其中的规律了
规律总结如果要删除的节点有两个子节点甚至子节点还有子节点这种情况下需要从要删除节点下面的子节点中找到一个合适的节点来替换当前的节点。
若用current表示需要删除的节点则合适的节点指的是
current左子树中比current小一点点的节点即current左子树中的最大值current右子树中比current大一点点的节点即current右子树中的最小值
前驱后继
在二叉搜索树中这两个特殊的节点有特殊的名字
比current小一点点的节点称为current节点的前驱。比如下图中的节点5就是节点7的前驱比current大一点点的节点称为current节点的后继。比如下图中的节点8就是节点7的后继 代码实现
查找需要被删除的节点current的后继时需要在current的右子树中查找最小值即在current的右子树中一直向左遍历查找查找前驱时则需要在current的左子树中查找最大值即在current的左子树中一直向右遍历查找。
下面只讨论查找current后继的情况查找前驱的原理相同这里暂不讨论。
4.4.完整实现 //删除节点BinarySearchTree.prototype.remove function(key){
/*------------------------------1.寻找要删除的节点---------------------------------*///1.1.定义变量current保存删除的节点parent保存它的父节点。isLeftChild保存current是否为parent的左节点let current this.rootlet parent nulllet isLeftChild true//1.2.开始寻找删除的节点while (current.key ! key) {parent current// 小于则往左查找if (key current.key) {isLeftChild truecurrent current.left} else{isLeftChild falsecurrent current.right}//找到最后依然没有找到相等的节点if (current null) {return false}}//结束while循环后current.key key/*------------------------------2.根据对应情况删除节点------------------------------*///情况1删除的是叶子节点(没有子节点)if (current.left null current.right null) {if (current this.root) {this.root null}else if(isLeftChild){parent.left null}else {parent.right null}}//情况2删除的节点有一个子节点//当current存在左子节点时else if(current.right null){if (current this.root) {this.root current.left} else if(isLeftChild) {parent.left current.left} else{parent.right current.left}//当current存在右子节点时} else if(current.left null){if (current this.root) {this.root current.right} else if(isLeftChild) {parent.left current.right} else{parent.right current.right} }//情况3删除的节点有两个子节点else{//1.获取后继节点let successor this.getSuccessor(current)//2.判断是否根节点if (current this.root) {this.root successor}else if (isLeftChild){parent.left successor}else{parent.right successor}//3.将后继的左子节点改为被删除节点的左子节点successor.left current.left}}//封装查找后继的方法BinarySearchTree.prototype.getSuccessor function(delNode){//1.定义变量,保存找到的后继let successor delNodelet current delNode.rightlet successorParent delNode//2.循环查找current的右子树节点while(current ! null){successorParent successorsuccessor currentcurrent current.left}//3.判断寻找到的后继节点是否直接就是删除节点的right节点if(successor ! delNode.right){successorParent.left successor.rightsuccessor.right delNode.right }return successor}测试代码 //测试代码//1.创建BinarySearchTreelet bst new BinarySearchTree()//2.插入数据bst.insert(11);bst.insert(7);bst.insert(15);bst.insert(5);bst.insert(3);bst.insert(9);bst.insert(8);bst.insert(10);bst.insert(13);bst.insert(12);bst.insert(14);bst.insert(20);bst.insert(18);bst.insert(25);bst.insert(6);bst.insert(19);//3.测试删除代码//删除没有子节点的节点bst.remove(3)bst.remove(8)bst.remove(10)//删除有一个子节点的节点bst.remove(5)bst.remove(19)//删除有两个子节点的节点bst.remove(9)bst.remove(7)bst.remove(15)//遍历二叉搜索树并输出let resultString bst.midOrderTraversal(function(key){resultString key -})alert(resultString)测试结果 可见三种情况的节点都被成功删除了。
5.二叉搜索树完整封装 //封装二叉搜索树function BinarySearchTree(){//节点内部类function Node(key){this.key keythis.left nullthis.right null}//属性this.root null//方法//一.插入数据insert方法:对外向用户暴露的方法BinarySearchTree.prototype.insert function(key){//1.根据key创建节点let newNode new Node(key)//2.判断根节点是否存在if (this.root null) {this.root newNode//根节点存在时}else {this.insertNode(this.root, newNode)}}//内部使用的insertNode方法:用于比较节点从左边插入还是右边插入BinarySearchTree.prototype.insertNode function(node, newNode){//当newNode.key node.key向左查找if(newNode.key node.key){//情况1node无左子节点直接插入if (node.left null) {node.left newNode//情况2node有左子节点递归调用insertNode(),直到遇到无左子节点成功插入newNode后不再符合该情况也就不再调用insertNode()递归停止。}else{this.insertNode(node.left, newNode)}//当newNode.key node.key向右查找}else{//情况1node无右子节点直接插入if(node.right null){node.right newNode//情况2node有右子节点依然递归调用insertNode(),直到遇到无右子节点成功插入newNode为止}else{this.insertNode(node.right, newNode)}}}//二.树的遍历//1.先序遍历//掺入一个handler函数对得到的key进行处理BinarySearchTree.prototype.preOrderTraversal function(handler){this.preOrderTraversalNode(this.root, handler)}//封装内部方法对某个节点进行遍历BinarySearchTree.prototype.preOrderTraversalNode function(node,handler){if (node ! null) {//1.处理经过的节点handler(node.key)//2.遍历经过节点的左子节点this.preOrderTraversalNode(node.left, handler)//3.遍历经过节点的右子节点this.preOrderTraversalNode(node.right, handler)}}//2.中序遍历BinarySearchTree.prototype.midOrderTraversal function(handler){this.midOrderTraversalNode(this.root, handler)}BinarySearchTree.prototype.midOrderTraversalNode function(node, handler){if (node ! null) {//1.遍历左子树中的节点this.midOrderTraversalNode(node.left, handler)//2.处理节点handler(node.key)//3.遍历右子树中的节点this.midOrderTraversalNode(node.right, handler)}}//3.后序遍历BinarySearchTree.prototype.postOrderTraversal function(handler){this.postOrderTraversalNode(this.root, handler)}BinarySearchTree.prototype.postOrderTraversalNode function(node, handler){if (node ! null) {//1.遍历左子树中的节点this.postOrderTraversalNode(node.left, handler)//2.遍历右子树中的节点this.postOrderTraversalNode(node.right, handler)//3.处理节点handler(node.key)}}//三.寻找最值//寻找最大值BinarySearchTree.prototype.max function () {//1.获取根节点let node this.root//2.定义key保存节点值let key null//3.依次向右不断查找直到节点为nullwhile (node ! null) {key node.keynode node.right}return key}//寻找最小值BinarySearchTree.prototype.min function(){//1.获取根节点let node this.root//2.定义key保存节点值let key null//3.依次向左不断查找直到节点为nullwhile (node ! null) {key node.keynode node.left}return key}//查找特定的keyBinarySearchTree.prototype.search function(key){//1.获取根节点let node this.root//2.循环搜索keywhile(node ! null){if (key node.key) {//小于根(父)节点就往左边找node node.left//大于根(父)节点就往右边找}else if(key node.key){node node.right}else{return true}} return false}//四.删除节点BinarySearchTree.prototype.remove function(key){
/*------------------------------1.寻找要删除的节点---------------------------------*///1.1.定义变量current保存删除的节点parent保存它的父节点。isLeftChild保存current是否为parent的左节点let current this.rootlet parent nulllet isLeftChild true//1.2.开始寻找删除的节点while (current.key ! key) {parent current// 小于则往左查找if (key current.key) {isLeftChild truecurrent current.left} else{isLeftChild falsecurrent current.right}//找到最后依然没有找到相等的节点if (current null) {return false}}//结束while循环后current.key key/*------------------------------2.根据对应情况删除节点------------------------------*///情况1删除的是叶子节点(没有子节点)if (current.left null current.right null) {if (current this.root) {this.root null}else if(isLeftChild){parent.left null}else {parent.right null}}//情况2删除的节点有一个子节点//当current存在左子节点时else if(current.right null){if (current this.root) {this.root current.left} else if(isLeftChild) {parent.left current.left} else{parent.right current.left}//当current存在右子节点时} else if(current.left null){if (current this.root) {this.root current.right} else if(isLeftChild) {parent.left current.right} else{parent.right current.right} }//情况3删除的节点有两个子节点else{//1.获取后继节点let successor this.getSuccessor(current)//2.判断是否根节点if (current this.root) {this.root successor}else if (isLeftChild){parent.left successor}else{parent.right successor}//3.将后继的左子节点改为被删除节点的左子节点successor.left current.left}}//封装查找后继的方法BinarySearchTree.prototype.getSuccessor function(delNode){//1.定义变量,保存找到的后继let successor delNodelet current delNode.rightlet successorParent delNode//2.循环查找current的右子树节点while(current ! null){successorParent successorsuccessor currentcurrent current.left}//3.判断寻找到的后继节点是否直接就是删除节点的right节点if(successor ! delNode.right){successorParent.left successor.rightsuccessor.right delNode.right }return successor}}二、平衡树
二叉搜索树的缺陷
当插入的数据是有序的数据就会造成二叉搜索树的深度过大。比如原二叉搜索树右 11 7 15 组成如下图所示 当插入一组有序数据6 5 4 3 2就会变成深度过大的搜索二叉树会严重影响二叉搜索树的性能。 非平衡树
比较好的二叉搜索树它的数据应该是左右均匀分布的但是插入连续数据后二叉搜索树中的数据分布就变得不均匀了我们称这种树为非平衡树对于一棵平衡二叉树来说插入/查找等操作的效率是OlogN而对于一棵非平衡二叉树来说相当于编写了一个链表查找效率变成了ON;
树的平衡性
为了能以较快的时间OlogN来操作一棵树我们需要保证树总是平衡的
起码大部分是平衡的此时的时间复杂度也是接近OlogN的这就要求树中每个节点左边的子孙节点的个数应该尽可能地等于右边的子孙节点的个数
常见的平衡树
AVL树是最早的一种平衡树它通过在每个节点多存储一个额外的数据来保持树的平衡。由于AVL树是平衡树所以它的时间复杂度也是OlogN。但是它的整体效率不如红黑树开发中比较少用。红黑树同样通过一些特性来保持树的平衡时间复杂度也是OlogN。进行插入/删除等操作时性能优于AVL树所以平衡树的应用基本都是红黑树。
