> 你看棵线段树，它可以这样旋，再这样旋。
抽了个时间专门把二叉排序树和[AVL树](https://baike.baidu.com/item/AVL%E6%A0%91/10986648?fr=aladdin)学了一遍，写一下相关代码吧。
## 二叉排序树
### 定义
二叉排序树又加二叉搜索树，其主要性质如下：
1. 左子树的值 < 根节点的值
2. 右子树的值 > 根节点的值
3. 中序遍历一颗二叉排序树，其结果是一个有序序列
4. 平均查找效率: 假设每个点被查找的概率相同，节点查找次数的期望值 $\frac{总次数} {节点数量}$ 。
### 插入操作
1. 插入的新节点一定会作为叶子节点存在于二叉排序树上。
### 删除操作
1. 删除度为 $0$ 的节点时，直接删除即可
2. 删除度为 $1$ 的节点时，把它唯一的一个叶子节点挂到自己的父亲节点上
3. 删除度为 $2$ 的节点时，先找到该节点的前驱，将二者的值互换，然后转化为在左子树中删除度为 $1$ 的节点
- 对于度为 $2$ 的节点：
- 前驱：左子树的最大值
- 后继：右子树的最小值
实现代码如下：
```cpp
#include <stdio.h>
#include <stdlib.h>
#define KEY(n) (n ? n->key : 0)
#define SIZE(n) (n ? n->size : 0)
typedef struct Node {
int key, size;
struct Node *lchild, *rchild;
} Node;
void Update_size(Node *root) {
root->size = SIZE(root->lchild) + SIZE(root->rchild) + 1;
return ;
}
// 创建一个新节点
Node* GetNewNode(int key) {
Node *p = (Node*)malloc(sizeof(Node));
p->key = key;
p->size = 1;
p->lchild = p->rchild = NULL;
return p;
}
//删除整棵树
void Clear(Node *root) {
if(root == NULL)
return ;
Clear(root->lchild);
Clear(root->rchild);
free(root);
return ;
}
//查询第 K 大的数字
int Search_k(Node *root, int k) {
if(root == NULL)return -1;
if(SIZE(root->lchild) == k-1)
return root->key;
return Search_k(root->rchild, k - SIZE(root->lchild) - 1);
}
//查询某个值是否存在于树上
int Search(Node *root, int val) {
if(root == NULL)return 0;
if(root->key == val)return 1;
if(val < root->key)return Search(root->lchild, val);
return Search(root->rchild, val);
}
//插入
Node* Insert(Node *root, int key) {
if(root == NULL)return GetNewNode(key);
if(root->key == key)return root;
if(key < root->key) root->lchild = Insert(root->lchild, key);
else root->rchild = Insert(root->rchild, key);
Update_size(root);
return root;
}
//查询某个节点的前驱，有 BUG，可能该节点的前驱与它本身不在同一个子树中
Node* FindPre(Node *root) {
Node *tmp = root->lchild;
while(tmp->rchild != NULL) tmp = tmp->rchild;
return tmp;
}
//删除一个点
#if 1
Node* DelNode(Node* root, int key) {
if(root == NULL)return root;
if(root->key == key) {
if(root->lchild == NULL || root->rchild == NULL) {
Node *tmp = (root->lchild == NULL)?root->rchild : root->lchild;
free(root);
return tmp;
} else {
Node *pre = FindPre(root);
root->key = pre->key;
root->lchild = DelNode(root->lchild, pre->key);
}
}
if(key < root->key) {
root->lchild = DelNode(root->lchild, key);
} else {
root->rchild = DelNode(root->rchild, key);
}
Update_size(root);
return root;
}
#endif
#if 0
Node* DelNode(Node *root, int key) {
if(root == NULL) return root;
if(key < root->key) {
root->lchild = DelNode(root->lchild, key);
} else if(key > root->key) {
root->rchild = DelNode(root->rchild, key);
} else {
if(root->lchild == NULL || root->rchild == NULL) {
Node *tmp = (root->lchild == NULL) ? root->rchild : root->lchild;
free(root);
return tmp;
} else {
Node *pre = FindPre(root);
root->key = pre->key;
root->lchild = DelNode(root->lchild, pre->key);
}
}
Update_size(root);
return root;
}
#endif
//中序遍历输出整棵树
void Output(Node *root) {
if(root == NULL)return ;
Output(root->lchild);
printf("(%d[%d], %d, %d)\n", KEY(root), SIZE(root), KEY(root->lchild), KEY(root->rchild));
Output(root->rchild);
return ;
}
int main() {
int op, val;
Node *root = NULL;
while(~scanf("%d %d", &op, &val)) {
switch (op) {
case 0:
printf("search %d, result: %d\n",val, Search(root, val));
break;
case 1:
root = Insert(root, val);
break;
case 2:
root = DelNode(root, val);
break;
case 3:
printf("search k = %d, result: %d\n",val, Search_k(root, val));
break;
}
if(op) {
Output(root);
printf("--------------------\n");
}
}
Clear(root);
return 0;
}
```
### 主要用途
1. 解决和排名有关的问题，例如 TOP-K 问题，前 K 大的数字有哪些
## AVL 树
二叉排序树有一个弊端就是会退化成为链表。当插入顺序为 [1, 2, 3, 4, 5] 时，根据二叉排序树的定义，会形成如下的一颗树
为了解决这种退化，人们发明了 AVL 树(平衡二叉排序树)。
### 定义
在 AVL 树中任何节点的两个子树的高度最大差别为 $1$，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。由于对每个节点的左右⼦树的树⾼做了限制，所以整棵树不会退化成⼀个链表。
当高度为 $H$ 时，二叉排序树所包含的节点的数量在什么范围内呢？
$$H \le SIZE(H) \le 2^H - 1$$
当高度为 $H$ 时，平衡二叉排序树所包含的节点的数量在什么范围内呢？
定义 $low(H)$，代表高为 $H$ 时，AVL 树所包含的最小的节点个数，那么得到如下递推式：
$$low(H-2) + low(H-1) + 1 \le SIZE(H) \le 2^H - 1$$
根据上述公式，可以观察出与 Fibonacci 序列的递推方式类似，Fibonacci 序列的增长速度大概为 $1.618^n$，所以当高度为 $H$ 时，平衡二叉排序树所包含的节点的数量应该在如下范围内：
$$1.618^H \le SIZE(H) \le 2^H - 1$$
同时，节点个数 $n$ 与树高 $h$ 之间的关系为 $h = \log(n)$
### AVL 树-左旋
如上图，以 $K1$ 为中心进行左旋，$K3$ 将作为新的根节点，而 $K1$ 将作为 $K3$ 的左子树，同时 $K3$ 原来的左子树 $A$ 变为 $K1$ 的右子树，满足二叉排序树的条件，进而左旋成如下的结果：
### AVL 树-右旋
如上图，以 $K1$ 为中心进行右旋，$K2$ 将作为新的根节点，而 $K1$ 将作为 $K2$ 的右子树，同时 $K2$ 原来的右子树 $B$ 变为 $K1$ 的左子树，满足二叉排序树的条件，进而右旋成如下的结果：
### AVL 树-失衡类型
一颗树出现失衡的状态只发生在插入或者删除阶段，<font color="#FF0000">当插入结束进行回溯的时候</font> ，该节点发现自己不平衡了，就需要进行旋转保证自己子树的平衡。例如上图均是在 $K1$ 处观察第一次产生失衡。
- <font color="#00BFFF">**LL 型**</font>: 也称“左左”。插入或删除一个节点后，根节点的左孩子（Left Child）的左孩子（Left Child）还有非空节点，导致根节点的**左子树高度比右子树高度高 2**，AVL 树失去平衡。
- <font color="#00BFFF">**LR 型**</font>: 也称“左右”。插入或删除一个节点后，根节点的左孩子（Left Child）的右孩子（Right Child）还有非空节点，导致**根节点的左子树高度比右子树高度高 2**，AVL 树失去平衡。
- <font color="#00BFFF">**RR 型**</font>: 也称“右右”。插入或删除一个节点后，根节点的右孩子（Right Child）的右孩子（Right Child）还有非空节点，导致**根节点的右子树高度比左子树高度高 2**，AVL树失去平衡。
- <font color="#00BFFF">**RL 型**</font>: 也称“右左”。插入或删除一个节点后，根节点的右孩子（Right Child）的左孩子（Left Child）还有非空节点，导致**根节点的右子树高度比左子树高度高** 2，AVL树失去平衡。
<font color="#FF0000">AVL 树有且仅有上述 4 种失衡类型</font>，其中 **LL** 与 **RR**， **LR** 与 **RL** 相对称。
#### AVL 树 -LL 型
如上图，在 $K1$ 处发生了 $LL$ 型失衡，假设 $A$，$B$，$C$，$D$ 的树高分别为 $h1$，$h2$，$h3$，$h4$，跟据 $AVL$ 树的性质应有如下等式：
1. 首先，根据 $AVL$ 树的定义，如果在 $K1$ 处发生 $LL$ 型失衡，那么 $K2、K3$ 一定是平衡的，所以，$h1 = h2 + 1$
2. 在 $K1$ 处发生 $LL$ 型失衡，说明 $K2$ 的高度与 $K3$ 的高度差是 $2$，而 $K3$ 的高度 $H(K3) = max(h3, h4) + 1$，$H(K2) = H(K3) + 2 = max(h3, h4) + 3$
3. 而由于发生的是 $LL$ 型失衡，故 $H(K2) = h1 + 1$
根据上述推论得到如下等式：
$$h1= max(h3, h4) + 2 = h2 + 1$$
于是，以 $K1$ 为中心，右旋整棵树得到下图：
再次分析：
1. $K3$ 子树的高度为 $H(K3) = max(h3, h4) + 1$
2. $K1$ 子树的高度为 $H(K1) = max(H(K3), h2) + 1$
3. $K2$ 子树的高度为 $H(K2) = MAX(H(K1), h1) + 1$
4. 整合可得 $H2 = h1 + 1 = max(h3, h4) + 2 = h2 + 1, $，右旋完后，整棵树保证平衡。
5. $RR$ 型同理，反向即可
#### AVL 树 -LR 型
如上图，在 $K1$ 处发生了 $LR$ 型失衡，假设 $A$，$B$，$C$，$D$ 的树高分别为 $h1$，$h2$，$h3$，$h4$，跟据 $AVL$ 树的性质应有如下等式：
1. $H(K2) = h4 + 2$
2. $H(K3) = max(h2, h3) + 1$
3. $h1 = H(K3) + 1$
综上归纳得出如下等式:
$$h1 = max(h2, h3) = h4$$
调整方法，先以 $K2$ 为中心进行左旋，转化为 $LL$ 型，然后以 $K1$ 为中心进行右旋，$RR$ 型同理反向即可。
### 实现代码
```cpp
#include <stdio.h>
#include <stdlib.h>
#define H(n) (n?n->h:0)
//定义树的相关属性，维护树高
typedef struct Node{
int key, h;
struct Node* lchild, *rchild;
} Node;
//引入 NIL来代替 NULL，NULL 不可被访问，但是 NIL 是一个实际节点可以被访问，将所有节点的指针初始置为 NIL
Node __NIL;
#define NIL (&__NIL)
__attribute__((constructor))
void Init_NIL(){
NIL->key = NIL->h = 0;
NIL->lchild = NIL->rchild = NIL;
return ;
}
//创建一个新节点
Node* GetNewNode(int key) {
Node* p = (Node*)malloc(sizeof(Node));
p->key = key;
p->lchild = p->rchild = NIL;
p->h = 1;
return p;
}
//每次删除、插入操作都需要重新计算树高
void Update_Heigh(Node *root) {
root->h = (H(root->lchild) > H(root->rchild) ? H(root->lchild) : H(root->rchild)) + 1;
return ;
}
//左旋，先保存当前节点的右儿子，因为它会是旋转后的新根节点
//然后新根节点的左孩子变成原根节点的右孩子
//新根节点的左孩子变成原来根节点的右孩子
//更新树高
Node *Left_rotate(Node *root) {
Node *tmp = root->rchild;
root->rchild = tmp->lchild;
tmp->lchild = root;
Update_Heigh(root);
Update_Heigh(tmp);
return tmp;
}
//与左旋相反
Node *Right_rotate(Node *root) {
Node *tmp = root->lchild;
root->lchild = tmp->rchild;
tmp->rchild = root;
Update_Heigh(root);
Update_Heigh(tmp);
return tmp;
}
//AVL 树平衡调整代码
Node* Maintain(Node *root) {
if(abs(H(root->lchild) - H(root->rchild)) <= 1)return root;
if(H(root->lchild) > H(root->rchild)) {
if(root->lchild->lchild->h < root->lchild->rchild->h) {
root->lchild = Left_rotate(root->lchild);
}
root = Right_rotate(root);
} else {
if(root->rchild->rchild->h < root->rchild->lchild->h) {
root->rchild = Right_rotate(root->rchild);
}
root = Left_rotate(root);
}
return root;
}
//插入节点
Node* Insert(Node* root, int key) {
if(root == NIL)return GetNewNode(key);
if(root->key == key)return root;
if(key < root->key) {
root->lchild = Insert(root->lchild, key);
} else {
root->rchild = Insert(root->rchild, key);
}
Update_Heigh(root);//注意更新树高
return Maintain(root);
}
//有BUG的前驱查询
Node* Find_Pre(Node *root) {
Node* tmp = root->lchild;
while(tmp != NIL) tmp = tmp->rchild;
return tmp;
}
//删除某个节点
Node* Erase(Node* root,int key) {
if(root == NIL) return root;
if(key < root->key) {
root->lchild = Erase(root->lchild, key);
} else if(key > root->key) {
root->rchild = Erase(root->rchild, key);
} else {
if(root->lchild == NIL || root->rchild == NIL) {
Node *tmp = (root->lchild == NIL)?root->rchild:root->lchild;
if(tmp == NIL)
return tmp;
free(tmp);
return tmp;
} else {
Node *pre = Find_Pre(root);
root->key = pre->key;
Erase(root->lchild, pre->key);
return root;
}
}
Update_Heigh(root);
return Maintain(root);
}
void Print_Node(Node *root) {
printf("(%d[%d], %d, %d)\n",
root->key, root->h,
root->lchild->key,
root->rchild->key
);
return ;
}
//先序遍历
void Output(Node *root) {
if(root == NIL)return ;
Print_Node(root);
Output(root->lchild);
Output(root->rchild);
return ;
}
void clear(Node* root) {
if(root == NIL)
return ;
clear(root->lchild);
clear(root->rchild);
free(root);
return ;
}
int main() {
int op, val;
Node *root = NIL;
while(~scanf("%d %d", &op, &val)) {
switch (op) {
case 0:
root = Erase(root, val);
break;
case 1:
root = Insert(root, val);
break;
}
Output(root);
printf("--------------\n");
}
clear(root);
return 0;
}
```
平衡二叉树
