二叉查找树和平衡树
#数据结构 #二叉树 #平衡树

二叉查找树

对于树中的每个结点X，它的左子树中所有关键字值小于X的关键字值，而它的右子树中所有关键字值大于X的关键字值

二叉查找树的平均深度\(O(log_2N)\)

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

typedef struct TreeNode *Tree;
typedef struct TreeNode TreeNode;
struct TreeNode
{
    int element;
    Tree left;
    Tree right;
};

// Find 查找指向树T中具有关键字X的结点的指针,如果这样的结点不存在则返回NULL
Tree Find(int x, Tree t)
{
    if (t == NULL)
    {
        return NULL;
    }
    if (x < t->element)
    {
        return Find(x, t->left);
    } else if (x > t->element)
    {
        return Find(x, t->right);
    }
    return t;
}

// FindMin 返回最小元的结点的指针
Tree FindMin(Tree t)
{
    if (t == NULL)
    {
        return NULL;
    }
    if (t->left == NULL)
    {
        return NULL;
    }
    return FindMin(t->left);
}

// FindMax 返回最大元的结点的指针
Tree FindMax(Tree t)
{
    if (t == NULL)
    {
        return NULL;
    }
    Tree cur = t;
    while (cur->right != NULL)
    {
        cur = cur->right;
    }
    return cur;
}

// Insert 插入元素x
Tree Insert(int x, Tree t)
{
    if (t == NULL)
    {
        Tree t = (Tree)malloc(sizeof(TreeNode));
        if (t == NULL)
        {
            printf("out of space!!!\n");
            return NULL;
        }
        t->element = x;
        t->left = NULL;
        t->right = NULL;
        return t;
    }
    if (x < t->element)
    {
        t->left = Insert(x, t->left);
    }
    if (x > t->element)
    {
        t->right = Insert(x, t->right);
    }
    return t;
}

// Delete 删除指定结点
Tree Delete(int x, Tree t)
{
    Tree tmpCell;
    if (t == NULL)
    {
        return NULL;
    }
    if (x == t->element)
    {
        // 该结点有两个子结点
        // 一般的删除策略是用其右子树的最小的数据代替该结点的数据并递归的删除那个结点
        if (t->left != NULL && t->right != NULL)
        {
            tmpCell = FindMin(t->right);
            t->element = tmpCell->element;
            t->right = Delete(t->element, t->right);
        } else
        {
            tmpCell = t;
            if (t->left == NULL)
            {
                t = t->right;
            } else if (t->right==NULL)
            {
                t = t->left;
            }
            free(tmpCell);
        }
    }
    if (x > t->element)
    {
        t->right = Delete(x, t->right);
    }
    if (x < t->element)
    {
        t->left = Delete(x, t->left);
    }
    return t;
}

平衡树

AVL树是带有平衡条件的二叉查找树，这个平衡条件必须要容易保持，而且它须保证树的深度是\(O(log_2N)\)

  • 一颗AVL树是其每个结点的左右子树的高度最多差1的二叉查找树
  • 在高度为h的AVL树中，最少结点数S(h)由S(h)=S(h-1) + S(h-2) + 1给出。对于h=0, S(h)=1; h=1, S(h)=2

重建平衡

不平衡的四种情况:

1和4是镜像对称，2和3是镜像对称，因此理论上只有两种情况

  1. 左子树的左子树进行一次插入
  2. 左子树的右子树进行一次插入
  3. 右子树的左子树进行一次插入
  4. 右子树的右子树进行一次插入

第一种情况是插入发生在“外边”的情况（即左-左或者右-右的情况），该情况下仅需通过对树的一次单旋转即可完成调整

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
graph TD

subgraph 单旋转后
A(5) --> B(2)
A(5) --> C(7)
B(2)-->D(1)
B(2)-->E(4)
E(4)-->F(3)
E(4)-->I((null))
C(7)-.->G(6)
C(7)-.->N(8)
end

subgraph 单旋转前
5 --> 2
5 --> 8
2-->1
2-->4
4-->3
4-->4r((null))
8-->7
8-->8r((null))
7-.->6
7-->7r((null))
end

第二种情况是发生在“内部“的情形，该情况需要通过稍微复杂的双旋转来处理

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
graph TD

subgraph 双旋转后
A(4)-->B(2)
A(4)-->C(7)
B(2)-->D(1)
B(2)-->E(3)
C(7)-->G(6)
C(7)-->H(15)
G(6)-->I(5)
G(6)-->L((null))
H(15)-->M(14)
H(15)-->N(16)
end

subgraph 双旋转前
4-->2
4-->6
2-->1
2-->3
6-->5
6-.->15
15-.->7
15-->16
7-->7l((null))
7-->14
end
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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
#include <stdio.h>
#include <stdlib.h>

typedef struct AvlNode *AvlTree;
typedef struct AvlNode AvlNode;
struct AvlNode
{
    int element;
    int height;
    AvlTree left;
    AvlTree right;
};

