高级数据结构之AVL树_由递增序列构造的排序树是avl

AVL树的简单介绍

百度百科
AVL树又叫做二叉平衡排序树，是平衡二叉树的一种改进版本。因为普通的平衡二叉树存在左右失衡，退化为链表的风险，因此需要某种策略来进行平衡调整。AVL树是根据左右子树的树高作为调整策略。也有一种叫做SB 树（size balance tree)，是根据左右子树节点的数量作为调整策略。

性质

• 拥有二叉排序树所有性质：
  任意节点的值大于左孩子，小于右孩子。
  即：通过中序遍历二叉排序树就可以得到一个有序序列。
• 任意节点满足左右子树高度差不大于1

失衡条件

AVL树的最重要性质就是左右子树是平衡的，因此打破了平衡就会导致失衡。也就是左右子树的高度差大于1。一般来说只会到达2。

失衡类型及调整方案

四种不平衡状态：

• LL：即某节点A的左子树失衡，（意味着A左子树高度= A 右左子树高度+ 2），且A左子树的左子树比A左子树的右子树更高。如图：
  

# 先看左边的图：

此时K1为失衡节点。假设ABCD的树高分别为HA,HB,HC,HD.
则根据失衡条件：
Hk2 = Hk3 + 2 //左子树树高比右子树大2
Hk2 = HA + 1 = HB + 2 // 因为是LL类型，左-左大于左-右
Hk3 = max(HC,HD) + 1; //显然HC HD 的差值最多为1
因此可以得到关系式：HA = HB + 1 = max(HC,HD) + 2
凡是满足这个式子的节点，它必然是LL类型的失衡。

在看右边的图：

旋转完成后：
K3 依然平衡
分析K1：由于 HB = max(HC,HD) + 1 因此K1显然也是平衡的
分析K2: 由于HA = HB + 1 所以K2也是平衡的。
所以旋转的本质是什么？就是把存在高度差的子树重新安排一个新的合适的位置。

• LR：显然LR的意思就是A的左子树失衡，且其右子树高度高于左子树。
  
  这种情况，需要先对A的左子树进行一次左旋，再对A进行右旋。（先小左旋，后大右旋）
  还是按照上面的套路分析树高：
  Hk2 = HD + 2 // 左子树失衡
  Hk2 = Hk3 + 1=HA + 2 = max(HB,HC) + 2 // HA+1 = Hk3
  可知： HA= HD = max(HB,HC）
  这就是LR失衡的四颗子树的高度关系。

• RR：与LL对称，只有左右顺序的差别 可以自行分析。
  调整操作为：对A左旋。(大左旋)

• RL：与LR对称，也不细说了。
  调整操作：先对A的左子树右旋，然后对A左旋。（先小右旋，后大左旋）

核心代码实现

//AVL树结构定义
#define L(n) (n->lchild)
#define R(n) (n->rchild)
#define H(n) (n->h)
typedef struct Node {
    int key;
    int h; //高度
    struct Node *lchild,*rchild;
} Node;
//虚拟空节点，替代NULL，可以访问
Node __NIL;
#define NIL (&__NIL)
__attribute__((constructor))
void init__NIL() {
    NIL->key = 0, NIL->h = 0;
    NIL->lchild = NIL->rchild = NIL;
    return;
}
//在main函数之前初始化上面这段代码


//左旋函数
Node *left_rotate(Node *root) {
    Node *temp = root->rchild; // 新根节点
    root->rchild = temp->lchild; //新的根节点的左成为了旧的根节点的右子树
    temp->lchild = root; //旧根成新左
    update_height(root);
    update_height(temp);
    return temp;
}
//右旋，记这个
Node *right_rotate(Node *root){
    Node *temp = root->lchild; // 新根
    root->lchild = temp->rchild; //新右成旧左
    temp->rchild = root; //旧根成新左
    update_height(root);
    update_height(temp);
    return temp;
}
//调整函数
Node *maintain(Node *root) {
    if (abs(H(L(root)) - H(R(root))) <= 1) return root;
        if (root->lchild->h > root->rchild->h) {
            //LR先小左旋
            if(root->lchild->lchild->h < root->lchild->rchild->h)
                root->lchild = left_rotate(root->lchild);
            //LL 只需大右旋
            root = right_rotate(root);
        } else {
                //RL 先小右旋
                if (root->rchild->rchild->h < root->rchild->lchild->h)
                    root->rchild = right_rotate(root->rchild);
                //RR 大左旋
                root = left_rotate(root);
        }

        return root;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

附录 完整代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;

#define L(n) (n->lchild)
#define R(n) (n->rchild)
#define H(n) (n->h)
typedef struct Node {
    int key;
    int h; //高度
    struct Node *lchild,*rchild;
} Node;
//虚拟空节点，替代NULL
Node __NIL;
#define NIL (&__NIL)
__attribute__((constructor))
void init__NIL() {
    NIL->key = 0, NIL->h = 0;
    NIL->lchild = NIL->rchild = NIL;
    return;
}
//优先初始化上面这段代码



Node *maintain(Node *root);

Node *getNewNode(int key) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->key = key;
    p->h = 1;
    p->lchild = p->rchild = NIL;
    return p;
}
void clear(Node *root) {
    if(root == NIL)
        return;
    clear(root->lchild);
    clear(root->rchild);
    free(root);
    return;
}

void update_height(Node *root){
    root->h = H(L(root)) > H(R(root)) ? H(L(root)) + 1 : H(R(root)) + 1;
    return;
}
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_height(root);
    return maintain(root);
}


