[数据结构与算法]算法-查找算法-树表的查找（二叉排序树、平衡二叉树）（类C语言版）

几种特殊的树

当表插入、删除操作频繁时，为维护表的有序性，需要移动表中很多记录。
改用动态查找表——几种特殊的树，表结构在查找过程中动态生成。
对于给定值key，若表中存在，则成功返回；否则，插入关键字等于key的记录。

几种特殊的树：

• 二叉排序树
• 平衡二叉树
• 红黑树
• B-树
• B+树
• 键树

二叉排序树

二叉排序树定义

二叉排序树（Binary Sort Tree）又称为二叉搜索树、二叉查找树，它是一种对排序和查找都很有用的特殊二叉树。
二叉排序树或是空树，或是满足如下性质的二叉树：
（1）若其左子树非空，则左子树上所有结点的值均小于根节点的值；
（2）若其右子树非空，则右子树上所有结点的值均大于等于根节点的值；
（3）其左右子树本身又各是一棵二叉排序树。

二叉排序树实例

若中序遍历图(a)，则可得到一个按数值大小排序的递增序列：
3, 12, 24, 37, 45, 53, 61, 78, 90, 100
若中序遍历图(b)，则可得到一个按字符大小排序的递增序列：
CAO, CHEN, DING, DU, LI, MA, WANG, XIA，ZHAO

可以得出二叉排序树的性质：中序遍历非空的二叉排序树所得到的数据元素序列是一个按关键字排列的递增有序序列。

二叉排序树的操作-查找思想

• 若查找的关键字等于根节点，成功
• 否则
  • 若小于根节点，查其左子树
  • 若大于根节点，查其右子树
• 在左右子树上的操作类似。

二叉排序树的二叉链表存储表示

// - - - - -二叉排序树的二叉链表存储表示－－－－－
typedef struct 
{
	KeyType key; 					// 关键字项
	InfoType otherinfo; 			// 其他数据项
}ElemType; 							// 每个结点的数据域的类型

typedef struct BSTNode 
{
	ElemType data; 					// 每个结点的数据域包括关键字项和其他数据项
	struct BSTNode *lchild,*rchild; // 左右孩子指针
}BSTNode,*BSTree; 

二叉排序树的递归查找

算法思想

（1）若二叉排序树为空，则查找失败，返回空指针。
（2）若二叉排序树非空，将给定值key与根节点的关键字T->data.key进行比较：
① 若key等于T->data.key，则查找成功，返回根节点地址；
② 若key小于T->data.key，则进一步查找左子树；
③ 若key大于T->data.key，则进一步查找右子树。

算法描述

BSTree SearchBST (BSTree T, KeyType key)
{	//在根指针T所指二叉排序树中递归地查找某关键字等于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); 						// 在右子树中继续查找
}

二叉排序树的查找分析

二叉排序树上查找某关键字等于给定值的结点过程，其实就是走了一条从根到该结点的路径。
比较的关键字次数 = 此结点所在层次数。
最多的比较次数 = 树的深度。

二叉排序树的平均查找长度

含有n个结点的二叉排序树的平均查找长度和树的形态有关。

最好情况：初始序列{45, 24, 53, 12, 37, 93} ，ASL =log₂(n+1) -1；树的深度为log₂n+1；与折半查找中的判定树相同。（形态比较均衡）：O(log₂n)

最坏情况：初始序列{12, 24, 37, 45, 53, 93}，插入的n个元素从一开始就有序，编程单支树的形态！此时树的深度为n，ASL=(n+1) / 2，查找效率与顺序查找情况相同：O(n)。

那么问题来了：如何提高形态不均衡的二叉排序树的查找效率？
解决办法：做“平衡化”处理，即尽量让二叉树的形态均衡！ —— 平衡二叉树

二叉排序树的操作-插入

• 若二叉排序树为空，则插入结点作为根节点插入到空树中；
• 否则，继续在其左、右子树上查找；
  • 树中已有，不再插入，
  • 树中没有
    • 查找直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子。

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

