3.树形查找

二叉排序树

构造一棵二叉排序树的目的并不是为了排序,而是为了提高查找、插入和删除关键字的速度,二叉排序树这种非线性结构也有利于插入和删除的实现。

定义

二叉排序树(也称二叉查找树)或者是一棵空树,或者是具有下列特性的二叉树:

1. 若左子树非空,则左子树上所有结点的值均小于根结点的值。
2. 若右子树非空,则右子树上所有结点的值均大于根结点的值。
3. 左、右子树也分别是一棵二叉排序树。

根据二叉排序树的定义,左子树结点值 <根结点值 <右子树结点值,因此对二叉排序树进行中序遍历,可以得到一个递增的有序序列。

查找

// 递归实现
BSTNode *BSTSearch(BSTree T, int key) {
	if ( T== NULL)
		return NULL; //查找失败
	if (k e y==T->k e y)
		return T; //查找成功
	else if (key < T->key)
		return BSTSearch(T->lchild, key)；//在左子树中找
	else
		return BSTSearch(T->rchild, key)；//在右子树中找
}
// 非递归实现
BSTNode *BSTSearch(BSTree T, int key) {
	while(T != NULL && T->value != key){
		if(key < T->value) T = T->lchild; //在左子树中找
		else  T = T->rchild；//在右子树中找
	}
	return T;
}

空间复杂度递归$O(n)$，非递归$O(1)$

插入

int BST_Insert(BSTree &T, int key){
	if(T == NULL){ //树为空
		T = (BiTree)malloc(sizeof(BSTNode));
		T->key = key;
		T->lchild = T->rchild = NULL;
		return 1; //插入成功返回1
	}
	else if(key == T->key) return 0; //存在相同关键字的结点，插入失败返回
	else if(key < T->key) return BST_Insert(T->lchild, key);
	else return BST_Insert(T->rchild, key);
}

构造

void Creat_BST(BSTree &T,int str[],int n){
	T=NULL; //初始时T为空树
	int i=0;
	while(i<n){
		//依次将每个关键字插入到二叉排序树中
		BST_Insert(T,str[i]);
		i++;
	}
}

删除

在二叉排序树中删除一个结点时,不能把以该结点为根的子树上的结点都删除,必须先把被删除结点从存储二叉排序树的链表上摘下,将因州除结点而断开的二叉链表重新链接起来,同时确保二叉排序树的性质不会丟失。

删除操作的实现过程按3种情况来处理:

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

image.png

查找效率分析

• 二叉排序树的查找效率, 主要取决于树的高度。若二叉排序树的左、右子树的高度之差 的绝对值不超过 1 (平衡二叉树), 它的平均查找长度为 $O\left(\log _{2} n\right)$ 。
• 若二叉排序树是 一个只有右（左）孩子的单支树（类似于有序的单链表）, 则其平均查找长度为 $O(n)$ 。
• 二分查找的判定树唯一,而二叉排序树的查找不唯一,相同的关键字其插入顺序不同可能生成不同的二叉排序树

提示

当有序表是静态查找表时,宜用顺序表作为其存储结构,而采用二分查找实现其找操作;若有序表是动态查找表,则应选择二叉排序树作为其逻辑结构。

平衡二叉树

定义

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

插入

每当在二叉排序树中插入(或删除)一个结点时,首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。若导致了不平衡,则先找到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点$A$,再对以$A$为根的子树,在保持二叉排序树特性的前提下,调整各结点的位置关系,使之重新达到平衡。

image.png

image.png

image.png

image.png

总结

• 在LL和RR中都是将B调整到A的位置，A则顺势下移，B上移后，A则成为B其中一个孩子，故原B中被替换掉的孩子转移为A的孩子
• 在LR和RL中都是将C作为"根"，B的位置不变，A,B均作为C的孩子，A,B原先已经存在的孩子位置不变，然后将C的孩子分配给A,B（按照大小关系）

删除

【课件】7.3.2_2平衡二叉树的删除

---

与平衡二叉树的插入操作类似, 以删除结点 $\mathrm{w}$ 为例来说明平衡二叉树删除操作的步骤:

