AVL树的介绍
AVL树是一种自平衡的二叉搜索树，它通过单旋转（single rotate）和双旋转(double rotate)的方式实现了根节点的左子树与右子树的高度差不超过1,。这有效的降低了二叉搜索树的时间复杂度，为O（log n）。那么，下面小编将详细介绍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
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
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
|
/* *平衡二叉树应该有些功能 *插入 删除 查找 *前序遍历 中序遍历 后序遍历 层次遍历 *统计结点数目 */ //代码已经调好，写了很久才写出来 #ifndef _AVLTREE_#define _AVLTREE_#include<iostream>#include<vector>#include<queue>#include<map>using namespace std;#define MAXFACTOR = 2;template<class Key , class E>class AVLNode{ private: Key key; E value; AVLNode<Key,E>* left; AVLNode<Key,E>* right; AVLNode<Key,E>* parent; public: AVLNode():left(nullptr),right(nullptr),parent(nullptr){} AVLNode(Key _key,E _value , AVLNode<Key,E>* _parent = nullptr,AVLNode<Key,E>*_left = nullptr, AVLNode<Key,E>*_right = nullptr): key(_key),value(_value),left(_left),right(_right),parent(_parent){} bool isLeaf(){return left==nullptr && right == nullptr ;} //元素设置 Key getKey() const { return key;} void setKey(Key set) {key = set;} E getValue() const { return value;} void setValue(E set) {value = set;} AVLNode<Key,E>* getLeft() { return left; } void setLeft (AVLNode< Key,E >* set){ left = set;} AVLNode<Key,E>* getRight() { return right;} void setRight (AVLNode<Key,E>* set) {right = set ;} AVLNode<Key,E>* getParent() {return parent;} void setParent(AVLNode<Key,E>* set) { parent = set;}};template<class Key , class E>class AVLTree{ private: AVLNode<Key,E>* root; void clear(AVLNode<Key,E>* &r) { if(r==nullptr)return; if(r->getLeft())clear(r->getLeft()); if(r->getRight())clear(r->getRight); delete r; } void Init() { root = new AVLNode<Key,E>(); root=nullptr; } void preOrder(AVLNode<Key,E>* r,void(*visit) (AVLNode<Key,E> * node)) { if(r==nullptr)return; (*visit) (r); preOrder(r->getLeft() , visit); preOrder(r->getRight(), visit); } void inOrder(AVLNode<Key,E>* r , void(*visit)(AVLNode<Key,E>* node) ) { if(r==nullptr)return; inOrder(r->getLeft() , visit); (*visit)(r); inOrder(r->getRight(),visit); } void postOrder(AVLNode<Key,E>*r , void (*visit) (AVLNode<Key,E>* node)) { if(r==nullptr)return; postOrder(r->getLeft(),visit); postOrder(r->getRight(),visit); (*visit)(r); } void levelOrder(AVLNode<Key,E>*r , void (*visit) (AVLNode<Key,E>* node)) { queue< AVLNode<Key,E>* > q; if(r==nullptr)return; q.push(r); while( ! q.empty() ) { AVLNode<Key,E>* tmp = q.front(); q.pop(); (*visit)(tmp); if(tmp->getLeft() ) q.push(tmp->getLeft() ); if(tmp->getRight()) q.push(tmp->getRight()); } } AVLNode<Key,E>* find(AVLNode<Key,E>* r,Key k) { if(r==nullptr)return nullptr; if(k == r->getKey() ) return r; else if( k < r->getKey()) { find(r->getLeft(),k); } else { find(r->getRight(),k); } } //Find the smallest element in the avl tree AVLNode<Key,E>* getMin(AVLNode<Key,E>* r) { if(r->getLeft() == nullptr) return r; else{ getMin(r->getLeft()); } } //Remove the smallest element AVLNode<Key,E>* deleteMin(AVLNode<Key,E>* rt) { if(rt->getLeft() == nullptr) return rt->getRight(); else{ rt->setLeft(deleteMin(rt->getLeft())); return rt; } } AVLNode<Key,E>* leftRotate(AVLNode<Key,E>* node) { if( node == nullptr) return nullptr; AVLNode<Key,E>* newHead = node->getRight(); node->setRight( newHead -> getLeft() ); newHead -> setLeft( node ); return newHead; } AVLNode<Key,E>* rightRotate(AVLNode<Key,E>* node) { if(node == nullptr)return nullptr; AVLNode<Key,E>* newHead = node->getLeft(); node->setLeft( newHead->getRight() ); newHead ->setRight(node); return newHead; } int getHeight(AVLNode<Key,E>*node) { if(node == nullptr)return 0; if(node->isLeaf())return 1; else return ( getHeight( node->getLeft() ) > getHeight( node->getRight() ) ? getHeight( node->getLeft() ) : getHeight( node->getRight() ) ) + 1; } int getBalanceFactor(AVLNode<Key,E>* node) { return getHeight(node->getLeft()) - getHeight(node->getRight() ); } AVLNode<Key,E>* balance(AVLNode<Key,E>* node) { if(!node) return nullptr; else if ( getBalanceFactor( node ) == 2) { if(getBalanceFactor( node ->getLeft() ) == 1) { node = rightRotate(node); } else { node->setLeft(leftRotate( node->getLeft() ) ); node = rightRotate(node); } } else if(getBalanceFactor( node ) == -2) { if(getBalanceFactor( node->getRight()) == -1) { node = leftRotate(node); } else { node->setRight( rightRotate( node->getRight() ) ); node = leftRotate(node); } } return node; } AVLNode<Key,E>* insert( AVLNode<Key,E>* root ,const pair<Key,E>& it) { if(root == nullptr) { return new AVLNode<Key,E>(it.first , it.second,NULL,NULL,NULL); } else if (it.first < root->getKey() ) { root ->setLeft( insert(root->getLeft() , it) ) ; } else{ root ->setRight( insert(root->getRight() , it) ); } root = balance(root); return root; } AVLNode<Key,E>* remove(AVLNode<Key,E>* node , const Key k) { if(node == nullptr) return nullptr; if(node->getKey() > k) { node->setLeft( remove(node->getLeft() , k) ); node = balance(node); } else if(node->getKey() < k) { node->setRight( remove(node->getRight(), k) ); node = balance(node); } else if(node->getKey() == k) { if(! node->isLeaf() ) { AVLNode<Key,E>* tmp = getMin(node->getRight() ); node->setKey( tmp->getKey() ); node->setValue( tmp->getValue() ); node->setRight( deleteMin(node->getRight() ) ); delete tmp; } else { AVLNode<Key,E>* tmp = node; node = (node->getLeft() != nullptr) ? node->getLeft() : node->getRight() ; delete tmp; } } return node; } public: ~AVLTree(){clear(root);} AVLTree(){/*Init();*/ root = nullptr; } //四种遍历方式 void preOrder( void (*visit)(AVLNode<Key,E>* r)) { preOrder(root,visit); } void inOrder(void (*visit)(AVLNode<Key,E>* r)) { inOrder(root,visit); } void postOrder(void (*visit)(AVLNode<Key,E>* r)) { postOrder(root,visit); } void levelOrder( void(*visit)(AVLNode<Key,E>*r) ) { levelOrder(root,visit); } //插入 void insert(const pair<Key,E> &it) { root = insert(root,it); } //删除 void remove(const Key& k) { remove(root,k); } bool find(const Key&k) { return find(root,k); } };#endif |
|
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
|
//AVLtest.cpp#include"NewAvl.h"#include<iostream>using namespace std;template<typename Key,typename E>void traverse(AVLNode<Key,E>* root){ cout<<root->getKey()<<" "<<root->getValue()<<" "; cout<<endl;}int main(){ AVLTree<int,int>* tree = new AVLTree<int ,int>; for(int i = 0 ; i < 5 ; i ++) { tree->insert(make_pair(i,i)); } tree->remove(1); cout<<"PreOrder: "<<endl; tree->preOrder(traverse); cout<<endl; cout<<"LevelOrder: "<<endl; tree->levelOrder(traverse); cout<<endl; cout<<"InOrder: "<<endl; tree->inOrder(traverse); cout<<endl; cout<<"PostOrder: "<<endl; tree->postOrder(traverse); cout<<endl; cout<<tree->find(2)<<endl; tree->insert(make_pair(9,9)); tree->levelOrder(traverse);} |
运行结果
以上就是C++实现AVL树的完整代码的详细内容，更多关于C++ AVL树的资料请关注服务器之家其它相关文章！
原文链接：https://blog.csdn.net/qq_51711403/article/details/117444588