void InsertBST(BSTree &T,ElemType e} 
{	// 当二叉排序树 T中不存在关键字等千e.key的数据元素时， 则插入该元素
	if (!T)
	{								// 找到插入位置 ， 递归结束	
		S=new BSTNode; 				// 生成新结点*S
		S->data=e; 					// 新结点*S的数据域置为e
		S->lchild=S->rchild=NULL; 	// 新结点*S作为叶子结点
		T=S; 						// 把新结点*S链接到已找到的插入位置
	}
	else if (e.key<T->data.key) 
		InsertBST(T->lchild, e ); 	// 将*S插入左子树
	else if (e.key> T->data.key)
		InsertBST(T->rchild, e); 	// 将*S插入右子树
}

二叉排序树插入的基本过程是查找，所以时间复杂度同查找一样，是 O(log₂n）。

二叉排序树的操作-生成

从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树。

一个无序序列可通过构造二叉排序树而变成一个有序序列。构造树的过程就是对无序序列进行排序的过程。

插入的结点均为叶子结点，故无需移动其他结点。相当于在有序序列上插入记录而无需移动其他记录。

但是：关键字的输入顺序不同，会建立不同二叉排序树。

void CreatBST(BSTree &T) 
{	//依次读人一个关键字为key的结点， 将此结点插人二叉排序树T中
	T=NULL; 					//将二叉排序树T初始化为空树
	cin>>e; 
	while(e.key!=ENDFLAG) 		// ENDFLAG为自定义常址，作为输入结束标志
	{
		InsertBST(T,e); 			// 将此结点插入二叉排序树T中
		cin>>e; 
	}
}

设关键字的输入次序为： 45,24,53,45, 12,24,90, 按上述算法生成的二叉排序树的过程如图 所示。

但是如果打乱顺序，生成的二叉排序树就会有很大差别。

二叉排序树的操作-删除

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

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

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

（1）被删除的结点是叶子结点：直接删去该结点。

（2）被删除的结点只有左子树或者右子树，用其左子树或者右子树替换它（结点替换）。

其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树”。
（3）被删除的结点既有左子树，也有右子树

• 以其中序前驱值替换之（值替换），然后再删除该前趋结点。前趋是左子树中最大的结点。
• 也可以用其后继替换之，然后再删除该后继结点。后继是右子树中最小的结点。
  

void DeleteBST(BSTree &T,KeyType key)
{	// 从二叉排序树 T 中删除关键字等千 key 的结点
	p=T;f=NULL; 							// 初始化
	/*------------下面的 while 循环从根开始查找关键字等于 key 的结点*p---------------*/
	while (p) 
	{
		if(p->data.key==key) break; 		// 找到关键字等于 key 的结点*p, 结束循环
		f=p; 								// *f 为*p 的双亲结点
		if(p->data.key>key) p=p->lchild; 	// 在*p 的左子树中继续查找
		else p=p->rchild; 					// 在*p 的右子树中继续查找
	}
	if (!p) return; 						// 找不到被删结点则返回
	/*----考虑3种情况实现p 所指子树内部的处理： *p 左右子树均不空、 无右子树、 无左子树－－－*/
	if ((p->lchild) && (p->rchild)) 		// 被删结点*p 左右子树均不空
	{
		q=p; s=p->lchild; 
		while (s->rchild) 					// 在*p 的左子树中继续查找其前驱结点，即最右下结点
		{
			q=s; s=s->rchild; 				// 向右到尽头
		}
		p->data=s->data; 					// s 指向被删结点的 “前驱＂
		if(q!=p) q->rchild=s->lchild; 		// 重接*q 的右子树
		else q->lchild=s->lchild; 			// 重接*q 的左子树
		delete s; 
		return; 
	}
	else if (! p->rchild) 					// 被删结点*p 无右子树， 只需重接其左子树
	{
		q=p; p=p->lchild; 
	}
	else if (!p- > lchild) 					// 被删结点*p 无左子树， 只需重接其右子树
	{
		q=p; p=p->rchild; 
	}
	/*＿＿＿＿＿＿＿＿＿＿＿＿＿＿－－将 p 所指的子树挂接到其双亲结点*f 相应的位置－－－＿＿＿＿＿＿＿＿＿＿*/
	if(!f) T=p; 							// 被删结点为根结点
	else if(q==f->lchild) f->lchild=p; 		// 挂接到*f 的左子树位置
	else f->rchild=p; 						// 挂接到*f 的右子树位置
	delete q; 
}

平衡二叉树（balanced binary tree）

• 又称AVL树（Adelson-Velskii and Landis）。
• 一棵平衡二叉树或者是空树，或者是具有下列性质的二叉排序树：
  ① 左子树与右子树的高度之差的绝对值小于等于1；
  ② 左子树和右子树也是平衡二叉排序树。
• 为了方便起见，给每个结点附加一个数字，给出该结点左子树与右子树的高度差。这个数字称为结点的平衡因子（BF）。
  平衡因子 = 结点左子树的高度 - 结点右子树的高度
• 根据平衡二叉树的定义，平衡二叉树上所有结点的平衡因子只能是-1、0，或1。
• 对于一棵有n个结点的AVL树，其高度保持在O(log₂n)数量级，ASL也保持在O(log₂n)量级。
  

平衡树的生成过程

失衡二叉排序树的分析与调整

当我们在一个平衡二叉排序树上插入一个结点时，有可能导致失衡，即出现平衡因子绝对值大于1的结点，如：2、-2。

如果在一棵AVL树中插入一个新结点后造成失衡，则必须重新调整树的结构，使之恢复平衡。

平衡调整的四种类型

A：失衡结点，不止一个失衡结点时，为最小失衡子树的根节点。
B：A结点的孩子，C结点的双亲。
C：插入新结点的子树。

失衡树的调整

调整原则：1）降低高度；2）保持二叉排序树性质。

LL型

• B结点带左子树B_L一起上升；
• A结点成为B的右孩子；
• 原来B结点的右子树B_R作为A的左子树。
  

RR型

• B结点带右子树B_R一起上升；
• A结点成为B的左孩子；
• 原来B结点的左子树B_L作为A的右子树。
  

LR型

• C结点穿过A、B结点上升；
• B结点成为C的左孩子，A结点成为C的右孩子；
• 原来C结点的左子树C_L作为B的右子树，原来C结点的右子树C_R作为A的左子树。
  

RL型

平衡二叉树的插入

在平衡的二叉排序树BBST上插入一个新的数据元素e的递归算法可描述如下。
① 若BBST为空树，则插入一个数据元素为e的新结点作为BBST的根结点，树的深度增1。
② 若e的关键字和BBST的根结点的关键字相等，则不进行插入。
③ 若e的关键字小于BBST的根结点的关键字，而且在BBST的左子树中不存在和e有相同关键字的结点，则将e插入在BBST的左子树上，并且当插入之后的左子树深度增加(+1)时，分别就下列不同情况处理之：
? BBST 的根结点的平衡因子为-1(右子树的深度大于左子树的深度）：则将根结点的平衡因子更改为0, BBST的深度不变；
? BBST的根结点的平衡因子为0(左、右子树的深度相等）：则将根结点的平衡因子更改为1, BBST的深度增1;
? BBST的根结点的平衡因子为1(左子树的深度大于右子树的深度）：若BBST的左子树根结点的平衡因子为1， 则需进行单向右旋平衡处理，并且在右旋处理之后，将根结点和其右子树根结点的平衡因子更改为 0, 树的深度不变；
? 若BBST的左子树根结点的平衡因子为-1，则需进行先向左、后向右的双向旋转平衡处理，,并且在旋转处理之后。修改根结点和其左、右子树根结点的平衡因子，树的深度不变。
② 若e的关键字大于BBST的根结点的关键字，而且在BBST的右子树中不存在和e有相同关键字的结点，则将e插入在BBST的右子树上，并且当插入之后的右子树深度增加(+I)时，分别就不同情况处理之。其处理操作和③ 中所述相对称，可自行补充。