6.5 二叉排序树★3◎4

6.5 二叉排序树★3◎4

　　1．二叉排序树定义
　　二叉排序树（Binary Sort Tree）或者是一棵空树；或者是具有下列性质的二叉树：
　　（1）若左子树不空，则左子树上所有结点的值均小于根结点的值；若右子树不空，则右子树上所有结点的值均大于根结点的值。
　　（2）左右子树也都是二叉排序树，如图6-2所示。

　　2．二叉排序树的查找过程
　　由其定义可见，二叉排序树的查找过程为：
　　（1）若查找树为空，查找失败。
　　（2）查找树非空，将给定值key与查找树的根结点关键码比较。
　　（3）若相等，查找成功，结束查找过程，否则：
　　① 当给值key小于根结点关键码，查找将在以左孩子为根的子树上继续进行，转（1）。
　　② 当给值key大于根结点关键码，查找将在以右孩子为根的子树上继续进行，转（1）。
　　3．二叉排序树插入操作和构造一棵二叉排序树
　　向二叉排序树中插入一个结点的过程：设待插入结点的关键码为key，为将其插入，先要在二叉排序树中进行查找，若查找成功，按二叉排序树定义，该插入结点已存在，不用插入；查找不成功时，则插入之。因此，新插入结点一定是作为叶子结点添加上去的。构造一棵二叉排序树则是逐个插入结点的过程。对于关键码序列为：｛63，90，70，55，67，42，98，83，10，45，58｝，则构造一棵二叉排序树的过程如图6-3所示。
　　4．二叉排序树删除操作
　　从二叉排序树中删除一个结点之后，要求其仍能保持二叉排序树的特性。
　　设待删结点为*p（p为指向待删结点的指针），其双亲结点为*f，删除可以分三种情况，如图6-4所示。

　　（1）*p结点为叶结点，由于删去叶结点后不影响整棵树的特性，所以，只需将被删结点的双亲结点相应指针域改为空指针，如图6-4（a）所示。
　　（2）*p结点只有右子树或只有左子树，此时，只需将或替换*f结点的*p子树即可，如图6-4（b）、（c）所示。
　　（3）*p结点既有左子树又有右子树，可按中序遍历保持有序地进行调整，如图6-4（d）、（e）所示。

　　设删除*p结点前，中序遍历序列为：
　　① P为F的左子女时有：…，Pi子树，P，Pj，S子树，Pk，Sk子树，…，P2，S2子树，P1，S1子树，F，…。
　　② P为F的右子女时有：…，F，Pi子树，P，Pj，S子树，Pk，Sk子树，…，P2，S2子树，P1，S1子树，…。
　　则删除*p结点后，中序遍历序列应为：
　　① P为F的左子女时有：…，Pi子树，Pj，S子树，Pk，Sk子树，…，P2，S2子树，P1，S1子树，F，…。
　　② P为F的右子女时有：…，F，Pi子树，Pj，S子树，Pk，Sk子树，…，P2，S2子树，P1，S1子树，…。
　　有两种调整方法：
　　① 直接令Pi为*f相应的子树，以Pr为Pi中序遍历的最后一个结点Pk的右子树。
　　② 令*p结点的直接前驱Pr或直接后继（对Pi子树中序遍历的最后一个结点Pk）替换*p结点，再按（2）的方法删去Pr或Pk。
　　【算法分析】
　　对给定序列建立二叉排序树，若左右子树均匀分布，则其查找过程类似于有序表的折半查找。但若给定序列原本有序，则建立的二叉排序树就蜕化为单链表，其查找效率和顺序查找一样。因此，对均匀的二叉排序树进行插入或删除结点后，应进行调整，使其依然保持均匀。