第8章搜索（3）-动态表搜索的二叉排序树

动态表格查询

动态查找表的特征是: 表结构本身是在查找过程中动态生成的，也就是说，对于给定值的键，如果存在键值等于表中键的记录，搜索将成功返回；否则，将插入键值等于键的记录. 动态查找表可以具有不同的表示方法. 本节仅讨论以各种树形结构表示的实现方法.

二进制排序树

在序列表的三种搜索方法中，二进制搜索具有最高的搜索效率. 但是，由于二进制搜索需要使用关键字对表中的记录进行排序，并且不能将链接列表用作存储结构，因此在插入表时，当删除操作非常频繁时，为了保持表的顺序，表中的许多记录需要移动. 由移动记录引起的额外时间开销将抵消二进制搜索的优势. 本节讨论的二进制排序树不仅具有二进制搜索的效率，而且还有助于查找表中记录的添加和删除.

①二进制排序树的定义

二进制排序树是具有以下属性的空树或二进制树:

如果左子树不为空，则左子树上所有节点的值小于根节点的值.

如果右子树不为空，则右子树上所有节点的值都大于根节点的值.

它的左和右子树也是二进制排序树.

例如，图是二进制排序树. 可以看出，二叉树的中间顺序遍历将导致记录序列按键排序.

二进制排序树的类结构定义如下:

向左或向右滑动或单击以查看完整图像

②二叉树的搜索过程

如果将查找表组织为二进制排序树，则根据二进制排序树的特征，搜索过程的主要步骤总结如下:

（1）如果搜索树为空，则搜索失败.

（2）如果搜索树不为空，则:

①如果给定值k等于根节点的键值，则搜索成功并且搜索过程结束，否则转到②.

②如果给定值k小于根节点的键值，则在根节点的左子树上继续，否则转到③.

③如果给定值k大于根节点的键值，则继续在根节点的右子树上进行.

以下内容使用二进制链接列表作为二进制排序树的存储结构. 假设当前二进制排序树的根节点为root，并且要搜索的记录的键值为key，则二进制排序树的搜索算法如下:

向左或向右滑动或单击以查看完整图像

③二进制排序树的插入操作

首先讨论将新节点插入二进制排序树的过程: 假设要插入的节点的键值为key，为了将其插入表中二叉排序树查找 算法，首先将其放入二进制排序树中. 搜索被执行. 如果搜索成功，则将其定义为二进制排序树. 要插入的节点已经存在，不需要插入. 否则，将新节点插入到表中. 因此，必须将新插入的节点作为叶节点添加到表中.

在二进制排序树中插入新节点的算法如下:

向左或向右滑动或单击以查看完整图像

构造二进制排序树是从空树开始一个接一个地插入节点的过程. 假设键序列为{49，25，55，10，51，65}，下图显示了构建二进制排序树的过程.

④删除二进制排序树

以下内容讨论如何从二进制排序树中删除节点. 在二进制排序树上进行插入操作的要求是相同的. 要从二进制排序树中删除节点，请确保删除后该节点仍然是二进制排序树. 根据二叉树的结构特点，可以考虑四种情况下的删除操作.

（1）如果要删除的节点是叶节点，则直接删除该节点. 如果该节点也是根节点，则二进制排序树在删除后将变为空树，如下图（a）所示.

（2）如果要删除的节点仅具有左子树，而没有右子树. 根据二进制排序树的特性，其左子树的根节点可以直接替换已删除节点的位置，即，如果已删除节点是父节点的左子节点，则删除节点的唯一左子节点是父节点的左子节点；否则，它是父节点的右子节点，如下图（b）所示.

（3）要删除的节点仅具有右子树，而没有左子树. 与情况（2）相似，其右子树的根节点可以直接替换已删除节点的位置，即，如果已删除节点是其父节点的左子节点，则该已删除节点中只有一个将右孩子视为父节点的左孩子；否则，该右子将被视为父节点的右子，如下图（c）所示.

（4）要删除的节点同时具有左子树和右子树. 根据二元排序树的特性，可以使用中级遍历序列下的删除节点的前任节点（或中级遍历序列下的后继节点）替换已删除的节点，并使用中间节点可以同时删除顺序遍历序列. 前任节点（或顺序遍历序列下的后继节点）. 有序遍历下已删除节点的前任没有右子树，有序遍历下已删除节点的后继没有左子树，因此问题被转换为（2）或（3）情况. 下图（d）所示的示例是在已删除节点（即，右子树中的左下节点）的有序遍历序列下，用后继节点替换已删除节点.

总而言之，假设要删除的节点的键值为key. 如果删除成功，将返回删除的节点. 否则，将返回null. 二进制排序树的节点删除算法描述如下:

向左或向右滑动或单击以查看完整图像

二元排序树的节点删除操作的主要时间成本是在删除节点的有序遍历下查找删除的节点和后续节点，并且此操作的时间成本与树的深度相关. 因此，删除操作的平均时间也是O（log2n）.

[Programming]二进制排序树算法测试程序.

[问题描述]假设每个姓氏都有一个对应的代码，下表显示了10个姓氏及其对应的代码.

尝试根据上表中的数据设计基于二进制排序树的测试程序二叉排序树查找 算法，并且需要执行以下操作:

上表中的代码为关键字创建了一个二进制排序树.

以中阶遍历的形式显示二进制排序树.

查找分别对应于关键字值63和39的姓氏.

删除键值为13的节点.

[问题分析]本章定义的二进制排序树的节点的数据字段类型为RecordNode，RecordNode类的数据成员为键和元素，其对应的数据类型分别为Comparable和Object. 根据此问题的含义，需要定义两个类KeyType和ElemenyType分别存储代码和姓氏，并且KeyType类需要实现Comparable接口，以便根据键值比较大小. 有关RecordNode，KeyType和ElemenyType的定义，请参阅第7（1）章中的内容. 此外，还需要设计一个测试类Example9_2来调用二进制排序树的插入，查询和删除算法.

[程序代码]

[实验结果]

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-285097-1.html