首页 > 代码库 > 平衡二叉树 AVL 的插入节点后旋转方法分析

平衡二叉树 AVL 的插入节点后旋转方法分析

2024-08-04 00:19:54   215人阅读

平衡二叉树 AVL（ 发明者为Adel‘son-Vel‘skii 和 Landis）是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1。

首先我们知道，当插入一个节点，从此插入点到树根节点路径上的所有节点的平衡都可能被打破，如何解决这个问题呢？

这里不讲大多数书上提的什么平衡因子，什么最小不平衡子树，实际上让人（me）更加费解。实际上你首要做的就是先找到第一个出现不平衡的节点，也就是高度最高的那个节点A，对以它为根的子树做一次旋转或者两次旋转，此时这个节点的平衡问题解决了，整个往上路径经过的节点平衡问题也随之解决。


下面先来分析下不平衡发生的四种情况：

1、An insertion into the left subtree of the left child of A; （LL）

2、An insertion into the right subtree of the left child of A;（RL）

3、An insertion into the left subtree of the right child of A;（LR）

4、An insertion into theright  child of A;（RR）


旋转方法：

1、A 和 A‘s child 顺时针旋转 singlerotateLL()

4、A 和 A‘s child 逆时针旋转 singlerotateRR()

2、A‘s child 和 A‘s grandchild 逆时针旋转，A 和 A‘s new child 顺时针旋转  doublerotateRL()

3、A‘s child 和 A‘s grandchild 顺时针旋转，A 和 A‘s new child 逆时针旋转 doublerotateLR()

可以看出1，4对称；2，3对称，实际在实现rotate函数的时候实现1和4即可，2和3直接调用1，4的实现。当然，这样说还是对应不上，下面上图分析。


第一种情况举例：


现在想要插入的点是6，请看是否符合第一种情况的描述。8是不是高度最高的发生不平衡的点？6是不是插入在A的左孩子的左子树？符合是吧，那就直接按上述方法顺时针旋转7和8，效果是右图。当然这只是逻辑上的视图而已，真正函数实现也不难，就是修改两个指针指向，待会再谈。第4种情况是对称的，就不说了。

下面来看第三种情况示例：


现在要插入的点是14，请看是否符合第3种情况的描述。6是不是高度最高的发生不平衡的点？14是不是插入在A的右孩子的左子树？符合是吧，那就先顺时针旋转7和15，中间结果如下图所示：

现在7是A的new child了是吧，那就逆时针旋转6和7就可以了。

接着来分析singlerotateLL() 和doublerotateRL() 的实现，剩下两个函数就是对称的了。

首先是singlerotateLL()，看下图：

改动其实很简单，先把Y解绑当k2的左孩子，接着k2成为k1的右孩子，代码如下：

 

 C++ Code 
1
2
3
4
5
6
7
8
9
10
11
 
/* return pointer to the new root */
static AVLNodePtr singlerotateLL(AVLNodePtr k2)
{
    AVLNodePtr 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), k2->height) + 1;
    return k1;
}

 

接着是doublerotateRL()的实现，看下图：


很明显B或者C的插入使得k3（A）不平衡了，那么首先应该是k1和k2逆时针旋转，所以调用

k3->left = singlerotateRR(k3->left);

接着是k3和new child 顺时针旋转，调用singlerotateLL(k3);

so easy, 代码如下：

 C++ Code 
1
2
3
4
5
 
static AVLNodePtr doublerotateRL(AVLNodePtr k3)
{
    k3->left = singlerotateRR(k3->left);
    return singlerotateLL(k3);
}

 

完整的测试代码如下：

 

 C++ Code 
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
 
#include <stdio.h>
#include <stdlib.h>

struct AVLNode;
typedef struct AVLNode *AVLNodePtr;

struct AVLNode
{
    int element;
    AVLNodePtr left;
    AVLNodePtr right;
    int height;
};

void makeempty(AVLNodePtr T)
{
    if (T == NULL)
        return;
    else
    {
        makeempty(T->left);
        makeempty(T->right);
        free(T);
    }
}

static int height(AVLNodePtr p)
{
    if (p == NULL)
        return -1;
    else
        return p->height;
}

static int Max(int ln, int rn)
{
    return ln > rn ? ln : rn;
}

/* return pointer to the new root */
static AVLNodePtr singlerotateLL(AVLNodePtr k2)
{
    AVLNodePtr 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), k2->height) + 1;
    return k1;
}

static AVLNodePtr singlerotateRR(AVLNodePtr k1)
{
    AVLNodePtr k2 = k1->right;
    k1->right = k2->left;
    k2->left = k1;
    k1->height = Max(height(k1->left), height(k1->right)) + 1;
    k2->height = Max(k1->height, height(k2->right)) + 1;
    return k2;
}

static AVLNodePtr doublerotateRL(AVLNodePtr k3)
{
    k3->left = singlerotateRR(k3->left);
    return singlerotateLL(k3);
}

static AVLNodePtr doublerotateLR(AVLNodePtr k3)
{
    k3->right = singlerotateLL(k3->right);
    return singlerotateRR(k3);
}


AVLNodePtr insert(int X, AVLNodePtr T)
{
    if (T == NULL)
    {
        /* create and return a one-node tree */
        T = (AVLNodePtr)malloc(sizeof(struct AVLNode));
        if (T == NULL)
        {
            printf("out of space!");
            exit(1);
        }
        else
        {
            T->element = X;
            T->height = 0;
            T->left = T->right = NULL;
        }
    }

    else if (X < T->element)
    {
        T->left = insert(X, T->left);
        if (height(T->left) - height(T->right) == 2)
        {
            if (X < T->left->element)
                T = singlerotateLL(T);
            else
                T = doublerotateRL(T);
        }
    }

    else if (X > T->element)
    {
        T->right = insert(X, T->right);
        if (height(T->right) - height(T->left) == 2)
        {
            if (X > T->right->element)
                T = singlerotateRR(T);
            else
                T = doublerotateLR(T);
        }
    }
    /* else X is in the tree already; we‘ll do nothing */
    T->height = Max(height(T->left), height(T->right)) + 1;
    return T;
}

void inorder(AVLNodePtr T)
{
    if (T == NULL)
        return;
    else
    {
        inorder(T->left);
        printf("%d ", T->element);
        inorder(T->right);
    }
}

int main(void)
{
    int arr[] = {3, 2, 1, 4, 5, 6, 7, 16, 15, 14, 13, 12, 11, 10, 8, 9};
    AVLNodePtr T = NULL;
    for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
        T = insert(arr[i], T);

    inorder(T);
    makeempty(T);
    return 0;
}
 

代码将数组元素插入后，中序遍历后输出，即1～16的顺序排列。

注意：输入数组元素就不要搞成有序的了，如果代码中没有调整的实现，整个树就是个右斜树，但即使实现了调整，也会使得每插入一次就调整一次，何必内耗啊。

 很显然，平衡二叉树的优势在于不会出现普通二叉查找树的最差情况。其查找的时间复杂度为O(logN)。


参考：《data structure and algorithm analysis in c》

平衡二叉树 AVL 的插入节点后旋转方法分析


联系
我们