第12章 二叉查找树(3)
12.3 二叉树的插入和删除
插入和删除操作将会导致由二叉树表示的动态集合改变。要反应出这种变化,数据结构也会作出相应变化,但在修改的同时,二叉树的性质还要继续保持。正如我们看到的那样向树中插入一个新元素相对比较简单,但是处理删除操作就更加复杂了。
插入
向二叉查找树T插入一个新的元素v,我们使用TREE-INSERT方法。方法传入一个z,并且z.key=v,z.left=NIL,z.right=NIL.这个方法会将会修改T和z的一些属性,并将z插入到树的合适的位置。
图12.3 向二叉查找树中插入key为13的数据项。浅色阴影部分标明了一条从根到插入数据项的自上而下的简易路径。虚线表明了向树中添加项的链接。
图12.3展示了TREE-INSERT的工作原理。跟TREE-SEARCH和ITERATIVE-TREE-SEARCH一样,TREE-INSERT也是从根开始指针x向下遍历找到NIL替换成输入项z。这个方法维护跟踪指针y作为x的双亲。初始化完成后,第3-7行的while循环中使两个指针沿树直下而上,向左还是向右取决非于z.key与x.key的比较,直到x变成NIL。该NIL的位置就是我希望的项z插入的位置。我们还需要尾随的指针y,因为当我找到z插入的NIL位置,搜索程序往结点后一步找到需要修改的结点。第8-13行设置了相应的指针使z插入。
跟其他的二叉查找树的原始操作一样,TREE-INSERT在高为h的树中运行时间是O(h)。
删除
在二叉查找树T中删除结点z的所有方法中有三种情况,正如我们将看到的那样,有一种情况有一点复杂。
- 如果z没有孩子,我们简单的删除它并修改它的双亲,用NIL作为孩子来代替z。
- 如果z只有一个孩子,我们通过修改z双亲,用该孩子替换z,提升这个孩子代替z在树中的位置。
- 如果z有两个孩子,我们先找到z的后继y,y一定在z的右子树,然后用y替换z的位置,然后z原来的右子树变成y的新右子树,z的左子树变成y的新左子树。这种情况有一点小复杂,因为正我们所看到的,y必须是z的右孩子。
删除二叉查找树T中的指定结点z的的方法需要两个参数指针T和z.它的过程跟之前描述的三种情况有点点不同,如图12.4考虑到了四种情况。
- 如果z没有左孩子(图中的a部分),我们将右孩子替换z,右孩子也有可能是NIL。当z的右孩子为NIL,这种情况等同于z没有孩子那个情形处理。当z的右孩子为非NIL,这种情况的处理相当于z只有一个孩子,并且这个孩子是右孩子。
- 如果z只有一个孩子,这个孩子是左孩子(图中的b部分),那我们就用z的左孩子替换z。
- 除此之外,z即有左孩子又有右孩子。我们找到z的后继y,y分布在z的右子树上并且没有左孩子(查看练习12.2-5)。我们想把y拼接到当前输出的位置这样就替换了z的位置。
- 如果y是z的右孩子(图示c部分),那我们就用y替换z, 只剩下了y的右孩子。
- 除此之外,y在z的右子树里面,并不是z的右孩子(图示d部分).这种情况,我们首先我们用y来替换z的右孩子,然后再用y来替换z.
为了方便在二叉查找树中移动子树,我们定义了一个子方法TRANSPLANT,用v为根结点的子树替换以u为根结点的子树,u的双亲变成v的双亲,并且u的双亲连接v作为它合适的孩子(译者注:如果u是双亲的左孩子,那么v就是双亲左孩子,反之亦然)。
第1-2行处理u是根的情况。除此之外,u的双亲不是有左子树就是有右子树(译者注:u如果有双亲,那么u的双亲至少有一个孩子)。第3-4行如果u是一个左孩子更新u.p.left,第5行表示如果u是右孩子更新u.p.right.我们允许v为NIL,第6-7如果v为非NIL,更新v.p。TRANSPLANT没有尝试去更新v.left和v.right;要不更去更新,取决于TRANSPLANT的调用者。
图12.4 从二叉查找树中删除结点z。z结点可能是根结点,结点的q的左孩子或者结点q的右孩子。(a)z没有左孩子。我们拿它的右孩子r替换z,r可能是空或者非空。(b)结点z有左孩子l但没有右孩子。我们拿l替换z.(c)结点z有两个孩子;它的左孩子为l,它的右孩子为就是它的后继y,y的右孩子为结点x.我们用y来替换z,y的左孩子变成了l,剩下的x作为y的右孩子。(d)结点z有两个孩子(左孩子为l并且右孩子为r),并且它的后继y≠r,y在它的右子树里,右子树根结点为r。我们用y的右孩子x替换y,并且我设置y为r的双亲。然后我们设置y为q的孩子,设置y为l的双亲。
利用上面的方法TRANSPLANT,下面方法是从二叉查找树T删除结点z:
TREE-DELET方法处理了下面的四种情况。第1-2行得理结点z有左孩子,第3-4行处理z有左孩子但没有右孩子的情形。第5-12处理剩下z有两个孩子的两种情况。第5找到y,y是z的后继。因为z右子树非空,它的后继一定是右子树key最小的结点;因此调用方法TREE-MINIMUM(z.right)。从前面的介绍,我们可以知道y没有左孩子(译者注:因为y是z右子树中key最小的结点,故y没有左孩子)。我们想把y拼接到当前输出的位置并且替换树中的z。如果y是z的右孩子,第10-12行用y替换了作为z双亲的孩子替换了z,用z的左孩子替换了 y的左孩子。如是y不是z的左孩子(译者注:这里应该“如果y不是z的右孩子”)第7-9行用y的右孩子作为y双亲的孩子替换y然后把z的右孩子变成y的右孩子,然后第10-12行用y作为z的双亲的孩子替换z,用z的左孩子替换y的左孩子。
TREE-DELETE除了第5行调用了TREE-MINIMUM之行,其它每一行代码,包括调用TRANSPLANT都花费常数时间。因此TREE-DELETE在高为h的树运行时间为O(h).
总之,我们证明了下面的定理。
定理12.2
在高度为h的二叉查找树上,我们实现的动态集操作,INSERT,DELETE运行时间都是O(h)。
练习12.2
12.3-1 给出TREE-INSERT方法的递归版本。
12.3-2 假想我们反复向二叉树插入不同的元素来构建一棵二叉查找树。证明从中查找某一个结点所要检查结点的数量等于首次向树中插入该结点所要检查结点的数量加1.
12.3-3 我们可以通过构建二叉查找树(使用TREE-INSERT反复一个一个地插入数字)对给定有数字集合进行排序,然后中序打印遍历打印这些数字。对于这种排序算法它的最坏情况与最好情况的运行时间是多少?
12.3-4 对二叉查找树的删除先从二叉查找树中删除x再删除y和先从二叉树删除y再删除y的操作是可交换吗?证明是或者举出一个反例。
12.3-5 假设替换结点属性x.p成x.succ,x.p指向双亲结点,x.succ指向x的后继指点。使用这个属性给出二叉查找树T的SEARH,INSERT和DELETE操作的方法。在高为h二叉查找树中,这些方法运行时间是O(h)。(提示:你可以实现一个子方法返回双亲结点)。
12.3-6 在TREE-DELETE中删除结点z时,我们可以选择前驱结点y而不是后继结点。如果这样做TREE-DELETE要做哪些改变?有些人提出一个公平策略,前驱和后继具有相同的优先级,而获取更高的性能。如何修改TREE-DELETE实现这个公平策略。
全文下载:Chapter_12-Binary_Search_Trees