数据结构之查找(五)——二叉排序树

当表插入、删除操作频繁时，为了维护表的有序性，需要移动表中的很多记录。
所以改用动态查找表——几种特殊的树。其表结构在查找的过程中动态生成。

对于给定的key，若表中存在，则成功返回；否则，插入关键字等于key的记录。
这样的动态查找表有：二叉排序树，平衡二叉树，红黑树，B-树，B+树以及键树等。

二叉排序树的定义

• 定义：
  二叉排序树或是空树，或是满足如下性质的二叉树：

  • 若其左子树非空，则左子树上所有结点的值均小于根结点的值；
  • 若其右子树非空，则右子树上所有结点的值均大于等于根结点的值；
  • 其左右子树本身又各是一棵二叉排序树。

• 例子：
  

• 性质： 中序遍历非空的二叉排序树所得到的数据元素序列是一个按关键字排列的递增有序序列。
  
  上述二叉排序树的中序序列为：3，12，24，37，45，53，61，78，90，100。很明显，该序列是一个递增序列。

二叉排序树的查找算法

• 查找步骤：
  • 若查找的关键字等于根结点，成功
  • 否则
    • 若小于根结点，查其左子树
    • 若大于根结点，查其右子树
  • 在左右子树上的操作类似
• 二叉排序树的存储结构——二叉链表

typedef struct
{
	KeyType key;           //关键字项
	InfoType otherinfo;    //其他数据项
}ElemType;                 //数据元素类型定义

typedef struct BSTNode
{
	ElemType data;                      //数据域
	struct BSTNode *lchild, *rchild;    //指针域
}BSTNode,*BSTree;                       //树类型定义

BSTree T;              //定义二叉排序树T

• 递归查找的算法思想：

  • 若二叉排序树为空，则查找失败，返回空指针。
  • 若二叉排序树非空，将给定值key与根结点的关键字T->data.key 进行比较;
    • 若key==T->data.key ，则查找成功，返回根结点地址；
    • 若key<T->data.key，则进一步查找左子树；
    • 若key>T->data.key，则进一步查找右子树；

• 算法描述：

BSTree SearchBST(BSTree T, KeyType key)
{
	if ((!T) || key == T->data.key)
		return T;             //返回类型为指向结点的指针型
	else if (key < T->data.key)
		return SearchBST(T->lchild, key); //在左子树中继续查找
	else
		return SearchBST(T->rchild, key); //在右子树中继续查找
}

• 性能分析：
  二叉排序树查找某关键字等于给定值的结点过程，其实就是走了一条从根到该结点的路径。
  
  所以，比较的关键次数=此结点所在层次数。最多的比较次数=树的深度。
  
  二叉排序树的ASL计算：
  例子：(12，24，37，45，53，93)
  对于该序列，可构造如下图的二叉排序树，
  
  $$ASL=\frac{1}{6}(1+2+2+3+3+3)=\frac{14}{6}$$
  同时，也可构造如下图的二叉排序树，
  
  $$ASL=\frac{1}{6}(1+2+3+4+5+6)=\frac{21}{6}$$

所以，ASL与树的高度有关系，树的高度越高，其平均查找长度就越长。
含有n个结点的二叉排序树的平均查找长度和树的形态有关。
最好情况：初始序列{45，24，53，12，37，93}，$ASL={\log }_2^{(n+1)}-1$；树的深度为：$\lfloor {\log }_2^n\rfloor +1$；与折半查找中的判定树相同(形态比较均衡)，时间复杂度为$O({\log }_2^n)$。
最坏情况：初始序列{12，24，37，45，53，93}，插入的n个元素一开始就有序——变成单支树的形态。树的深度为：$n,ASL=\frac{n+1}{2}$；查找效率与顺序查找情况相同，时间复杂度为$O(n)$。

• 如何提高形态不均衡的二叉排序树的查找效率？
  方法：做“平衡化”处理，即尽量让二叉树的形状均衡——平衡二叉树。

二叉排序树的插入操作

• 例子：在如下的二叉排序树中插入值为40和50的元素。
  
  插入值为40的元素，是37的右孩子，黄色部分为路径，
  
  插入值为50的元素，是53的左孩子，右边黄色所示的是路径，
  
• 插入步骤：
  • 若二叉排序树为空，则插入结点作为根结点插入到空树中。
  • 否则，继续在其左右子树上查找
    • 树中已有，不再插入
    • 树中没有
      • 查找直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子。

插入的元素一定在叶结点上。

二叉排序树的生成操作

• 从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树。例子如下，
  
• 一个无序序列可通过构造二叉排序树而变成一个有序序列。构造树的过程就是对无序序列进行排序的过程。
• 插入的结点均为叶子结点，故无需移动其他结点。相当于在有序序列上插入记录而无需移动其他记录。
• 但是，关键字的输入顺序不同，建立的二叉排序树也是不同的。例子如下，
  

二叉排序树的删除操作

• 从二叉排序树中删除一个结点，不能把以该结点为根的子树都删去，只能删掉该结点，并且还应保证删除后所得到的二叉树仍然满足二叉排序树的性质不变。

• 由于中序遍历二叉排序树可以得到一个递增有序的序列。那么，在二叉排序树种删去一个结点相当于删去有序序列中的一个结点。

  • 将因删除结点而断开的二叉链表重新链接起来
  • 防止重新链接后树的高度增加

• 下面分几种情况具体讨论：

  • 被删除的是叶子结点：直接删去该结点。
    
    
    直接修改双亲结点，将双亲结点中相应的指针域的值改为“空”。
  • 被删除的结点只有左子树或者只有右子树，用其左子树或者右子树替换它(结点替换)。
    
    
    其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树”。
  • 被删除的结点既有左子树，也有右子树。
    
    
    以其中序前驱值替换之(值替换)，然后再删除该前驱结点。前驱结点是左子树中最大的结点。
    也可以用其后继替换之，然后再删除该后继结点。后继是右子树中最小的结点。

• 几个例子：