1. 用二叉排序树的方法对结点 $\mathrm{w}$ 执行删除操作。
2. 若导致了不平衡, 则从结点 $\mathrm{w}$ 开始向上回溯, 找到第一个不平衡的结点 $\mathrm{z}$ (即最小不平 衡子树); $\mathrm{y}$ 为结点 $\mathrm{z}$ 的高度最高的孩子结点; $\mathrm{x}$ 是结点 $\mathrm{y}$ 的高度最高的孩子结点。
3. 然后对以 $z$ 为根的子树进行平衡调整, 其中 $x$、$y$ 和 $z$ 可能的位置有 4 种情况:
   • $\mathrm{y}$ 是 $\mathrm{z}$ 的左孩子, $\mathrm{x}$ 是 $\mathrm{y}$ 的左孩子 ( $\mathrm{LL}$, 右单旋转);
   • $\mathrm{y}$ 是 $\mathrm{z}$ 的左孩子, $\mathrm{x}$ 是 $\mathrm{y}$ 的右孩子 (LR, 先左后右双旋转);
   • $y$ 是 $z$ 的右孩子, $x$ 是 $y$ 的右孩子 ( $R R$, 左单旋转);
   • $y$ 是 $\mathrm{z}$ 的右孩子, $\mathrm{x}$ 是 $\mathrm{y}$ 的左孩子 ( $R L$, 先右后左双旋转)。

这四种情况与插入操作的调整方式一样。不同之处在于, 插入操作仅需要对以 $\mathrm{z}$ 为根的子树 进行平衡调整; 而删除操作就不一样, 先对以 $\mathrm{z}$ 为根的子树进行平衡调整, 如果调整后子树的高度减 1 , 则可能需要对 $\mathrm{z}$ 的祖先结点进行平衡调整, 甚至回溯到根结点（导致树高减 1)。

以删除图中结点 32 为例, 由于 32 为叶结点, 直接删除即可, 向上回溯找到第一个不平衡结点 $44($ 即 $\mathrm{z}), \mathrm{z}$ 的高度最高的孩子结点为 $78(\mathrm{y}), \mathrm{y}$ 的高度最高的孩子结点为 $50(\mathrm{x})$, 满足 $\mathrm{RL}$ 情况, 先右后左双旋转, 调整后的结果如图所示。

image.png

查找

比较的关键字个数不超过树的深度。假设以 $n_{h}$ 表示深度为 $h$ 的平衡树中含有的最少结点数。显然, 有 $n_{0}=0, n_{1}=1, n_{2}=2$, 并且有 $n_{h}=n_{h-1}+n_{h-2}+1$ 。可以证明, 含有 $n$ 个结点的平衡二叉树的最大深度为 $O\left(\log _{2} n\right)$, 因此平衡二叉树的平均查找长度为 $O\left(\log _{2} n\right)$, 如图所示。视频讲解

image.png

提示

结点个数n最少的情况下，所有非叶子结点的平衡因子都是1

红黑树

警告

考研不会涉及太难的考点（红黑树是在 22 年才加入的大纲），大概率是考察红黑树的定义、性质（选择题），插入最多就是掌握手绘过程，其中删除操作比插入更复杂，考察概率更小

定义

一棵红黑树是满足如下红黑性质的二叉排序树：

1. 每个结点或是红色，或是黑色的。
2. 根结点是黑色的。
3. 叶结点（虚构的外部结点、NULL 结点）都是黑色的。
4. 不存在两个相邻的红结点（即红结点的父结点和孩子结点均是黑色的）。
5. 对每个结点，从该结点到任意一个叶结,点的简单路径上，所含黑结点的数量相同。

简单路径简单路径简单路径简单路径简单路径简单路径简单路径简单路径简单路径简单路径简单路径路径、简单回路)上的黑结点总数称为该结点的黑高(记为bh),黑高的概念是由性质5确定的。根结点的黑高称为红黑树的黑高

结论

1. 从根到叶结点的最长路径不大于最短路径的2倍。
2. 有$n$个内部结点的红黑树的高度 $h \leqslant 2 \log _{2}(n+1)$ 。

插入

image.png

【课件】7.3.3_2红黑树的插入.pdf

---