//找前驱
Node *predecessor(Node *root) {
    Node* temp = root->lchild;
    //左节点的最右节点
    while(temp->rchild) temp = temp->rchild;
    return temp;
}
//左旋 和右旋对称
Node *left_rotate(Node *root) {
    Node *temp = root->rchild; // 新根节点
    root->rchild = temp->lchild; //新左挂旧右
    temp->lchild = root; //旧根挂新左
    update_height(root);
    update_height(temp);
    return temp;
}
//右旋，记这个
Node *right_rotate(Node *root){
    Node *temp = root->lchild; // 新根
    root->lchild = temp->rchild; //新右成旧左
    temp->rchild = root; //旧根成新左
    update_height(root);
    update_height(temp);
    return temp;
}
//调整
Node *maintain(Node *root) {
    if (abs(H(L(root)) - H(R(root))) <= 1) return root;
        if (root->lchild->h > root->rchild->h) {
            //LR先小左旋
            if(root->lchild->lchild->h < root->lchild->rchild->h)
                root->lchild = left_rotate(root->lchild);
            //LL 只需大右旋
            root = right_rotate(root);
        } else {
                //RL 先小右旋
                if (root->rchild->rchild->h < root->rchild->lchild->h)
                    root->rchild = right_rotate(root->rchild);
                //RR 大左旋
                root = left_rotate(root);
        }

        return root;
}
//删除
Node *erase(Node *root, int key){
    if ( root == NIL) return NIL;
    if (key < root->key)
        root->lchild = erase(root->lchild,key);
    else if(key > root->key)
        root->rchild = erase(root->rchild,key);
    else {
        // 叶子节点 或者 度为1
        if(root->lchild == NIL || root->rchild == NIL) {
            Node *temp = root->lchild ? root->lchild : root->rchild;
            free(root);
            return temp;
        } else {
            Node *temp = predecessor(root); // 找前驱
            root->key = temp->key; //覆盖当前值
            root->lchild = erase(root->lchild,root->key); //从左子树删除重复节点
        }

    }
    update_height(root);
    return maintain(root);
}

void printf(Node *root) {
    printf("(%d[%d],%d,%d)\n",
           root->key,root->h,
           root->lchild->h,
           root->rchild->h
          );
    return;
}
void output(Node *root) {
    if(root == NIL) return;
    printf(root);
    output(root->lchild);
    output(root->rchild);
    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);
    }
     return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164

代码执行

3[3],2,2 表示节点值为3，高度为3，左子树高度为2，右子树高度为2.可以观察到我们无论怎么插入，都能够保持平衡。