【数据结构】4. 树与二叉树(8)

构造一棵二叉排序树就是依次输入数据元素，并将它们插入到二叉排序树中的适当位置上的过程。
具体过程是，每读入一个元素，就建立一个新结点，若二叉排序树非空，则将新结点的值与根结点的值比较，
如果小于根结点的值，则插入到左子树中，否则插入到右子树中；若二叉排序树为空，则新结点作为二叉排序树的根结点。

void Creat_BST(BiTree ST,KeyType str[],int n) {
    //用关键字数组 str[] 建立一个二叉排序树
    T=NULL; //初始时 bt 为空树
    int i=0;
    while(i<n){ / /依次将每个元素插入
        BST_Insert(T,str[i]);
        i++;
    }
}

（5）二叉排序树的删除

在二叉排序树中删除一个结点时，不能把以该结点为根的子树上的结点都删除，
必须先把被删除结点从存储二叉排序树的链表上摘下，将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性质不会丢失。
删除操作的实现过程按 3 种情况来处理：

1. 如果被删除结点 z 是计结点，则直接删除，不会破坏二叉排序树的性质。
2. 若结点 z 只有一棵左子树或右子树，则让 z 的子树成为 z 父结点的子树，替代 z 的位置。
3. 若结点 z 有左、右两棵子树，则令 z 的直接后继（或直接前驱）替代 z,然后从二叉排序树中删去这个直接后继（或直接前驱），这样就转换成了第一或第二种情况。

如图 4-22 所示，在 3 种情况下分别删除结点 45、78、78。

思考：若在二叉排序树中删除并插入某结点，得到的二叉排序树是否和原来的相同？

（6）二叉排序树的査找效率分析

对于高度为 H 的二叉排序树，其插入和删除操作的运行时间都是 \(\mathcal{O}(H)\)。
但在最坏的情况下，即构造二叉排序树的输入序列是有序的，则会形成一个倾斜的单支树，此时二叉排序树的性能显著变坏，树的高度也增加为元素个数 N,如图 4-23 所示。
在等概率情况下，图 4-23(a) 的査找成功的平均査找长度为
\[ASL_a = (1+2x2+3x4+4x3)/10 = 2.9\]
而图 4-23(b) 的査找成功的平均査找长度为
\[ASL_b = (1+2+3+4+5+6+7+8+9+10)/10 = 5.5\]
由上可知，二叉排序树査找算法的平均査找长度，主要取决于树的高度，即与二叉树的形态有关。
如果二叉排序树是一个只有右（左）孩子的单支树（类似于有序的单链表），其平均査找长度和单链表相同，为 \(\mathcal{O}(n)\)。
如果二叉排序树的左、右子树的高度之差的绝对值不超过 1，这样的二叉排序树称为平衡二叉树，它的平均査找长度达到 \(\mathcal{O}(\log_2 n)\)。

从査找过程看，二叉排序树与二分査找相似。
就平均时间性能而言，二叉排序树上的査找和二分査找差不多。
但二分査找的判定树唯一，而二叉排序树不唯一，相同的关键字其插入顺序不同可能生成不同的二叉排序树，如图 4-23 所示。

就维护表的有序性而言，二叉排序树无须移动结点，只需修改指针即可完成插入和删除操作，平均执行时间为 \(\mathcal{O}(\log_2 n)\)。
二分査找的对象是有序顺序表，若有插入和删除结点的操作，所花的代价是 \(\mathcal{O}(n)\)。
当有序表是静态査找表时，宜用顺序表作为其存储结构，而采用二分査找实现其査找操作；若有序表是动态査找表，则应选择二叉排序树作为其逻辑结构。

4.5.2 平衡二叉树（Balanced Binary Tree）

（1）平衡二又树的定义

为了避免树的高度增长过快，降低二叉排序树的性能，我们规定
在插入和删除二叉树结点时，要保证任意结点的左、右子树高度差的绝对值不超过 1，将这样的二叉树称为平衡二叉树，简称平衡树（AVL 树）。
定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是-1、0 或 1。

因此，平衡二叉树可定义为它或者是一棵空树，或者是具有下列性质的二叉树：
它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度差的绝对值不超过 1。
如图 4-24(a) 所示是平衡二叉树，图 4-24(b) 所示是不平衡的二叉树。
结点中的值为该结点的平衡因子。

（2）平衡二叉树的插入

二叉排序树保证平衡的基本思想：每当在二叉排序树中插入（或删除）一个结点时，首先要检査其插入路径上的结点是否因为此次操作而导致了不平衡。
如果导致了不平衡. 则先找到插入路径上离插入结点最近的平衡因子绝对值大于 1 的结点 A，再对以 A 为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡。

注意：
每次调整的对象都是最小不平衡子树，即在插入路径上离插入结点最近的平衡因子的绝对值大于 1 的结点作为根的子树。如图 4-25 所示虚线框内为最小不平衡子树。

平衡二叉树的插入过程前半部分与二叉排序树相同，但是在新结点插入后，如果造成了査找路径上某个结点不再平衡，需要做出相应的调整。
一般可将失去平衡后进行调整的规律归纳为下列 4 种情况：

1. （编辑：ASP站长网）