// Find 查找指向树T中具有关键字X的结点的指针,如果这样的结点不存在则返回NULL
AvlTree Find(int x, AvlTree t)
{
    if (t == NULL)
    {
        return NULL;
    }
    if (x < t->element)
    {
        return Find(x, t->left);
    }
    else if (x > t->element)
    {
        return Find(x, t->right);
    }
    return t;
}

// FindMin 返回最小元的结点的指针
AvlTree FindMin(AvlTree t)
{
    if (t == NULL)
    {
        return NULL;
    }
    if (t->left == NULL)
    {
        return NULL;
    }
    return FindMin(t->left);
}

// FindMax 返回最大元的结点的指针
AvlTree FindMax(AvlTree t)
{
    if (t == NULL)
    {
        return NULL;
    }
    AvlTree cur = t;
    while (cur->right != NULL)
    {
        cur = cur->right;
    }
    return cur;
}

int height(AvlTree t)
{
    if (t == NULL)
    {
        return -1;
    }
    return t->height;
}

int max(int a, int b)
{
    if (a > b)
    {
        return a;
    }
    return b;
}

// 左子树的左子树进行插入导致平衡树失衡
// 1. 指针p暂存该树根结点的左子树结点
// 2. 该树根结点的左子树的右子树作为根结点的左子树
// 3. 该树根结点作指针p的右子树
// 4. 指针p作为该树新的根结点
AvlTree singleRotateWithLeft(AvlTree t)
{
    AvlTree p;
    p = t->left;
    t->left = p->right;
    p->right = t;

    t->height = max(height(t->left), height(t->right)) + 1;
    p->height = max(height(p->left), height(p->right)) + 1;

    return p;
}

// 右子树的右子树进行插入导致平衡树失衡
// 1. 指针p暂存该树根结点的右子树结点
// 2. 该树根结点的右子树的左子树作为根结点的右子树
// 3. 该树根结点作指针p的左子树
// 4. 指针p作为该树新的根结点
AvlTree singleRotateWithRigth(AvlTree t)
{
    AvlTree p;
    p = t->right;
    t->right = p->left;
    p->left = t;

    t->height = max(height(t->left), height(t->right)) + 1;
    p->height = max(height(p->left), height(p->right)) + 1;

    return p;
}

// 右子树的左子树进行插入导致平衡树失衡
// 1. 针对该树根结点的左子树进行旋转
// 2. 针对该树根结点进行旋转
AvlTree doubleRotateWithLeft(AvlTree t)
{
    t->left = singleRotateWithRigth(t->left);
    return singleRotateWithLeft(t);
}

// 左子树的右子树进行插入导致平衡树失衡
// 1. 针对该树根结点的右子树进行一次旋转
// 2. 针对该树根结点进行旋转
AvlTree doubleRotateWithRigth(AvlTree t)
{
    t->right = singleRotateWithLeft(t->right);
    return singleRotateWithRigth(t);
}

// Insert 插入元素x
AvlTree Insert(int x, AvlTree t)
{
    if (t == NULL)
    {
        AvlTree t = (AvlTree)malloc(sizeof(AvlNode));
        if (t == NULL)
        {
            printf("out of space!!!\n");
            return NULL;
        }
        t->element = x;
        t->left = NULL;
        t->right = NULL;
        return t;
    }
    if (x < t->element)
    {
        t->left = Insert(x, t->left);
        if (height(t->left) - height(t->right) == 2)
        {
            // 左子树的左子树插入结点
            if (x < t->left->element)
            {
                t = singleRotateWithLeft(t);
            }
            // 左子树的右子树插入结点(双旋转)
            else
            {
                t = doubleRotateWithLeft(t);
            }
        }
    }
    if (x > t->element)
    {
        t->right = Insert(x, t->right);
        if (height(t->right) - height(t->left) == 2)
        {
            // 右子树的右子树插入结点
            if (x > t->right->element)
            {
                t = singleRotateWithRigth(t);
            }
            // 右子树的左子树插入结点(双旋转)
            else
            {
                t = doubleRotateWithRigth(t);
            }
        }
    }
    if (height(t->left) > height(t->right))
    {
        t->height = height(t->left) + 1;
    }
    else
    {
        t->height = height(t->right) + 1;
    }
    return t;
}

// Delete 删除指定结点
AvlTree Delete(int x, AvlTree t)
{
    AvlTree tmpCell;
    if (t == NULL)
    {
        return NULL;
    }
    if (x == t->element)
    {
        // 该结点有两个子结点
        // 一般的删除策略是用其右子树的最小的数据代替该结点的数据并递归的删除那个结点
        if (t->left != NULL && t->right != NULL)
        {
            tmpCell = FindMin(t->right);
            t->element = tmpCell->element;
            t->right = Delete(t->element, t->right);
        }
        else
        {
            tmpCell = t;
            if (t->left == NULL)
            {
                t = t->right;
            }
            else if (t->right == NULL)
            {
                t = t->left;
            }
            free(tmpCell);
        }
    }
    if (x > t->element)
    {
        t->right = Delete(x, t->right);
    }
    if (x < t->element)
    {
        t->left = Delete(x, t->left);
    }
    return t;
}
上一页
#数据结构 #二叉树 #平衡树
下一页