AVLtree（C++实现）有统一的旋转操作
路璐 人气:1在学习完AVLtree之后，我发现，左旋，右旋均可以采用统一的旋转方式来实现，所以把代码贴在下面
代码是完整的AVLTree实现
C++标准为C++11
在ubuntu 18.04下通过编译和调试
1 /*
2 * BinarySearchTree.h
3 * 1. 添加元素时需自己做判断元素是否合法
4 * 2. 除层序遍历外，本源代码均采用递归遍历，若要减少栈的消耗，应该实现递归遍历
5 * 3. 本代码实现的AVL树有统一旋转操作，不用分情况讨论LL,LR,RR,RL来进行树的平衡
6 * 统一旋转操作有特殊优化版本和统一接口版本，本代码保留了统一接口的源码，但是采用的是特殊优化版本
7 * Created on: 2020年1月29日
8 * Author: LuYonglei
9 */
10
11 #ifndef SRC_BINARYSEARCHTREE_H_
12 #define SRC_BINARYSEARCHTREE_H_
13 #include <queue>
14
15 template<typename Element>
16 class BinarySearchTree {
17 public:
18
19 BinarySearchTree(int (*cmp)(Element e1, Element e2)); //比较函数指针
20
21 virtual ~BinarySearchTree();
22
23 int size(); //元素的数量
24
25 bool isEmpty(); //是否为空
26
27 void clear() {
28 //清空所有元素
29 NODE *node = root_;
30 root_ = nullptr;
31 using namespace std;
32 queue<NODE*> q;
33 q.push(node);
34 while (!q.empty()) {
35 NODE *tmp = q.front();
36 if (tmp->left != nullptr)
37 q.push(tmp->left);
38 if (tmp->right != nullptr)
39 q.push(tmp->right);
40 delete tmp;
41 q.pop();
42 }
43 }
44
45 void add(Element e) {
46 //添加元素
47 add(e, cmp_);
48 }
49
50 void remove(Element e) {
51 //删除元素
52 remove(Node(e, cmp_));
53 }
54
55 bool contains(Element e) {
56 //是否包含某元素
57 return Node(e, cmp_) != nullptr;
58 }
59
60 void preorderTraversal(bool (*visitor)(Element &e)) {
61 //前序遍历
62 if (visitor == nullptr)
63 return;
64 bool stop = false; //停止标志，若stop为true，则停止遍历
65 preorderTraversal(root_, stop, visitor);
66 }
67
68 void inorderTraversal(bool (*visitor)(Element &e)) {
69 //中序遍历
70 if (visitor == nullptr)
71 return;
72 bool stop = false; //停止标志，若stop为true，则停止遍历
73 inorderTraversal(root_, stop, visitor);
74 }
75
76 void postorderTraversal(bool (*visitor)(Element &e)) {
77 //后序遍历
78 if (visitor == nullptr)
79 return;
80 bool stop = false; //停止标志，若stop为true，则停止遍历
81 postorderTraversal(root_, stop, visitor);
82 }
83
84 void levelOrderTraversal(bool (*visitor)(Element &e)) {
85 //层序遍历，迭代实现
86 if (visitor == nullptr)
87 return;
88 levelOrderTraversal(root_, visitor);
89 }
90
91 int height() {
92 //树的高度
93 return height(root_);
94 }
95
96 bool isComplete() {
97 //判断是否是完全二叉树
98 return isComplete(root_);
99 }
100
101 private:
102
103 int size_;
104
105 typedef struct _Node {
106 Element e;
107 _Node *parent;
108 _Node *left;
109 _Node *right;
110 int height; //节点的高度
111 _Node(Element e_, _Node *parent_) :
112 e(e_), parent(parent_), left(nullptr), right(nullptr), height(1) {
113 //节点构造函数
114 }
115
116 inline bool isLeaf() {
117 return (left == nullptr && right == nullptr);
118 }
119
120 inline bool hasTwoChildren() {
121 return (left != nullptr && right != nullptr);
122 }
123
124 inline int balanceFactor() {
125 //获得节点的平衡因子
126 int leftHeight = left == nullptr ? 0 : left->height; //获得左子树的高度
127 int rightHeight = right == nullptr ? 0 : right->height; //获得右子树的高度
128 return leftHeight - rightHeight;
129 }
130
131 inline bool isBalanced() {
132 //判断node是否平衡
133 int balanceFactor_ = balanceFactor();
134 return balanceFactor_ >= -1 && balanceFactor_ <= 1; //平衡因子为-1,0,1则返回true
135 }
136
137 inline void updateHeight() {
138 //更新节点的高度
139 int leftHeight = left == nullptr ? 0 : left->height; //获得左子树的高度
140 int rightHeight = right == nullptr ? 0 : right->height; //获得右子树的高度
141 height = 1 + (leftHeight > rightHeight ? leftHeight : rightHeight); //把节点高度更新为左右子树最大的高度+1
142 }
143
144 inline bool isLeftChild() {
145 //判断节点是否是父亲节点的左子结点
146 return parent != nullptr && parent->left == this;
147 }
148
149 inline bool isRightChild() {
150 //判断节点是否是父亲节点的右子结点
151 return parent != nullptr && parent->right == this;
152 }
153
154 inline _Node* tallerChild() {
155 //获得高度更高的子树
156 int leftHeight = left == nullptr ? 0 : left->height; //获得左子树的高度
157 int rightHeight = right == nullptr ? 0 : right->height; //获得右子树的高度
158 if (leftHeight > rightHeight)
159 return left;
160 if (leftHeight < rightHeight)
161 return right;
162 return isLeftChild() ? left : right;
163 }
164
165 } NODE;
166
167 NODE *root_;
168
169 int (*cmp_)(Element e1, Element e2); //为实现树的排序的个性化配置，私有成员保存一个比较函数指针
170
171 NODE* Node(Element e, int (*cmp_)(Element e1, Element e2)) {
172 //返回e元素所在的节点
173 NODE *node = root_;
174 while (node != nullptr) {
175 int cmp = cmp_(e, node->e);
176 if (cmp == 0) //找到了元素
177 return node;
178 if (cmp > 0) { //待寻找元素大于节点存储的元素
179 node = node->right;
180 } else { //待寻找元素小于节点存储的元素
181 node = node->left;
182 }
183 }
184 return nullptr;
185 }
186
187 NODE* predecessor(NODE *node) {
188 //返回node的前驱节点
189 if (node == nullptr)
190 return nullptr;
191 //前驱节点在左子树
192 NODE *tmp = node->left;
193 if (tmp != nullptr) {
194 while (tmp->right != nullptr)
195 tmp = tmp->right;
196 return tmp;
197 }
198 //从父节点，祖父节点中寻找前驱节点
199 while (node->parent != nullptr && node == node->parent->left) {
200 node = node->parent;
201 }
202 return node->parent;
203 }
204
205 NODE* successor(NODE *node) {
206 //返回node的后继节点
207 if (node == nullptr)
208 return nullptr;
209 //后继节点在右子树
210 NODE *tmp = node->right;
211 if (tmp != nullptr) {
212 while (tmp->left != nullptr)
213 tmp = tmp->left;
214 return tmp;
215 }
216 //从父节点，祖父节点中寻找后继节点
217 while (node->parent != nullptr && node == node->parent->right) {
218 node = node->parent;
219 }
220 return node->parent;
221 }
222
223 #if 0
224 //统一接口版本(未优化)
225 void rotate(NODE *r, NODE *a, NODE *b, NODE *c, NODE *d, NODE *e, NODE *f,
226 NODE *g) {
227 //统一的旋转操作
228 /* r是变换前高度最低的不平衡节点
229 * 传入的参数a,b,c,d,e,f,g是经过变换后节点应该在的位置
230 * d
231 * / \
232 * b f
233 * / \ / \
234 * a c e g
235 * a,c,e,g均有可能为空，所以要对它们做判空处理
236 * b,d,f绝不为空
237 * d的parent可能为null，则d就为根节点，所以就要改变树中root_的指向
238 */
239 //对d节点做处理
240 d->parent = r->parent;
241 if (r->isLeftChild())
242 r->parent->left = d;
243 else if (r->isRightChild())
244 r->parent->right = d;
245 else
246 root_ = d;
247 //a-b-c
248 b->left = a;
249 b->right = c;
250 if (a != nullptr)
251 a->parent = b;
252 if (c != nullptr)
253 c->parent = b;
254 b->updateHeight();
255 //e-f-g
256 f->left = e;
257 f->right = g;
258 if (e != nullptr)
259 e->parent = f;
260 if (g != nullptr)
261 g->parent = f;
262 f->updateHeight();
263 //b-d-f
264 d->left = b;
265 d->right = f;
266 b->parent = d;
267 f->parent = d;
268 d->updateHeight();
269 }
270
271 void rebalance(NODE *gNode) {
272 //恢复平衡,grand为高度最低的不平衡节点
273 NODE *pNode = gNode->tallerChild();
274 NODE *nNode = pNode->tallerChild();
275 if (pNode->isLeftChild()) {
276 if (nNode->isLeftChild()) {
277 //LL
278 /*
279 * gNode(f)
280 * / \ 变换后
281 * pNode(d) g ====> pNode(d)
282 * / \ / \
283 * nNode(b) e nNode(b) gNode(f)
284 * / \ / \ / \
285 * a c a c e g
286 */
287 rotate(gNode, nNode->left, nNode, nNode->right, pNode,
288 pNode->right, gNode, gNode->right);
289 } else {
290 //LR
291 /*
292 * gNode(f)
293 * / \ 变换后
294 * pNode(b) g ====> nNode(d)
295 * / \ / \
296 * a nNode(d) pNode(b) gNode(f)
297 * / \ / \ / \
298 * c e a c e g
299 */
300 rotate(gNode, pNode->left, pNode, nNode->left, nNode,
301 nNode->right, gNode, gNode->right);
302 }
303 } else {
304 if (nNode->isLeftChild()) {
305 //RL
306 /*
307 * gNode(b)
308 * / \ 变换后
309 * a pNode(f) ====> nNode(d)
310 * / \ / \
311 * nNode(d) g gNode(b) pNode(f)
312 * / \ / \ / \
313 * c e a c e g
314 */
315 rotate(gNode, gNode->left, gNode, nNode->left, nNode,
316 nNode->right, pNode, pNode->right);
317 } else {
318 //RR
319 /*
320 * gNode(b)
321 * / \ 变换后
322 * a pNode(d) ====> pNode(d)
323 * / \ / \
324 * c nNode(f) gNode(b) nNode(f)
325 * / \ / \ / \
326 * e g a c e g
327 */
328 rotate(gNode, gNode->left, gNode, pNode->left, pNode,
329 nNode->left, nNode, nNode->right);
330 }
331 }
332 }
333
334 #endif
335
336 void rotate(NODE *r, NODE *b, NODE *c, NODE *d, NODE *e, NODE *f) {
337 //统一的旋转操作
338 /* r是变换前高度最低的不平衡节点
339 * 传入的参数b,c,d,e,f是经过变换后节点应该在的位置
340 * d
341 * / \
342 * b f
343 * / \ / \
344 * a c e g
345 * c,e均有可能为空，所以要对它们做判空处理
346 * b,d,f绝不为空
347 * d的parent可能为null，则d就为根节点，所以就要改变树中root_的指向
348 */
349 //对d节点做处理
350 d->parent = r->parent;
351 if (r->isLeftChild())
352 r->parent->left = d;
353 else if (r->isRightChild())
354 r->parent->right = d;
355 else
356 root_ = d;
357 //b-c
358 b->right = c;
359 if (c != nullptr)
360 c->parent = b;
361 b->updateHeight();
362 //e-f
363 f->left = e;
364 if (e != nullptr)
365 e->parent = f;
366 f->updateHeight();
367 //b-d-f
368 d->left = b;
369 d->right = f;
370 b->parent = d;
371 f->parent = d;
372 d->updateHeight();
373 }
374
375 void rebalance(NODE *gNode) {
376 //恢复平衡,grand为高度最低的不平衡节点
377 NODE *pNode = gNode->tallerChild();
378 NODE *nNode = pNode->tallerChild();
379 if (pNode->isLeftChild()) {
380 if (nNode->isLeftChild()) {
381 //LL
382 /*
383 * gNode(f)
384 * / \ 变换后
385 * pNode(d) g ====> pNode(d)
386 * / \ / \
387 * nNode(b) e nNode(b) gNode(f)
388 * / \ / \ / \
389 * a c a c e g
390 */
391 rotate(gNode, nNode, nNode->right, pNode, pNode->right, gNode);
392 } else {
393 //LR
394 /*
395 * gNode(f)
396 * / \ 变换后
397 * pNode(b) g ====> nNode(d)
398 * / \ / \
399 * a nNode(d) pNode(b) gNode(f)
400 * / \ / \ / \
401 * c e a c e g
402 */
403 rotate(gNode, pNode, nNode->left, nNode, nNode->right, gNode);
404 }
405 } else {
406 if (nNode->isLeftChild()) {
407 //RL
408 /*
409 * gNode(b)
410 * / \ 变换后
411 * a pNode(f) ====> nNode(d)
412 * / \ / \
413 * nNode(d) g gNode(b) pNode(f)
414 * / \ / \ / \
415 * c e a c e g
416 */
417 rotate(gNode, gNode, nNode->left, nNode, nNode->right, pNode);
418 } else {
419 //RR
420 /*
421 * gNode(b)
422 * / \ 变换后
423 * a pNode(d) ====> pNode(d)
424 * / \ / \
425 * c nNode(f) gNode(b) nNode(f)
426 * / \ / \ / \
427 * e g a c e g
428 */
429 rotate(gNode, gNode, pNode->left, pNode, nNode->left, nNode);
430 }
431 }
432 }
433
434 void afterAdd(NODE *node) {
435 //添加node之后的调整
436 if (node == nullptr)
437 return;
438 node = node->parent;
439 while (node != nullptr) {
440 if (node->isBalanced()) {
441 //如果节点平衡，则对其更新高度
442 node->updateHeight();
443 } else {
444 //此时对第一个不平衡节点操作，使其平衡
445 rebalance(node);
446 //整棵树恢复平衡后,跳出循环
447 break;
448 }
449 node = node->parent;
450 }
451 }
452
453 void add(Element e, int (*cmp_)(Element e1, Element e2)) {
454 //当树为空时，添加的节点作为树的根节点
455 if (root_ == nullptr) {
456 root_ = new NODE(e, nullptr);
457 size_++;
458 //插入一个根节点之后进行调整
459 afterAdd(root_);
460 return;
461 }
462 //当添加的节点不是第一个节点
463 NODE *parent = root_;
464 NODE *node = root_;
465 int cmp = 0; //比较结果
466 while (node != nullptr) {
467 parent = node; //保存父节点
468 cmp = cmp_(e, node->e); //由函数指针来比较
469 if (cmp > 0) {
470 node = node->right; //添加的元素大于节点中的元素
471 } else if (cmp < 0) {
472 node = node->left; //添加的元素小于节点中的元素
473 } else {
474 node->e = e; //相等时就覆盖
475 return; //添加的元素等于节点中的元素,直接返回
476 }
477 }
478 //判断要插入父节点的哪个位置
479 NODE *newNode = new NODE(e, parent); //为新元素创建节点
480 if (cmp > 0) {
481 parent->right = newNode; //添加的元素大于节点中的元素
482 } else {
483 parent->left = newNode; //添加的元素小于节点中的元素
484 }
485 size_++;
486 //添加一个新节点之后进行调整
487 afterAdd(newNode);
488 }
489
490 void afterRemove(NODE *node) {
491 //删除node之后的调整
492 if (node == nullptr)
493 return;
494 node = node->parent;
495 while (node != nullptr) {
496 if (node->isBalanced()) {
497 //如果节点平衡，则对其更新高度
498 node->updateHeight();
499 } else {
500 //此时对不平衡节点操作，使其平衡
501 rebalance(node);
502 }
503 node = node->parent;
504 }
505 }
506
507 void remove(NODE *node_) {
508 //删除某一节点
509 if (node_ == nullptr)
510 return;
511 size_--;
512 //优先删除度为2的节点
513 if (node_->hasTwoChildren()) {
514 NODE *pre = successor(node_); //找到node_的后继节点
515 node_->e = pre->e; //用后继节点的值覆盖度为2的节点的值
516 //删除后继节点(后继节点的度只能为1或0)
517 node_ = pre;
518 }
519 //此时node_的度必然为0或1
520 NODE *replacement = node_->left != nullptr ? node_->left : node_->right;
521 if (replacement != nullptr) { //node_的度为1
522 replacement->parent = node_->parent;
523 if (node_->parent == nullptr) //度为1的根节点
524 root_ = replacement;
525 else if (node_->parent->left == node_)
526 node_->parent->left = replacement;
527 else
528 node_->parent->right = replacement;
529 //所有删除操作准备完成，准备释放节点内存前进行平衡操作
530 afterRemove(node_);
531 delete node_;
532 } else if (node_->parent == nullptr) { //node_是叶子节点，也是根节点
533 root_ = nullptr;
534 //所有删除操作准备完成，准备释放节点内存前进行平衡操作
535 afterRemove(node_);
536 delete node_;
537 } else { //node_是叶子节点，但不是根节点
538 if (node_->parent->left == node_)
539 node_->parent->left = nullptr;
540 else
541 node_->parent->right = nullptr;
542 //所有删除操作准备完成，准备释放节点内存前进行平衡操作
543 afterRemove(node_);
544 delete node_;
545 }
546 }
547
548 void preorderTraversal(NODE *node, bool &stop,
549 bool (*visitor)(Element &e)) {
550 //递归实现前序遍历
551 if (node == nullptr || stop == true)
552 return;
553 stop = visitor(node->e);
554 preorderTraversal(node->left, stop, visitor);
555 preorderTraversal(node->right, stop, visitor);
556 }
557
558 void inorderTraversal(NODE *node, bool &stop, bool (*visitor)(Element &e)) {
559 //递归实现中序遍历
560 if (node == nullptr || stop == true)
561 return;
562 inorderTraversal(node->left, stop, visitor);
563 if (stop == true)
564 return;
565 stop = visitor(node->e);
566 inorderTraversal(node->right, stop, visitor);
567 }
568
569 void postorderTraversal(NODE *node, bool &stop,
570 bool (*visitor)(Element &e)) {
571 //递归实现后序遍历
572 if (node == nullptr || stop == true)
573 return;
574 postorderTraversal(node->left, stop, visitor);
575 postorderTraversal(node->right, stop, visitor);
576 if (stop == true)
577 return;
578 stop = visitor(node->e);
579 }
580
581 void levelOrderTraversal(NODE *node, bool (*visitor)(Element &e)) {
582 if (node == nullptr)
583 return;
584 using namespace std;
585 queue<NODE*> q;
586 q.push(node);
587 while (!q.empty()) {
588 NODE *node = q.front();
589 if (visitor(node->e) == true)
590 return;
591 if (node->left != nullptr)
592 q.push(node->left);
593 if (node->right != nullptr)
594 q.push(node->right);
595 q.pop();
596 }
597 }
598
599 int height(NODE *node) {
600 //某一节点的高度
601 return node->height;
602 }
603
604 bool isComplete(NODE *node) {
605 if (node == nullptr)
606 return false;
607 using namespace std;
608 queue<NODE*> q;
609 q.push(node);
610 bool leaf = false; //判断接下来的节点是否为叶子节点
611 while (!q.empty()) {
612 NODE *node = q.front();
613 if (leaf && !node->isLeaf()) //判断叶子节点
614 return false;
615 if (node->left != nullptr) {
616 q.push(node->left);
617 } else if (node->right != nullptr) { //node->left == nullptr && node->right != nullptr
618 return false;
619 }
620 if (node->right != nullptr) {
621 q.push(node->right);
622 } else { //node->right==nullptr
623 leaf = true;
624 }
625 q.pop();
626 }
627 return true;
628 }
629
630 };
631
632 template<typename Element>
633 BinarySearchTree<Element>::BinarySearchTree(int (*cmp)(Element e1, Element e2)) :
634 size_(0), root_(nullptr), cmp_(cmp) {
635 //树的构造函数
636 }
637
638 template<typename Element>
639 BinarySearchTree<Element>::~BinarySearchTree() {
640 // 析构函数
641 clear();
642 }
643
644 template<typename Element>
645 inline int BinarySearchTree<Element>::size() {
646 //返回元素个数
647 return size_;
648 }
649
650 template<typename Element>
651 inline bool BinarySearchTree<Element>::isEmpty() {
652 //判断是否为空树
653 return size_ == 0;
654 }
655
656 #endif /* SRC_BINARYSEARCHTREE_H_ */
main方法
1 /*
2 * main.cpp
3 *
4 * Created on: 2020年1月29日
5 * Author: LuYonglei
6 */
7
8 #include "BinarySearchTree.h"
9 #include <iostream>
10 #include <time.h>
11
12 using namespace std;
13
14 template<typename Element>
15 int compare(Element e1, Element e2) {
16 //比较函数,相同返回0,e1<e2返回-1,e1>e2返回1
17 return e1 == e2 ? 0 : (e1 < e2 ? -1 : 1);
18 }
19
20 template<typename Elemnet>
21 bool visitor(Elemnet &e) {
22 cout << e << " ";
23 cout << endl;
24 return false; //若返回true，则在遍历时会退出
25 }
26
27 int main(int argc, char **argv) {
28 BinarySearchTree<double> a(compare);
29 // a.add(85);
30 // a.add(19);
31 // a.add(69);
32 // a.add(3);
33 // a.add(7);
34 // a.add(99);
35 // a.add(95);
36 // a.add(2);
37 // a.add(1);
38 // a.add(70);
39 // a.add(44);
40 // a.add(58);
41 // a.add(11);
42 // a.add(21);
43 // a.add(14);
44 // a.add(93);
45 // a.add(57);
46 // a.add(4);
47 // a.add(56);
48 clock_t start = clock();
49 for (int i = 0; i < 1000000; i++) {
50 a.add(i);
51 }
52 for (int i = 0; i < 1000000; i++) {
53 a.remove(i);
54 }
55 // a.inorderTraversal(visitor);
56 clock_t end = clock();
57 cout << end - start << endl;
58 // cout <<a.height()<< endl;
59 // cout << a.isComplete() << endl;
60 // a.remove(7);
61 // a.clear();
62 // a.levelOrderTraversal(visitor);
63 // cout << endl;
64 // cout<<a.contains(0)<<endl;
65 }
加载全部内容