平衡二叉树

你看棵线段树，它可以这样旋，再这样旋。

抽了个时间专门把二叉排序树和AVL树学了一遍，写一下相关代码吧。

二叉排序树

定义

二叉排序树又加二叉搜索树，其主要性质如下：

左子树的值 < 根节点的值
右子树的值 > 根节点的值
中序遍历一颗二叉排序树，其结果是一个有序序列
平均查找效率: 假设每个点被查找的概率相同，节点查找次数的期望值 $\frac{总次数} {节点数量}$ 。

插入操作

插入的新节点一定会作为叶子节点存在于二叉排序树上。

删除操作

删除度为 $0$ 的节点时，直接删除即可
删除度为 $1$ 的节点时，把它唯一的一个叶子节点挂到自己的父亲节点上
删除度为 $2$ 的节点时，先找到该节点的前驱，将二者的值互换，然后转化为在左子树中删除度为 $1$ 的节点
- 对于度为 $2$ 的节点：
  - 前驱：左子树的最大值
  - 后继：右子树的最小值

实现代码如下：

#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;
}

主要用途

解决和排名有关的问题，例如 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 树-失衡类型

一颗树出现失衡的状态只发生在插入或者删除阶段，当插入结束进行回溯的时候，该节点发现自己不平衡了，就需要进行旋转保证自己子树的平衡。例如上图均是在 $K1$ 处观察第一次产生失衡。

LL 型: 也称“左左”。插入或删除一个节点后，根节点的左孩子（Left Child）的左孩子（Left Child）还有非空节点，导致根节点的左子树高度比右子树高度高 2，AVL 树失去平衡。
LR 型: 也称“左右”。插入或删除一个节点后，根节点的左孩子（Left Child）的右孩子（Right Child）还有非空节点，导致根节点的左子树高度比右子树高度高 2，AVL 树失去平衡。
RR 型: 也称“右右”。插入或删除一个节点后，根节点的右孩子（Right Child）的右孩子（Right Child）还有非空节点，导致根节点的右子树高度比左子树高度高 2，AVL树失去平衡。
RL 型: 也称“右左”。插入或删除一个节点后，根节点的右孩子（Right Child）的左孩子（Left Child）还有非空节点，导致根节点的右子树高度比左子树高度高 2，AVL树失去平衡。

AVL 树有且仅有上述 4 种失衡类型，其中 LL 与 RR， LR 与 RL 相对称。

AVL 树 -LL 型

如上图，在 $K1$ 处发生了 $LL$ 型失衡，假设 $A$，$B$，$C$，$D$ 的树高分别为 $h1$，$h2$，$h3$，$h4$，跟据 $AVL$ 树的性质应有如下等式：

首先，根据 $AVL$ 树的定义，如果在 $K1$ 处发生 $LL$ 型失衡，那么 $K2、K3$ 一定是平衡的，所以，$h1 = h2 + 1$
在 $K1$ 处发生 $LL$ 型失衡，说明 $K2$ 的高度与 $K3$ 的高度差是 $2$，而 $K3$ 的高度 $H(K3) = max(h3, h4) + 1$，$H(K2) = H(K3) + 2 = max(h3, h4) + 3$
而由于发生的是 $LL$ 型失衡，故 $H(K2) = h1 + 1$

根据上述推论得到如下等式：
$$h1= max(h3, h4) + 2 = h2 + 1$$

于是，以 $K1$ 为中心，右旋整棵树得到下图：

再次分析：

$K3$ 子树的高度为 $H(K3) = max(h3, h4) + 1$
$K1$ 子树的高度为 $H(K1) = max(H(K3), h2) + 1$
$K2$ 子树的高度为 $H(K2) = MAX(H(K1), h1) + 1$
整合可得 $H2 = h1 + 1 = max(h3, h4) + 2 = h2 + 1, $，右旋完后，整棵树保证平衡。
$RR$ 型同理，反向即可

AVL 树 -LR 型

如上图，在 $K1$ 处发生了 $LR$ 型失衡，假设 $A$，$B$，$C$，$D$ 的树高分别为 $h1$，$h2$，$h3$，$h4$，跟据 $AVL$ 树的性质应有如下等式：

$H(K2) = h4 + 2$
$H(K3) = max(h2, h3) + 1$
$h1 = H(K3) + 1$

综上归纳得出如下等式:

$$h1 = max(h2, h3) = h4$$

调整方法，先以 $K2$ 为中心进行左旋，转化为 $LL$ 型，然后以 $K1$ 为中心进行右旋，$RR$ 型同理反向即可。

实现代码

#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;
}