大二的时候数据结构课死活没看懂的一个东东，看了2小时，敲了2小时，调了2小时。。。
平衡树某一节点的左右子树高度相差大于1的时候即需要调整，调整可分为四中情况 ll,rr,lr,rl其中lr,rl是由不同顺序的ll,rr来实现的，代码比想象的简短。
一棵平衡的树只有在插入和删除节点的时候，才会变的不平衡，所以掌握好时机，判断平衡是否破坏及不平衡的种类，再纠正即可
代码如下。。
avl.h
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 |
struct
AVLNode { struct
AVLNode *left; struct
AVLNode *right; int
data; int
height;};static
const int AVL_STATUS_OK = 0;static
const int AVL_STATUS_FOUNDED = 1;static
const int AVL_STATUS_NOTFOUNDED = 2;static
const int AVL_STATUS_FAILED = -1;int
avl_insert(struct
AVLNode **root, int
data);int
avl_find(struct
AVLNode *root, int
data);int
avl_del(struct
AVLNode **root, int
data);int
avl_del_tree(struct
AVLNode *root);void
print_avl_tree(struct
AVLNode *root);int
_get_height(struct
AVLNode *node);int
_max(int
a, int
b);void
_single_rotate_left(struct
AVLNode **node);void
_single_rotate_right(struct
AVLNode **node);void
_double_rotate_left_right(struct
AVLNode **node);void
_double_rotate_right_left(struct
AVLNode **node); |
avl.c
|
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 |
#include <stdio.h>#include <stdlib.h>#include <assert.h>#include "avl.h"int avl_insert(struct
AVLNode **ptr_root, int
data) { int
ret; if(NULL == *ptr_root) { *ptr_root = malloc(sizeof(struct
AVLNode)); if(NULL == *ptr_root) { return
AVL_STATUS_FAILED; } (*ptr_root)->data = data; (*ptr_root)->left = NULL; (*ptr_root)->right = NULL; (*ptr_root)->height = 0; return
AVL_STATUS_OK; } if(data == (*ptr_root)->data) { return
AVL_STATUS_OK; } else
if(data < (*ptr_root)->data) { ret = avl_insert(&((*ptr_root)->left), data); if(_get_height((*ptr_root)->left) - _get_height((*ptr_root)->right) > 1){ if(data < (*ptr_root)->left->data){ _single_rotate_left(ptr_root); } else
{ _double_rotate_left_right(ptr_root); } } } else
{ ret = avl_insert(&((*ptr_root)->right), data); if(_get_height((*ptr_root)->right) - _get_height((*ptr_root)->left) > 1){ if(data > (*ptr_root)->right->data) { _single_rotate_right(ptr_root); } else
{ _double_rotate_right_left(ptr_root); } } } (*ptr_root)->height = _max(_get_height((*ptr_root)->left), _get_height((*ptr_root)->right)) + 1; return
ret;}int
avl_find(struct
AVLNode *root, int
data) { if(NULL == root) { return
AVL_STATUS_NOTFOUNDED; } if(data == root->data) { return
AVL_STATUS_FOUNDED; } if(data < root->data) { return
avl_find(root->left, data); } else
{ return
avl_find(root->right, data); }}int
avl_del(struct
AVLNode **root, int
data) { struct
AVLNode *t; if(*root == NULL) { return
AVL_STATUS_OK; } if(data < (*root)->data) { avl_del(&((*root)->left), data); if(_get_height((*root)->right) - _get_height((*root)->left) > 1){ if((*root)->right->left != NULL && (_get_height((*root)->right->left) > _get_height((*root)->right->right))) { _double_rotate_right_left(root); } else
{ _single_rotate_right(root); } } } else
if(data > (*root)->data) { avl_del(&((*root)->right), data); if(_get_height((*root)->left) - _get_height((*root)->right) > 1){ if((*root)->left->right != NULL && (_get_height((*root)->left->right) > _get_height((*root)->left->left))) { _double_rotate_left_right(root); } else
{ _single_rotate_left(root); } } } else
{ if(NULL != (*root)->left && NULL != (*root)->right) { t = (*root) -> right; while(t->left != NULL) { t = t->left; } (*root) -> data = t->data; avl_del(&((*root)->right), t->data); if(_get_height((*root)->left) - _get_height((*root)->right) > 1){ if((*root)->left->right != NULL && (_get_height((*root)->left->right) > _get_height((*root)->left->left))) { _double_rotate_left_right(root); } else
{ _single_rotate_left(root); } } } else
{ t = *root; if((*root)->left == NULL) { *root = (*root) -> right; } else
if((*root)->right == NULL) { *root = (*root) -> left; } free(t); } } return
AVL_STATUS_OK;}int
avl_del_tree(struct
AVLNode *root) { if(NULL == root) { return
AVL_STATUS_OK; } avl_del_tree(root->left); avl_del_tree(root->right); free(root); return
AVL_STATUS_OK;}int
_get_height(struct
AVLNode *node) { if(NULL == node){ return
-1; } else{ return
node->height; }}int
_max(int
a, int
b) { return
a > b ? a:b;}void
_single_rotate_left(struct
AVLNode **node) { struct
AVLNode* root = *node; *node = root->left; root->left = (*node)->right; (*node)->right = root; root->height = _max(_get_height(root->left), _get_height(root->right)) + 1; (*node)->height = _max(_get_height((*node)->left), _get_height((*node)->right)) + 1;}void
_single_rotate_right(struct
AVLNode **node) { struct
AVLNode* root = *node; *node = root->right; root->right = (*node)->left; (*node)->left = root; root->height = _max(_get_height(root->left), _get_height(root->right)) + 1; (*node)->height = _max(_get_height((*node)->left), _get_height((*node)->right)) + 1;}void
_double_rotate_left_right(struct
AVLNode **node) { struct
AVLNode* root = *node; _single_rotate_right(&(root->left)); _single_rotate_left(node);}void
_double_rotate_right_left(struct
AVLNode **node) { struct
AVLNode* root = *node; _single_rotate_left(&(root->right)); _single_rotate_right(node);}void
print_avl_tree(struct
AVLNode *node) { if(NULL == node) { return; } print_avl_tree(node->left); printf("%d\t%d\n", node->data, node->height); print_avl_tree(node->right);} |
main.c
|
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 |
#include <stdio.h>#include "avl.h"int main() { struct
AVLNode *root = NULL; int
ret = avl_insert(&root, 7); printf("hello, world\n"); printf("root:address %ld\n", (long)root); printf("after:%d\n", 7); print_avl_tree(root); avl_insert(&root, 6); printf("after:%d\n", 6); print_avl_tree(root); avl_insert(&root, 5); printf("after:%d\n", 5); print_avl_tree(root); avl_insert(&root, 7); printf("after:%d\n", 7); print_avl_tree(root); avl_insert(&root, 1); printf("after:%d\n", 1); print_avl_tree(root); avl_insert(&root, 0); printf("after:%d\n", 0); print_avl_tree(root); avl_insert(&root, 9); printf("after:%d\n", 9); print_avl_tree(root); ret = avl_find(root, 7); printf("find 7 result is %d\n", ret); ret = avl_find(root, 17); printf("find 17 result is %d\n", ret); ret = avl_del(&root, 7); printf("del 7 result is %d\n", ret); print_avl_tree(root); ret = avl_del(&root, 17); printf("del 17 result is %d\n", ret); print_avl_tree(root); avl_del_tree(root); return
0;} |
#gcc -g main.c avl.c -o main
#./main
hello, world
root:address 27951120
after:7
7 0
after:6
6
0
7 1
after:5
5 0
6 1
7
0
after:7
5 0
6 1
7 0
after:1
1 0
5
1
6 2
7 0
after:0
0 0
1 1
5
0
6 2
7 0
after:9
0 0
1 1
5
0
6 2
7 1
9 0
find 7 result is 1
find 17 result
is 2
del 7 result is 0
0 0
1 1
5 0
6
2
9 0
del 17 result is 0
0 0
1 1
5 0
6
2
9 0
应该是正确的。
原文：http://www.cnblogs.com/igloo1986/p/3574636.html