动态查找表-二进制排序树（二进制搜索树）

1. 二进制排序树的定义

二进制排序树（Binary Sort Tree），也称为二进制搜索树（Binary Search Tree）. 它定义为: 二进制排序树或空树，或满足以下属性的二进制树:

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

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

③左右子树都是二叉排序树.

以上属性被称为二进制排序树属性（BST属性），因此二进制排序树实际上是满足BST属性的二进制树

2. 二进制排序树的存储结构

typedef int KeyType; //假设关键字类型是整数

typedef struct node {//节点类型

KeyType键； //关键字项

InfoType otherinfo; //其他数据字段，InfoType取决于应用程序，下面将不对其进行处理

结构节点* lchild，* rchild; //左右子指针

} BSTNode；

typedef BSTNode * BSTree; // BSTree是二进制排序树的类型

3. 二进制排序树上的操作

（1）将新节点插入二进制排序树的过程

在二进制排序树中插入一个新节点，以确保插入后仍满足BST属性. 插入过程为:

（a）如果二进制排序树T为空，请为要插入的密钥申请一个新节点并将其设为根；

（b）如果二进制排序树T不为空，则比较key和root关键字:

（i）如果两者相等，则意味着关键字key已存在于树中，无需插入.

（ii）如果键

（iii）如果键> T→键，则将其插入到根的右子树中.

子树中的插入过程与上面树中的插入过程相同. 执行此操作，直到将密钥作为新叶节点的密钥插入到二进制排序树中为止，或者直到在树中找到该密钥为止.

（2）生成二进制排序树

二进制排序树的生成从一个空的二进制排序树开始. 每次输入节点数据时，都会调用插入算法将其插入当前生成的二进制排序树中. 生成二进制排序树的算法如下:

BSTree CreateBST（无效）

{//输入节点序列，构建二进制排序树，并返回根节点指针

BSTree T = NULL; //初始T是一棵空树

KeyType键；

scanf（“％d”，＆键）; //阅读关键字

while（key）{//假设key = 0是输入结束符号

InsertBST（＆T，键）； //将密钥插入二进制排序树T

scanf（“％d”，＆键）; //阅读下一个关键字

}

返回T； //返回已建立的二进制排序树的根指针

} // BSTree

（3）二进制排序树的生成过程

从输入示例（5、3、7、2、4、8）中，根据生成二进制排序树的算法生成二进制排序树的过程[请参见演示]

注意:

输入序列确定二进制排序树的形状.

二进制排序树的中序序列是有序序列. 因此，要为任意键序列构建二进制排序树，本质是对键序列进行排序，使其成为有序序列. “排序树”的名称也由此得出. 这种排序通常称为树排序（Tree Sort），可以证明这种排序的平均执行时间也是O（nlgn）.

对于相同的输入实例，树排序的执行时间约为堆排序的2到3倍. 因此，通常，构造二进制排序树的目的不是排序，而是使用它来加快搜索速度. 这是因为在有序集合上进行搜索通常比在无序集合上进行搜索更快. 因此，人们经常将二进制排序树称为二进制搜索树.

（4）查找递归算法

在二元排序树上进行搜索与二元搜索相似，也是逐渐缩小搜索范围的过程.

递归搜索算法:

BSTNode * SearchBST（BSTree T，KeyType键）

{//找到其键是二进制排序树T上的键的节点，并在成功时返回节点位置，否则返回NUll

if（T == NULL ||键== T->键）//递归的结束条件

返回T； // T为空二叉排序树查找算法，搜索失败；否则，它将成功并返回找到的节点位置

如果（键键）

返回SearchBST（T-> lchild，密钥）；

其他

返回SearchBST（T-> rchild，键）； //继续在右边的子树中搜索

} // SearchBST

4. 算法分析

（1）在二叉排序树上搜索时，如果搜索成功，则将从根节点获取从根到要检查的节点的路径. 如果搜索不成功，则从根节点获取从根到叶的路径. 注意:

类似于二进制搜索，与关键字的比较次数不超过树的深度.

（2）在二叉排序树上搜索时的平均搜索长度与二叉树的形状有关

二进制搜索方法搜索长度为n的有序列表，并且其决策树是唯一的. 具有n个节点的二进制排序树不是唯一的. 对于具有相同节点集的表，由于节点的插入顺序不同，因此形成的二进制排序树的形式和深度也可能不同

【示例】以下（a）所示的树是按以下插入顺序构造的:

45、24、55、12、37、53、60、28、40、70

下面（b）所示的树是按以下插入顺序构造的:

12、24、28、37、40、45、53、55、60、70

在二叉排序树上搜索时的平均搜索长度与二叉树的形状有关:

①在最坏的情况下，通过顺序插入一个有序列表的n个节点来生成二进制排序树，然后将所得的二进制排序树转换为深度为n的单个分支树，其平均搜索长度与在单链列表上的顺序搜索，该列表也是（n +1）/ 2.

②在最佳情况下，在生成二进制排序树的过程中，树的形状相对对称，最终结果是一个二进制排序树，其形式类似于二进制搜索的决策树. 搜索长度约为lgn.

③插入，删除和搜索算法的时间复杂度均为O（lgn）.

（3）二进制排序树和二进制搜索的比较

就平均时间性能而言，对二进制排序树的搜索类似于对二进制搜索.

就维护表的顺序而言，二进制排序树不需要移动节点，只需修改指针即可完成插入和删除操作，平均执行时间为O（lgn）二叉排序树查找算法，这样更有效. 二进制搜索中涉及的有序表是一个向量. 如果有插入和删除节点的操作，则维护表顺序的成本为O（n）. 当有序表是静态查找表时，应将向量用作其存储结构，并使用二进制搜索来实现其搜索操作. 如果动态查找表位于有序表中，则应选择二进制排序树作为其存储结构.

（4）平衡二叉树

为了确保二进制排序树的高度为lgn，以确保对二进制排序树执行的插入，删除和搜索基本操作的平均时间为O（lgn），或删除树中的节点当时，应调整树的形状以保持树的“平衡”. 应该保持BST属性不变，并确保树的高度在任何情况下均为O（lgn），从而确保在最坏的情况下，树的基本操作都为O（lgn）.

注意:

①平衡二叉树（Balanced Binary Tree）是指该树中任何节点的左右子树具有大约相同的高度.

②任何节点的左右子树的高度相同（例如完整的二叉树），则二叉树完全平衡. 通常，只要二叉树的高度为O（1gn），就可以认为它是平衡的.

③平衡二叉树是指满足BST特性的平衡二叉树.

④AVL树中任何节点的左右子树之间的高度差的绝对值不超过1. 在最坏的情况下，具有n个节点的AVL树的高度约为1.44lgn. 虽然完全平衡的二叉树的程度约为lgn，但AVL树已接近最佳.

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