查找知识盘点(树形结构)_最小不平衡子树

上半部分顺序结构

---

树型查找

二叉排序树BST

（借图）

二叉排序树是一种有序的排序树，满足以下性质

• 若左子树非空，则左子树上所有结点值均小于根节点的值
• 若右子树非空，则右子树上所有结点值均大于根节点的值

即 左子树<根<右子树
如果我们对其进行中序排序就会得到一个递增的有序序列

因此我们对于二叉排序树的搜索主要是与根节点作比较，若key值>根节点值，则向其右子树搜索，若key值<根节点值，则向其左子树搜索。

BSTNode *BST_Search(Btree T,ElemType key){
	while(T==NULL || T.data==key){//当树为空或值为key结束
		if(key>T.data){
			T=T->rchild;
		}
		else{
			T=T->lchild;
		}
	}//while
	return T;//指针函数返回T当前位置作为指针
}
1
2
3
4
5
6
7
8
9
10
11

如果要实现某结点在二叉树中的插入，最重要的是找到其位置
那么插入的本质其实就可以理解为我们以新节点的值为key值遍历这颗二叉树，一旦找到其位置则插入，若发现没有它的位置则返回0

int BST_Insert(Btree &T,ElemType key){
	if(T==NULL){//当树为空时
		T=(Btree)malloc(sizeof(Btree));
		T.data=key;
		T->lchild=NULL;T->rchild=NULL;
	}
	if(T.data==key){
		return 0;}//已经有该结点
	else if(T.data<key){
		return BST_Insert(T->rchild,key);
	}
	else{
		return BST_Insert(T->lchild,key);
	}
	return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

构造二叉排序树

void create_BST(Btee &T,ElemType str[],int n){
	T=NULL;
	int i=0;
	while(i<n){
		BST_insert(T,str[i]);
		i++;}
}
1
2
3
4
5
6
7

对于二叉排序树的删除结点可分为三种情况

• 当被删除点是叶子节点则直接删除
• 被删除点非叶子，但只有一个孩子，直接将其孩子代替删除节点
• 被删除节点非叶子，且有两个孩子，那么应当用其最左孩子的左孩子（即不断遍历其左孩子直到左孩子为空时的根节点）替代被删除节点。

---

平衡二叉树

在构建二叉树的时候，为了防止二叉树高度增长过快导致性能降低，我们规定了一种平衡二叉树。平衡二叉树在插入和删除二叉树结点时要保证结点的左右子树高度差不能超过1，我们将高度差称为平衡因子，则平衡因子只有可能是-1，0，1。而不可能是2或-2。

平衡因子=左子树高度-右子树高度

关于平衡二叉树的插入和删除比较难理解，主要是平衡二叉树旋转的四种形状
LL型，RR型，LR型，RL型，我们主要就看最小不平衡子树的主要结点是什么形状的
注意以下单字母圆形节点的排列形状

LL旋转

LL型的节点排序，A是2，B为1，两个平衡因子是同号且都为正，在形状上是这样的

我们实现LL变换，就把平衡因子为1的这个B节点拎起来，想象一下把图（b）的B节点提起来，然后因为重力，BL成了它的左节点，A掉下来成了它的右节点，也就是以A为起点遍历两次Lchild，即为LL，遍历了A B BL，再以B为中心，BL和A分别成了B的左右孩子。原来节点BR断开，挂到了A的左子树，AR成了B的右子树。

RR旋转

同理，我们观察RR旋转，A为-2，B为-1，AB同号且都为负，那么要抓住其最小不平衡子树中的这个形状

我们以一样的方法，RR就是指以A开始遍历两个右子树得到A B BR三个节点，我们提起B结点，A成了左孩子，BR成了右孩子，BL挂到了A的右孩子上，就得到了图（c）

LR旋转

我们注意看ABC，从A开始遍历LR得到了A B C三个结点，其中A为2，B为-1，AB异号，C可以为1，-1或0

注意ABC的排列形状
那么我们这次以C为中心，把C提起来，从AB中间穿过，并将B作为左孩子，A作为右孩子，那么CL挂到了B的右孩子上，CR挂到了A的左孩子上，就得到了（c）

RL旋转

我们注意看ABC，从A开始遍历RL孩子得到了A B C三个结点，其中A为-2，B为1，AB异号，C可以为1，-1或0

注意ABC的排列形状
那么我们这次以C为中心，把C提起来，从AB中间穿过，并将A作为左孩子，B作为右孩子，那么CL挂到了A的右孩子上，CR挂到了B的左孩子上，就得到了（c）

当然上述描述只能用容易理解的方式说明它的形状变化，下面我们来看看一个简单的例子

我已经标出了变化前的最小不平衡二叉树的平衡因子
（d）中由于A的平衡因子是2，B是-1，两个异号，且形状是LR型，所以使用LR旋转
（g）中A是2，B是1，同号，使用LL旋转
（i）中A是-2，B是1，异号，且为RL型，使用RL旋转
当然插入和删除操作都是同理的，就是在最小不平衡子树上进行的四种旋转操作

---

红黑树

红黑树满足以下几个条件：

1. 每个结点要么红色，要么黑色
2. 根结点为黑色
3. 所有叶结点（无论是否为空）都是黑色
4. 不存在两个相邻的红色结点
5. 对每个结点，从该节点到任一叶结点的简单路径上，所含黑色结点的数量相同

结论一：从根到叶结点的最长路径不大于最短路径的2倍
结论二：有n个内部结点的红黑树高度h<=$2lo{g}_2(n+1)$
结论三：新插入红黑树的结点初始着色为红色

好麻烦，情况好多，不想看

---

B树

B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示
一颗m阶B树或为空树，或为满足以下特性的m叉树

1. 树中每个结点至多有 m 棵子树，即至多有m-1个关键字
2. 若根结点不是终端结点，则至少有两棵子树
3. 除根结点之外的所有非叶子结点至少有$\lceil m/2\rceil$棵子树，即至少含有$\lceil m/2\rceil -1$个关键字
4. 所有非叶结点的结构如下:

5) 所有的叶结点都出现在同一层上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空)

