平衡二叉树

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

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

二叉排序树

定义

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

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

插入操作

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

删除操作

  1. 删除度为 $0$ 的节点时,直接删除即可
  2. 删除度为 $1$ 的节点时,把它唯一的一个叶子节点挂到自己的父亲节点上
  3. 删除度为 $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;
}

主要用途

  1. 解决和排名有关的问题,例如 TOP-K 问题,前 K 大的数字有哪些

AVL 树

  二叉排序树有一个弊端就是会退化成为链表。当插入顺序为 [1, 2, 3, 4, 5] 时,根据二叉排序树的定义,会形成如下的一颗树
image.png
  为了解决这种退化,人们发明了 AVL 树(平衡二叉排序树)。

定义

  在 AVL 树中任何节点的两个子树的高度最大差别为 $1$,所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。由于对每个节点的左右⼦树的树⾼做了限制,所以整棵树不会退化成⼀个链表。

  当高度为 $H$ 时,二叉排序树所包含的节点的数量在什么范围内呢?
$$H \le SIZE(H) \le 2H - 1$$
  当高度为 $H$ 时,平衡二叉排序树所包含的节点的数量在什么范围内呢?
定义 $low(H)$,代表高为 $H$ 时,AVL 树所包含的最小的节点个数,那么得到如下递推式:
$$low(H-2) + low(H-1) + 1 \le SIZE(H) \le 2
H - 1$$
根据上述公式,可以观察出与 Fibonacci 序列的递推方式类似,Fibonacci 序列的增长速度大概为 $1.618n$,所以当高度为 $H$ 时,平衡二叉排序树所包含的节点的数量应该在如下范围内:
$$1.618
H \le SIZE(H) \le 2^H - 1$$
同时,节点个数 $n$ 与树高 $h$ 之间的关系为 $h = \log(n)$

AVL 树-左旋

image.png

  如上图,以 $K1$ 为中心进行左旋,$K3$ 将作为新的根节点,而 $K1$ 将作为 $K3$ 的左子树,同时 $K3$ 原来的左子树 $A$ 变为 $K1$ 的右子树,满足二叉排序树的条件,进而左旋成如下的结果:
image.png

AVL 树-右旋

image.png

  如上图,以 $K1$ 为中心进行右旋,$K2$ 将作为新的根节点,而 $K1$ 将作为 $K2$ 的右子树,同时 $K2$ 原来的右子树 $B$ 变为 $K1$ 的左子树,满足二叉排序树的条件,进而右旋成如下的结果:
image.png

AVL 树-失衡类型

image.png

  一颗树出现失衡的状态只发生在插入或者删除阶段,当插入结束进行回溯的时候 ,该节点发现自己不平衡了,就需要进行旋转保证自己子树的平衡。例如上图均是在 $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 种失衡类型,其中 LLRRLRRL 相对称。

AVL 树 -LL 型

image.png
  如上图,在 $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$ 为中心,右旋整棵树得到下图:
image.png

再次分析:

  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 型

image.png

  如上图,在 $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$ 型同理反向即可。

image.png

实现代码

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