| 二叉查找树、B-树、红黑树等是常见的以树表方式组织的查找表。
|
|
|
|
|
| 二叉查找树是一种动态查找表，其特点是表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。
|
|
|
| 根据定义，非空的二叉查找树中左子树上所有结点的关键字均小于根结点的关键字，右子树上所有结点的关键字均大于根结点的关键字，因此，可将二叉查找树看成是一个有序表，其查找过程与折半查找过程相似。
|
|
|
| 在二叉查找树上进行查找的过程为：若二叉查找树非空，将给定值与根结点的关键字值相比较，若相等，则查找成功；若不等，则当根结点的关键字值大于给定值时，到根的左子树中进行查找，否则到根的右子树中进行查找。若找到，则查找过程是走了一条从树根到所找到结点的路径；否则，查找过程终止于一棵空树。
|
|
|
| 设二叉查找树以二叉链表为存储结构，结点的类型定义如下：
|
|
|
|
|
|
|
|
|
|
|
| 二叉查找树是通过依次输入数据元素并把它们插入到二叉树的适当位置上构造起来的，即每读入一个元素，首先在二叉查找树中进行查找，若找到则不再插入，否则根据查找时得到的位置信息进行插入。其过程为：若二叉查找树为空，则为新元素创建结点并作为二叉查找树的根结点；若二叉查找树非空，则将新元素的值与根结点的值相比较，如果小于根结点的值，则继续在左子树中查找，否则在右子树中继续查找，直到某结点的值与新元素的值相等，或者到达空的子树为止，此时创建新元素的结点并替换该空的子树完成插入处理。设关键字序列为｛46，25，54，13，29，91｝，则对应的二叉查找树构造过程如下图（a）~（g）所示。
|
|
|
|
|
|
|
| 从上面的插入过程还可以看到，每次插入的新结点都是二叉查找树上新的叶子结点，因此在进行插入操作时，不必移动其他结点，仅需改动某个结点的指针域，由空变为非空即可。这就相当于在一个有序序列上插入一个记录而不需要移动其他记录。
|
|
|
| 另外，由于一棵二叉查找树的形态完全由输入序列决定，所以在输入序列已经有序的情况下，所构造的二叉查找树是一棵单枝树。从二叉查找树的查找过程可知，这种情况下的查找效率与顺序查找的效率相当。
|
|
|
|
|
| 一棵m阶的B_树，或为空树，或为满足下列特性的m叉树。
|
|
|
|
|
|
|
（3）除根之外的所有非终端结点最少有 棵子树。
|
|
|
|
|
| （n，A0，K1，A1，K2，A2，…，Kn，An）
|
|
|
其中，Ki（i=1，2，…，n）为关键字，且Ki<Ki+1（i=1，2，…，n-1）；Ai（i=0，1，…，n）为指向子树根结点的指针，且指针Ai-1所指子树中所有结点的关键字均小于Ki（i=1，2，…，n），An所指子树中所有结点的关键字均大于Kn，n为结点中关键字的个数且满足 。
|
|
|
| （5）所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。
|
|
|
|
|
|
|
|
|
| 由B_树的定义可知，在B_树上进行查找的过程是：首先在根结点所包含的关键字中查找给定的关键字，若找到则成功返回；否则确定待查找的关键字所在的子树并继续进行查找，直到查找成功或查找失败（指针为空）时为止。
|
|
|
B_树上的插入和删除运算较为复杂，因为要保证运算后结点中关键字的个数大于等于 ，因此涉及结点的“分裂”及“合并”问题。
|
|
|
| 在B_树中插入一个关键字时，不是在树中增加一个叶子结点，而是首先在低层的某个非终端结点中添加一个关键字，若该结点中关键字的个数不超过m-1，则完成插入；否则，要进行结点的“分裂”处理。所谓“分裂”，就是把结点中处于中间位置上的关键字取出来插入到其父结点中，并以该关键字为分界线，把原结点分成两个结点。“分裂”过程可能会一直持续到树根。
|
|
|
同样，在B_树中删除一个结点时，首先找到关键字所在的结点，若该结点在含有信息的最后一层，且其中关键字的数目不少于 ，则完成删除；否则需进行结点的“合并”运算。
|
|
|
| 若待删除的关键字所在的结点不在含有信息的最后一层，则将该关键字用其在B_树中的后继替代，然后删除其后继元素，即将需要处理的情况统一转化为在含有信息的最后一层再进行删除运算。
|
|
|