B树是所有结点的平衡因子均为0的多路平衡查找树

简单来说，B树就是一种多路并举的查找方法，它将不同区间的值放在了不同的层数和位置，你可以将其理解为一种特殊的二分查找法，第一层是第一次二分，第二层是在一次二分分为两个区间后再对这两个区间分别二分找出两个二分数，以此类推。
这个算法的好处是，我们可以尽可能快速的找出是否存在这个值，因为我们是按照区间来查找的，第一层相当于是二分法，第二层是四分，第三层是八分，我们只需要进入关键字属于的子树区间即可。一旦到达叶结点，也就宣告区间内没有我们想要的关键字，宣告失败。

B树的插入

如果想要在B树里插入，需要完成两步
第一步是找到其关键字的位置，这个并不难
但是要知道插入后由于B树结点的孩子必须满足关键字数-1
也就是说我们找到插入结点，还要满足上述的父子关系
因此第二步，我们常常需要分裂其孩子结点，使得某些孩子结点转移到父结点上满足这一条件
并且由于孩子结点分裂了，那么孩子的孩子也就不满足父子关系了，也就是说孩子的孩子也要分裂
那么这样重复下来，其结果往往是整棵B树的高度+1了，
如此看来，还不如重新构建一颗B树呢

B树的删除

B树的删除也要满足上述父子关系
我们尽量不改变父结点，如果，兄弟结点够借用的话，在删除该结点的某关键字后，可以和父结点借一个关键字，父结点再从兄弟结点借一个关键字，这样只改变兄弟结点后续结构即可
如果兄弟结点不够借用的话，那只能改变父结点了，这样会导致此后的结构都产生巨大变化

---

B+树

B+树是B树的变形结构，大体上二者是相似的，B+树主要有以下特点

1. 在B+树中，拥有m个关键字的结点有m棵子树，而非m+1
2. 每个结点关键字的范围是$\lceil m/2\rceil <=n<=m$,也就是说根节点至少有2个数，而叶结点的上一层的关键字数量n,1<=n<=2
3. B+树中，叶节点不是空结点，所有的非叶结点仅起到索引作用，与B树相反，所有的信息是存储在叶结点内的
4. B+树中，叶节点包含了所有关键字，这就意味着非叶结点的作为索引的关键字也是包含在叶结点之中的

其余插入删除等操作则是类似的