|
|
|
动态查找也称树表查找，可执行动态查找的数据结构有二叉排序树、B-树和B+树等。动态查找表的特点是：表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在其关键字等于key的记录，则在查找成功后返回，否则插入关键字等于key的记录。考生重点掌握二叉排序树，因此这里主要介绍二叉排序树。
|
|
|
|
二叉排序树（简称BST）或者是一棵空树，或者是具有下列性质的二叉树。
|
|
|
|
.若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值。
|
|
|
|
.若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
|
|
|
|
|
|
从BST的性质可推出二叉排序树的另一个重要性质：按中序遍历该树所得到的中序序列是一个递增有序序列。
|
|
|
|
二叉排序树的查找方法：类似于折半查找，当二叉排序树不空时，首先将给定值k与根结点的关键字进行比较，若相等则查找成功；否则依k的大小在左子树或右子树上查找。可见，二叉排序树的查找是一个递归过程。
|
|
|
|
二叉排序树的构造：二叉排序树由依次输入的数据元素的序列构造而成。每读入一个元素，建立一个新的结点，并按下列原则插入结点。
|
|
|
|
.若二叉排序树为空树，则新结点为二叉排序树的根结点。
|
|
|
|
.若二叉排序树非空，则新结点的值与根结点比较，若小于根结点，则插入到左子树；否则插入到右子树。
|
|
|
|
|
|
.若删除的结点为*p，其双亲为*f，如果*p没有左右孩子，则可直接删除*p，修改*f的指针即可。
|
|
|
|
.若*p结点只有左子树或只有右子树，此时只要令其左子树或右子树直接成为其双亲结点*p的左子树即可。
|
|
|
|
.若*p结点的左子树和右子树均不空，如果希望中序遍历该二叉树得到的序列的相对位置在删除结点前后不变，则可采用如下方法：其一，令*p的左子树为*f的左子树，而*p的右子树为*s的右子树。其中*s为*p左子树中最右边的一个结点。其二，令*p的直接前驱（或直接后继）替代*p，然后再从二叉排序树中删除它的直接前驱（或直接后继）。这两种删除方法都能使原二叉排序树的中序遍历结果中结点的先后次序保持不变。
|
|
|
|
就平均时间性能而言，二叉排序树上的查找和折半查找相似。但就维护表的有序性而言，前者更有效，因为无须移动记录，只需修改指针即可完成对二叉排序树的插入和删除操作，而且其平均的执行时间均为O(log2n)。
|
|
|
|
有关平衡二叉树、B-树和B+树的知识，考生可参考相关参考文献。
|
|
|
