优秀网站建设网页,青岛网站建设公司招聘,房地产政策最新消息2022,阿里云1M做网站文章目录 1.概述2. 查找2.1 查找#xff1a;算法2.2 查找#xff1a;理解2.3 查找#xff1a;实现2.4 查找#xff1a;语义 3. 插入3.1 插入#xff1a;算法3.2 插入#xff1a;实现 4. 删除4.1 删除#xff1a;框架4.2 删除#xff1a;单分支4.3 删除#xff1a;双分… 文章目录 1.概述2. 查找2.1 查找算法2.2 查找理解2.3 查找实现2.4 查找语义 3. 插入3.1 插入算法3.2 插入实现 4. 删除4.1 删除框架4.2 删除单分支4.3 删除双分支 1.概述
之前介绍了二叉搜索树的概念和性质可以看到相对其他数据结构二叉搜索树的特征首先体现在它独特的元素访问方式也就是寻关键码访问call by key。
而所有这类访问无非都是通过三种主要的操作接口完成的也就是静态查找search以及动态插入和删除。
接下来讨论在三个接口的背后分别应该采用什么算法这些算法又该如何实现显示的效率又将如何
2. 查找
2.1 查找算法
作为最基本操作接口首当其冲自然是查找。 那么如何在BST中查找特定的关键码呢看上图中具体实例。 首先按照上节推荐方法验证这的确是一棵BST。 ~ 每一次查找都是从根节点开始假设要查找22那么首先将目标关键码22与根节点处所对应的关键码16做一比较不难看出22相对16更大那么这样一判断结果意味着什么应该记得BST所处处具有的顺序性是的对于根节点而言它的左后代都不可能比它更大而当前的查找目标却比它更大这就意味着根节点的整棵左子树都可以被忽略掉反过来如果树中的确存有目标关键码22那么它也必然位于右子树中因此接下来应相应转入这棵右子树具体地也就是将控制权交给这棵子树的树根25。同样的每当进入一棵子树都要将目标关键码与当前的子树根节点进行比较经过这次比较发现目标关键码22相对于子树根节点要更小那么这意味着什么呢同样地根据顺序性节点25的所有右后代都不会比25小都不可能等于目标关键码22因此这些节点同样可以被忽略掉反过来如果目标关键码的确存在于这棵子树中那么它也只能存在于其中的左子树中接下来要顺藤摸瓜转入25的左子树也就是将控制权交给这棵子树的根节点19。在进入这棵子树之后同样要将目标关键码22与这棵子树的树根19进行比较并可以相应忽略掉它的所有左后代虽然现在只有一个而将查找范围缩小到这个根节点的右子树最后一步在相应进入到这棵右子树之后同样要将这棵子树的根节点22与目标节点进行比较终于返现二者相等至此这次查找也就相应地以成功而告终。 现在请留意观察在下方列出的这样一个序列应该看出来这就是这棵BST的中序遍历序列。好的现在假想地认为它就是一个向量当然根据全局单调性它必然是一个有序向量。以下将重新回顾下在这棵BST中刚才的搜索过程不妨体味一下这样一个搜索过程在下方的有序向量中对应于怎样的一个过程。
2.2 查找理解 查找首先是对根节点进行一次比较在有序向量中这对应于以某个轴点为基准进行一次比较这次比较的结果既可以认为是摒弃掉整棵树的左子树同时也可以等效地认为是摒弃掉整个向量的左侧子向量当然也包括根节点以及轴点本身。而接下来所做的决策也就是深入到BST的右子树中这也可以等效地认为在有序向量中将搜索的范围有效地收缩到它的右子向量中。以下过程只不过是刚才那一步骤在不同程度上的简单重放而已每一次都会摒弃掉一棵子树或等效的一个子向量并且深入到对应的另一侧子树或者说另一侧子向量每次对新的根节点的比较也相当于在向量中对新的轴点进行比较如此往复直到最终收缩为仅含一个元素。
其实对于并不存在的关键码所做的查找虽然会以失败告终但整个过程相仿。 比如在这棵树中搜索23依然会在16这个位置向右并且在25这个位置向左再在19这个位置向右直到最终到22这个位置依然试图向右但是此时已经无路可走了。在这样一个情况下也就是可以判断整个查找失败的时机与成功的查找相比无非增加了最后一次额外的判断而已本质上没有任何区别。 不难看出在这个算法的背后也就是已经熟知的减而治之策略。 具体来说这里不过是通过一次又一次的比较逐步地缩小整个查找地范围直至最终抵达平凡地情况。 通过方才对中序遍历序列的比照也可以看出整个过程也可以等效地视作是在仿效此前有序向量所行之有效的那种二分查找策略那么这样一个策略以及查找的过程如何具体实现为代码呢
2.3 查找实现
以下给出BST查找算法的一种实现方式 可以看到对外的标准search接口实际上在内部是调用了名为searchIn的一个功能来实现的。
而作为一个更为基本的算法searchIn可以实现如下 具体来说也就是在以v为根的当前子树中去查找某一个特定的关键码e。作为一个递归函数首先给出了递归基比如如果当前子树已经为空就可以直接返回失败。否则如果当前根节点与目标关键码正好相等也就意味着查找成功无论如何在这种情况下都可以直接返回。 ~ 而在一般情况下也就是子树非空同时也没有在子树的树根处命中就继续递归地深入查找而查找范围在经过一次比较之后可以相应地确定为究竟是左子树还是右子树。 不难看出这个算法每递归一次当前节点v都会下降一层因此这个算法在最坏情况下地递归深度也不会超过树的高度这也是这个算法时间复杂度。
2.4 查找语义
最后再来考察这里地hot参数作为一个引用型的参数它总是在这个算法被首次调用时统一初始化为初值为NULL的内部变量_hot因此在随后算法的执行过程中对这个参数的修改实质上也就是对内部变量_hot的修改可以看到对_hot的修改总是发生在每一次试图深入递归之前具体来说_hot会记下此前刚刚接受访问的那个非空的节点。
那么总体而言_hot最终将会指向谁呢它所对应的语义又是什么呢 为了便于search接口更加简洁也更加准确地被其他的算法使用有必要对它的接口语义予以明确地定义这体现在两个方面。
首先这个接口的返回值在不同的情况下分别对应什么 这些语义可以通过上图来表示。实际上也无非就是查找成功以及查找失败这两种情况。 ~ 我们知道返回值本身也是引用类型的这里约定在查找成功时返回的引用将指向一个真实存在的节点而且这个节点恰好与目标关键码相等。而在查找失败时返回的引用将指向一个空节点这里所说的空节点是指首先它的数值为NULL但正因为它是一个引用更确切地讲此时所返回的那个数值为null的引用。实际上就是在整个查找的过程中最后一步所试图转入的那个数值为空的分支它指向查找路径末端节点当前仍不存在的某一个孩子。 其次经过这个算法的反复更新_hot变量的最终取值在各种情况下有对应什么
在查找成功时它将指向命中返回节点的父亲。而在失败的时候它将指向在整个查找过程中最后访问的一个真实存在的节点。
那么如何从语义上将这两种情况下的返回值以及_hot变量统一起来呢 一种简明的方法就是引入哨兵。是的在查找失败的时候可以在末端节点试图转向的那个数值当前为空的引用处增加个假想的哨兵而且可以进一步的假想着将它的关键码就设置为查找目标。当然不难验证如果此时的确在这个位置增加一个这样的真实的节点那么全树依然将是一棵合法的BST。而更有意义的是在引入了这样一个假想的哨兵之后就可以从语义上将两种情况统一起来。 具体来说也就是无论成功与否返回值总是等效的指向命中节点。尽管在失败情况下这个命中节点只是假想的而非真是存在的。而在如此引入了一个假想的哨兵之后_hot也可以认为总是指向命中节点的父亲。
那么基于这样一个语义明确的search接口插入、删除算法又当如何具体实现呢
3. 插入
3.1 插入算法
介绍下BST的插入算法。 具体来说如果插入的关键码为e需要首先调用search接口对它进行定位。既然已经约定禁止雷同元素存在所以这里不妨假设e还不存在。请注意此时的search尽管会以失败告终但_hot变量将会指向查找路径的末端节点而更重要的是作为返回值_hot的某一个当前仍为空的孩子恰好就是待插入节点应该接入的位置。
来看一个具体的实例 同样地需要首先确认这是一棵BST接下来如果需要插入40就会在search的过程中经过一系列的比较将查找的范围逐步地收缩直至最终失败于46。请注意在此时_hot指向的就是这个46而此时search的返回值恰好就是46当前为NULL的那个左孩子引用因此只需将待插入的关键码封装为一个节点并且令46对应的那个孩子引用改为指向这个新节点即可完成这次插入操作。插入之后就像上图右上方所示。 ~ 进一步假设需要再插入55同样地经过一系列的搜索最终失败于53。请注意尽管此时53的左孩子是存在的但是根据55和53的大小在这个位置最终试图转向的是它的右孩子只不过右孩子当前为空所以search返回的恰好就是53这个当前为空的右孩子引用而根据此前所做的统一语义约定在此时_hot指向的恰好就是53因此同样地只需将待插入的55封装为节点并且令53原先为空的那个孩子引用改为指向这个新节点也可以顺利地完成一次插入操作。新插入的节点以及此后所对应的BST就是上图右下方的图。 既然每个新节点所插入的位置在此前都是为空所以在插入之后它们也必然是叶子这也是为什么它们都被画作方形而不是圆形。
好了接下来的问题自然就是这样一个插入过程如何体现为具体代码呢
3.2 插入实现
BST的插入算法可以具体地实现如下 首先针对目标进行一次查找而且按照约定这里会忽略掉雷同的元素。也就是说算法的确会终止于_hot而返回一个名为x数值为空的引用所以接下来只需创建一个关键码为e的新节点并且将_hot作为它的父亲。没错创建一个以e为关键码的新节点并且以_hot作为父亲。同时还需要通过这个赋值语句令x不再为空而改为指向这个新创建的节点完成节点的双向连接至此就完成了新创建的这个节点与原树的正确连接。当然接下来还需要更新这棵树的规模以及新节点历代祖先的高度。 这个代码虽然简单但是它可以处理各种边界情况。
那么如此实现的insert接口累计的时间复杂度是多少呢答案是Oh 不难看出时间消耗主要集中在两个方面也就是search以及updataHeightAbove而且这二者在最坏情况下都不会超过整棵树的高度。因此总体而言算法的时间复杂度不过Oh。 4. 删除
4.1 删除框架
相对于节点插入操作BST的节点删除操作要略微复杂一些在此不妨先给出整个算法的主题框架 可以看到首先也需要针对目标做一次查找定位而且与插入操作正好对称这里需要忽略的是元素尚不存在的情况反过来如果这个元素的确存在就会调用一个名为removeAt的内部例程来真正地实施删除。当然接下来同样要更新全树的规模同时更新相关祖先的高度。 就运行时间而言如果暂时忽略掉removeAt接口整个算法时间消耗依然主要集中于search以及updateHeightAbove这两个例程所以同样地这些时间累计而言也不会超过全树的高度Oh。
那么接下来的问题就是removeAt可能需要处理哪几种情况各种情况又当如何具体应对呢
4.2 删除单分支
先来考虑第一种情况这也是相对而言更为简单的一种情况。 它的特征是经过查找所确定的那个目标节点x至多只有一个孩子或者反过来它至少有某棵子树是空的。 比如在这样一棵BST中上图中最上方图如果试图删除其中的69那么经过逐层地不断深入最终的确可以定位到69而且会发现69至多只有一个孩子此时只需将这个节点大胆地删除掉并且取而代之以它那个非空地孩子在这里也就是64不难验证经过这样的处理之后整颗BST依然是一棵名副其实的BST。 因此接下来不妨将这种情况下的处理方法整理并且实现为具体的代码比如下面就是一种可能的实现方式。 在这个名为removeAt的算法中要删除的对象是以x指示的那个节点请注意在此前经过搜索所确定的hot也会作为参数传入。接下来需要进行判断如果x的左孩子并不存在那么只需直接用它的右孩子来代替新近提升一层的节点。对称地如果当前节点没有右孩子也可以直接用左孩子来代替。这也就是刚刚所说的第一种情况。 ~ 需要特别指出的是其实这两种情况还涵盖了一种非常特殊的情况也就是左右孩子可能同时为空针对这种特殊情况它依然是能够正确处理。 经过这样的替换操作之后新进提升一层的节点还需要与它此前的祖父完成直接的连接这也是以下这两句所完成的任务。至此情况一的处理已经完全结束。
当然接下来比较棘手的是互补的那种情况也就是尽管删除的目标存在但是它的左右孩子同时存在情况一的策略在这种情况下无法直接套用那么面对这种情况又当如何处置呢
4.3 删除双分支
在这里需要再次使用计算机科学中的法宝也就是化繁为简具体来说要将比较棘手的第二种情况有效地转化为第一种情况。 以上左图中的一棵BST为例假设需要删除节点36可以看到这个节点的确是比较棘手的情况因为它的左右后代都存在此时不妨找到它的直接后继每次直接后继。 应该记得在实现二叉树的时候对于BinNode类型曾经实现一个名为succ接口。应该记得它的功能与语义没错就是返回当前节点在中序遍历下的直接后继。 ~ 具体来说也就是在全树中f不小于当前节点的最小节点回顾当时的succ算法在当前节点拥有右后代情况下算法将首先进入到它所对应的右子树然后在右子树中沿着左侧分支不断地下行直到最终不能下行而整个过程最终所抵达地节点就应该是当前节点地直接后继。 对于这个例子而言36地直接后继就是40那么接下来可以用当前节点36与它的直接后继40互相兑换比如对这个例子而言兑换后的状态就是上中图。 可能会有点担心因为此时的这棵树在36位置违反了顺序性它已经不再是一棵BST。是的担心非常有道理但是其实大可不必因为这样一个状态只是一个瞬态马上就会使它成为一棵BST而且能够将目标节点删除。是的此时已经可以着手对目标节点实施删除了难道不是吗 稍加观察不难发现此时的局部3646已经转化为此前的第一种情况也就是说待删除36至多只有一个孩子更确切地讲它只有右孩子为什么它没有左孩子呢因为作为此前节点地直接后继它必然是某条左侧分支地末端自然没有左孩子喽。既然如此可以直接沿用此前第一种情况的处理手法也就是用待删除节点36的右孩子46去顶替36可以得到上右图。 此时不难验证这棵树已经恢复成一棵不择不扣的BST。
需要特意说明的是在此后还需要令内部_hot变量指向刚刚被实际删除的节点的父亲并且从53开始不断地向上追溯历代祖先因为这些祖先的高度有可能因为刚才后代36的删除而发生变化。
那么同样地这样一颗化繁为简并且顺利处理的过程如何描述并且实现为具体代码呢 还是回到刚刚尚未完成的removeAt算法来补充对第二种情况的处理方法。
按照刚才的分析只需要找出当前节点的直接后继并且令这两个节点数据互换从而等效地将待删除节点转移至新的位置而且这个位置至多只有一个分支当然这个分支只可能是右孩子要将待删除节点顶替为右孩子只需在这个右孩子以及它此前的祖父之间正确地完成一次双向连接。
复杂度 好了那么作为remove算法地有机部分这个removeAt算法它的时间复杂度又是多少呢是否会超过remove原有的O(h)复杂度呢 幸好不会原因在于removeAt本身并不包含任何循环而其中唯一可能引起复杂度的无非是在第二种情况下对succ()接口的调用而按照此前的实现方法以及分析结论这个接口所需要的时间这个接口所需要的时间也不会超过全树的高度O(h)。 至此可以得出结论BST的删除操作与插入操作一样在最坏情况下所需要的时间不会操作全树当时的高度h。
那么这个结论是好还是不足够好呢后面将针对这个问题做进一步的探讨。
