1. 激活谷首页
  2. 激活谷笔记

搜索二叉树的查找原理_二叉查找树和二叉排序树

• 激活谷笔记

搜索二叉树的查找原理_二叉查找树和二叉排序树算法导论（第四版）第十二章：二叉搜索树　第三节：插入和删除12.3 插入和删除(Insertion and deletion)插入和删除操作会引起二叉搜索树表示的动态集合的变化，但是二叉搜索树的性质保持不变。插入(Insertion)向二叉搜索树 中插入结点 ，其关键字为 ，

算法导论（第四版）第十二章：二叉搜索树　第三节：插入和删除 　　12.3 插入和删除(Insertion and deletion) 　　插入和删除操作会引起二叉搜索树表示的动态集合的变化，但是二叉搜索树的性质保持不变。 　　插入(Insertion) 　　
搜索二叉树的查找原理_二叉查找树和二叉排序树
搜索二叉树的查找原理_二叉查找树和二叉排序树 　　向二叉搜索树
T 中插入结点
z ，其关键字为
z.key ，伪代码TREE-INSERT如下： 　　该过程保持跟踪指针(trailing pointer)
y 记录
x 的父结点。 　　TREE-INSERT的运行时间为
O(h)，其中
h为树的高度。 　　删除(Deletion) 　　
搜索二叉树的查找原理_二叉查找树和二叉排序树
搜索二叉树的查找原理_二叉查找树和二叉排序树 　　从二叉搜索树
T 中删除结点
z 分三种情况：情况一：如果
z 没有孩子结点，直接删除，
z 的父结点指向
z 的指针置为NIL。情况二：如果
z 只有一个孩子结点，将这个孩子结点提升到
z 的位置，
z 的父结点指向
z 的指针改为指向这个孩子结点。情况三：如果
z 有两个孩子结点，找出
z 的后继
y ，让
y 占据
z 的位置，
z 的右子树变为
y 的右子树，
z 的左子树变为
y 的左子树。由于
y 是
z 的后继，所以
y 不可能有左孩子。如果
y 是
z 的右孩子，用
y 替换
z 。如果
y 在
z 的右子树中且
y 不是
z 的右孩子，先用
y 的右孩子结点替换
y ，然后用
y 替换
z 。 　　子程序TRANSPLANT实现了用某子树原先父结点的指向该子树的指针指向另一棵子树，实现了子树的替换。伪代码如下： 　　伪代码TREE-DELETE如下： 　　TREE-DELETE的运行时间为
O(h)，其中
h为树的高度。 　　我们可以总结出如下定理。 　　定理12.3 (Theorem 12.3) 　　在一棵高度为
h 的二叉搜索树上，INSERT和DELETE的运行时间为
O(h) 。 　　练习题(Exercises) 　　12.3-1 　　写出TREE-INSERT的递归版。 　　解答： 　　对应第三版练习题12.3-1。 　　12.3-2 　　假设采用反复向二叉搜索树中插入互不相同的关键字的方式构建二叉搜索树，证明：在这棵二叉树中查找关键字所检查的结点数等于先前插入这个关键字所检查的结点数加一。 　　解答： 　　对应第三版练习题12.3-2。 　　比较TREE-INSERT和ITERATIVE-TREE-SEARCH的伪代码，两者检查的路径完全相同，因为必须遵循二叉搜索树性质，最后需要检查被插入关键字，需要加一，所以在这棵二叉树中查找关键字所检查的结点数等于先前插入这个关键字所检查的结点数加一，得证。 　　12.3-3 　　你可以用构建二叉搜索树的方式对
n 个数进行排序。采用反复向二叉搜索树中插入关键字的方式构建二叉搜索树。然后用中序遍历输出所有数。这个排序算法最坏情况下和最好情况下运行时间分别是多少。 　　解答： 　　对应第三版练习题12.3-3。 　　最坏情况下插入序列已经有序，如果所有素均不相同会形成一条链表，运行时间为
\Theta(n^2) 。 　　最好情况下插入序列式是一个均匀随机排列，最后二叉树左右平衡，每次插入运行时间不会超过树高
h =
O(\lg n) ，即
O(\lg n) ，总计
n 个素，运行时间
O(n\lg n) ，又由于插入操作是基于比较，根据定8.1，最坏情况下，任何比较排序算法都需要
\Omega(n\lg n) 次比较。根据定理3.1，运行时间为
\Theta(n\lg n) 。 　　12.3-4 　　当TREE-DELETE调用TRANSPLANT时，在什么情况下TRANSPLANT中的参数
v 可以为NIL。 　　解答： 　　观察TREE-DELETE伪代码，有四处地方调用了TRANSPLANT，我们逐一分析。第一处：
v 为
z.right ，可以为NIL。第二处：
v 为
z.left ，不可能为NIL，否则会进入前一个判断分支。第三处：
v 为
y.right ，可以为NIL。第四处：
v 为
y ，不可能为NIL，因为
z 的右子树不为空，
y 是右子树关键字最小的结点，
y 一定不为NIL，否则会进入前面的判断分支。 　　12.3-5 　　删除操作可交换吗？可交换的含义是，先删除
x 再删除
y 留下的结果树与先删除
y 再删除
x 留下的结果树完全一样。如果是，说明为什么？否则，给出一个反例。 　　解答： 　　对应第三版练习题12.3-4。 　　反例如下： 　　先删除
A 再删除
B 。 　　先删除
B 再删除
A 。 　　12.3-6 　　假设为每个结点换一种设计，用属性
x.succ 指向
x 的后继替代属性
x.p 指向
x 的父结点。给出使用这种表示法的二叉搜索树
T 上的TREE-SEARCH、TREE-INSERT和TREE-DELETE的伪代码。这些伪代码运行时间为
O(h) ，其中
h 为树
T 的高度。（提示：设计一个返回某结点的父结点的子过程）。 　　解答： 　　对应第三版练习题12.3-5。 　　这里每个结点没有
p 指针，有
succ 指针。首先需要编写新的PARENT函数。 　　评：这道题难度非常大，需要运用二叉搜索树的性质将指针和结点重新关联。 　　12.3-7 　　当TREE-DELETE中的结点
z 有两个孩子时，应该选择结点
y 作为它的前驱，而不是作为它的后继。如果这样做，对TREE-DELETE应该做哪些什么必要的修改？一些人提出了一个公平的策略，为前驱和后继赋予相等的优先级，这样得到了较好的实验性能。如何对TREE-DELETE进行修改来实现这样一种公平策略？ 　　解答： 　　对应第三版练习题12.3-6。 　　即用前驱替换被删除结点，由于
y 是
z 的前驱，所以
y 不可能有左孩子。如果
y 是
z 的左孩子，用
y 替换
z 。如果
y 在
z 的左子树中且
y 不是
z 的左孩子，先用
y 的左孩子结点替换
y ，然后用
y 替换
z 。 　　修改伪代码TREE-DELETE如下： 　　为了使用公平策略，我们随机使用前驱或后继替换被删除结点。引入随机数
r 。当
r=0 时，使用前驱替换被删除结点。当
r=1 时，使用后继替换被删除结点。 　　评：这道题充分体现了算法思维的严谨性，由于某个结点的前驱和后继的地位是完全等同的，符合对称性，既然可以用前驱，也可以用后继。

2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/25362.html

赞 (0)
0
上一篇 2024年 9月 13日
下一篇 2024年 9月 13日

相关推荐

关注微信