平衡树——AVL树

数据结构

平衡树的存在是为了解决二叉查找树的最坏情形——单支树的情况；因为二叉查找树的任意节点的期望平均深度为O（logN），但是，这只是期望值，很有可能出现二叉查找树只向其中一支子树不断生长的情况，那么，树的期望深度变成了O（根号（N）），这不是我们期望看到的，因此，我们希望，二叉查找树每时每刻都能保持左右子树深度的差值可以是{0,1}这两个树，这时，平衡树便被提了出来并实现。

平衡树有一个很重要的因子——平衡因子，平衡因子是决定旋转类型的重要因素，二叉查找树不平衡的情况有四种：①、对a的左儿子的左子树进行一次插入；②、对a的右儿子的右孩子树进行一次插入；③、对a的左儿子的右子树进行一次插入操作；④、对a的右儿子的左子树进行一次插入；其实理解下，只有两种情况：外边插入和内部插入，对于外边插入，我们只需要执行一次单旋转，如果是内部插入，那就要执行一次双旋转；那么如何区分外部插入和内部插入？简单来说，从插入位置开始检查连续的三个点A，B，C，如果这三个点在 ‘/’ 或者 ‘\’ 是一条直线，那么就是单旋转，如果不是一条直线，那么就是双旋转。

下面是平衡树（AVL）的代码，包括插入代码以及平衡的单双旋转代码

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
struct AvlNode {
    int date;
    AvlNode *left;
    AvlNode *right;
    int height;
}

int Height(AvlNode *T) {
    if(T ==NULL)
       return-1;
    return p ->height;
}

AvlNode* Insert(int x, AvlNode *T) {
    if(T ==NULL) {
        T = malloc(sizeof(struct AvlNode));
        if(T ==NULL)
            return NULL;
        else {
            T -> date = x;
            T -> left = T -> right = NULL;
        }
    }
    else
    if(x < T ->date){
        T -> left = Insert(x, T -> left);
        if(Height(T ->left)-Height(T - right)==2) {
            if(x < T ->left->date)
                T = SingleRotaWithLeft(T);
            else
                T = DoubleRotaWithLeft(T);
        }
    }
    else
    if(x > T ->date){
        T -> right = Insert(x, T- > right);
        if(Height(T ->right)-Height(T ->left)==2) {
            if(x > T ->right->date)
                T = SingleRotaWithRight(T);
            else
                T = DoubleRotaWithRight(T);
        }
    }
    T -> height = Max(Height(T -> left), Height(T -> right)) + 1; 
    return T;
}

未命名文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
右单旋转
*/
AvlNode* SingleRotaWithLeft(AvlNode *k2) {
    AvlNode *k1;
    k1 = k2 -> left;
    k2 -> left = k1 -> right;
    k1 -> right = k2;
    k2 -> height = Max(Height(k2 -> left), Height(k2 -> right) + 1);
    k1 -> height = Max(Height(k1 -> left), Height(k1 -> right) + 1);
}

/*
左单旋转
*/
AvlNode* SingleRotaWithRight(AvlNode *k2) {
    AvlNode *k1;
    k1 = k2 -> right;
    k2 -> right = k1 -> left;
    k1 -> left = k2;
    k2 -> height = Max(Height(k2 -> left) + 1, Height(k2 -> right));
    k1 -> height = Max(Height(k1 -> left) + 1, Height(k1 -> right));
}

未命名文件 (1)

1
2
3
4
5
6
7
8
9
10
11
12
/*
双旋转，先进行左单旋转，再进行右单旋转
*/
AvlNode* DoubleRotaWithLeft(AvlNode *k3) {
    k3 -> left = SingleRotaWithRight(k3 -> left);
    return SingleRotaWithLeft(k3);
}

AvlNode* DoubleRotaWithRight(AvlNode *k3) {
    k3 -> right = SingleRotaWithLeft(k3 -> right);
    return SingleRotaWithRight(k3);
}