二叉树之AVL树

AVL树

　　引用：https://www.cnblogs.com/skywang12345/

　　详解以后再补充。。。

代码

这是Qt Creator创建的工程

其余代码从此处获取：https://github.com/Duacai/Data-Structure-and-Algorithms/tree/master/Data-Structure/Tree/AVLTree

AVLTree.h

  1 #ifndef AVLTREE_H
  2 #define AVLTREE_H
  3 
  4 #include <iostream>
  5 #include <queue>
  6 #include <iomanip>
  7 
  8 using namespace std;
  9 
 10 namespace Viclib
 11 {
 12 
 13 template <typename T>
 14 class AVLTreeNode
 15 {
 16 public:
 17     T key;
 18     uint16_t height;
 19     AVLTreeNode* left;
 20     AVLTreeNode* right;
 21 
 22     AVLTreeNode(T v, AVLTreeNode* l, AVLTreeNode* r) :
 23         key(v), height(0), left(l), right(r) {}
 24 };
 25 
 26 template <typename T>
 27 class AVLTree
 28 {
 29 private:
 30     AVLTreeNode<T>* mRoot;
 31     uint64_t mCount;
 32 
 33     void preOrder(AVLTreeNode<T>* tree) const;
 34     void inOrder(AVLTreeNode<T>* tree) const;
 35     void postOrder(AVLTreeNode<T>* tree) const;
 36 
 37     void levelOrder(AVLTreeNode<T>* tree) const;
 38 
 39     AVLTreeNode<T>* search(AVLTreeNode<T>* tree, T key) const;
 40     AVLTreeNode<T>* iterativeSearch(AVLTreeNode<T>* tree, T key) const;
 41 
 42     AVLTreeNode<T>* minimum(AVLTreeNode<T>* tree) const;
 43     AVLTreeNode<T>* maximum(AVLTreeNode<T>* tree) const;
 44 
 45     AVLTreeNode<T>* llRotation(AVLTreeNode<T>* tree) const;
 46     AVLTreeNode<T>* rrRotation(AVLTreeNode<T>* tree) const;
 47     AVLTreeNode<T>* lrRotation(AVLTreeNode<T>* tree) const;
 48     AVLTreeNode<T>* rlRotation(AVLTreeNode<T>* tree) const;
 49 
 50     AVLTreeNode<T>* insert(AVLTreeNode<T>* &tree, T key);
 51     AVLTreeNode<T>* remove(AVLTreeNode<T>* &tree, AVLTreeNode<T>* del);
 52 
 53     void printGraph(const void* mRoot, uint16_t m_keyStrLen) const;
 54     void printTree(AVLTreeNode<T> const* const tree, bool firstNode) const;
 55 
 56     void destroy(AVLTreeNode<T>* &tree) const;
 57     uint16_t height(AVLTreeNode<T>* tree) const;
 58 
 59 public:
 60     AVLTree();
 61     virtual ~AVLTree();
 62 
 63     void preOrder() const;
 64     void inOrder() const;
 65     void postOrder() const;
 66 
 67     void levelOrder() const;
 68 
 69     AVLTreeNode<T>* search(T key) const;            // 递归版
 70     AVLTreeNode<T>* iterativeSearch(T key) const;    // 非递归版
 71 
 72     T minimum() const;
 73     T maximum() const;
 74 
 75     void insert(T key);
 76     bool remove(T key);
 77 
 78     void print() const;                                // 打印结点关系，谁是谁的结点
 79     void printGraph(uint16_t keyStrLen) const;        // 以图形树方式打印关系
 80     void printTree() const;
 81 
 82     void destroy();
 83     uint16_t height() const;
 84 
 85     uint64_t getCount() const;
 86     bool rootIsNullptr() const;
 87 
 88     T getRootKey() const;
 89 };
 90 
 91 template <typename T>
 92 AVLTree<T>::AVLTree() : mRoot(nullptr), mCount(0)
 93 {
 94 }
 95 
 96 template <typename T>
 97 void AVLTree<T>::preOrder(AVLTreeNode<T>* tree) const    // 前序遍历
 98 {
 99     if ( tree != nullptr )
100     {
101         cout << tree->key << " " << flush;
102         preOrder(tree->left);
103         preOrder(tree->right);
104     }
105 }
106 
107 template <typename T>
108 void AVLTree<T>::preOrder() const
109 {
110     preOrder(mRoot);
111     cout << endl;
112 }
113 
114 template <typename T>
115 void AVLTree<T>::inOrder(AVLTreeNode<T>* tree) const    // 中序遍历
116 {
117     if ( tree != nullptr )
118     {
119         inOrder(tree->left);
120         cout << tree->key << " " << flush;
121         inOrder(tree->right);
122     }
123 }
124 
125 template <typename T>
126 void AVLTree<T>::inOrder() const
127 {
128     inOrder(mRoot);
129     cout << endl;
130 }
131 
132 template <typename T>
133 void AVLTree<T>::postOrder(AVLTreeNode<T>* tree) const    // 后续遍历
134 {
135     if ( tree != nullptr )
136     {
137         postOrder(tree->left);
138         postOrder(tree->right);
139         cout << tree->key << " " << flush;
140     }
141 }
142 
143 template <typename T>
144 void AVLTree<T>::postOrder() const
145 {
146     postOrder(mRoot);
147     cout << endl;
148 }
149 
150 template <typename T>
151 void AVLTree<T>::levelOrder(AVLTreeNode<T>* tree) const    // 广度优先
152 {
153     if ( tree != nullptr )
154     {
155         queue<AVLTreeNode<T>*> tmp;
156         tmp.push(tree);
157 
158         while( tmp.size() > 0 )
159         {
160             AVLTreeNode<T>* t = tmp.front();
161 
162             if ( t->left != nullptr )
163                 tmp.push(t->left);
164 
165             if ( t->right != nullptr )
166                 tmp.push(t->right);
167 
168             tmp.pop();
169 
170             cout << t->key << " " << flush;
171         }
172     }
173 }
174 
175 template <typename T>
176 void AVLTree<T>::levelOrder() const
177 {
178     levelOrder(mRoot);
179     cout << endl;
180 }
181 
182 template <typename T>
183 AVLTreeNode<T>* AVLTree<T>::search(AVLTreeNode<T>* tree, T key) const    // 递归版搜索
184 {
185     if ( (tree == nullptr) || (tree->key == key) )
186         return tree;
187 
188     if ( key < tree->key )
189         return search(tree->left, key);
190     else
191         return search(tree->right, key);
192 }
193 
194 template <typename T>
195 AVLTreeNode<T>* AVLTree<T>::search(T key) const
196 {
197     return search(mRoot, key);
198 }
199 
200 template <typename T>
201 AVLTreeNode<T>* AVLTree<T>::iterativeSearch(AVLTreeNode<T>* tree, T key) const    // 非递归版搜索
202 {
203     while ( (tree != nullptr) && (tree->key != key) )
204     {
205         if ( key < tree->key )
206             tree = tree->left;
207         else
208             tree = tree->right;
209     }
210 
211     return tree;
212 }
213 
214 template <typename T>
215 AVLTreeNode<T>* AVLTree<T>::iterativeSearch(T key) const
216 {
217     return iterativeSearch(mRoot, key);
218 }
219 
220 template <typename T>
221 AVLTreeNode<T>* AVLTree<T>::minimum(AVLTreeNode<T>* tree) const
222 {
223     if ( tree == nullptr )
224         return nullptr;
225 
226     while ( tree->left != nullptr )
227         tree = tree->left;
228 
229     return tree;
230 }
231 
232 template <typename T>
233 T AVLTree<T>::minimum() const
234 {
235     AVLTreeNode<T> *ret = minimum(mRoot);
236 //    if ( ret == nullptr )
237 //        THROW_EXCEPTION(EmptyTreeException, "The tree is empty ...");
238 
239     return ret->key;
240 }
241 
242 template <typename T>
243 AVLTreeNode<T>* AVLTree<T>::maximum(AVLTreeNode<T>* tree) const
244 {
245     if ( tree == nullptr )
246         return nullptr;
247 
248     while ( tree->right != nullptr )
249         tree = tree->right;
250 
251     return tree;
252 }
253 
254 template <typename T>
255 T AVLTree<T>::maximum() const
256 {
257     AVLTreeNode<T> *ret = maximum(mRoot);
258 //    if ( ret == nullptr )
259 //        THROW_EXCEPTION(EmptyTreeException, "The tree is empty ...");
260 
261     return ret->key;
262 }
263 
264 template <typename T>
265 AVLTreeNode<T>* AVLTree<T>::llRotation(AVLTreeNode<T>* tree) const            // 左单旋，旋转前左孩子有孩子右孩子没有
266 {
267     AVLTreeNode<T>* ret;
268 
269     ret = tree->left;
270     tree->left = tree->left->right;
271     ret->right = tree;
272 
273     tree->height = max( height(tree->left), height(tree->right) ) + 1;
274     ret->height = max( height(ret->left), height(ret->right) ) + 1;
275 
276     return ret;
277 }
278 
279 template <typename T>
280 AVLTreeNode<T>* AVLTree<T>::rrRotation(AVLTreeNode<T>* tree) const            // 右单旋，旋转前右孩子有孩子左孩子没有
281 {
282     AVLTreeNode<T>* ret;
283 
284     ret = tree->right;
285     tree->right = tree->right->left;
286     ret->left = tree;
287 
288     tree->height = max( height(tree->left), height(tree->right) ) + 1;
289     ret->height = max ( height(ret->left), height(ret->right) ) + 1;
290 
291     return ret;
292 }
293 
294 template <typename T>
295 AVLTreeNode<T>* AVLTree<T>::lrRotation(AVLTreeNode<T>* tree) const            // 左右双旋，先右旋，后左旋；tree左孩子的右孩子有后代，tree右孩子没有后代
296 {
297     tree->left = rrRotation(tree->left);    // 确保多出的后代在左子树的左子树上
298 
299     return llRotation(tree);
300 }
301 
302 template <typename T>
303 AVLTreeNode<T>* AVLTree<T>::rlRotation(AVLTreeNode<T>* tree) const            // 右左双旋，先左旋，后右旋；tree右孩子的左孩子有后代，tree左孩子没有后代
304 {
305     tree->right = llRotation(tree->right);    // 确保多出的后代在右子树的右子树上
306 
307     return rrRotation(tree);
308 }
309 
310 template <typename T>
311 AVLTreeNode<T>* AVLTree<T>::insert(AVLTreeNode<T>* &tree, T key)
312 {
313     if ( tree == nullptr )                                    // 创建新结点，下面的两个else if会最终递归进入此if创建新结点
314     {
315         tree = new AVLTreeNode<T>(key, nullptr, nullptr);
316         ++mCount;
317     }
318     else if ( key < tree->key )                                // 将新结点交给左子树负责插入
319     {
320         tree->left = insert(tree->left, key);                // 注意更新左结点，因为它可能旋转或是新创建的结点
321 
322         if ( height(tree->left) - height(tree->right) == 2)    // 如果插入的左子树超重
323         {
324             if ( key < tree->left->key )
325                 tree = llRotation(tree);                    // 如果插入的位置是左孩子的左孩子，左单旋
326             else
327                 tree = lrRotation(tree);                    // 否则插入的位置是左孩子的右孩子，右单旋；最外层的else保证不会有重复值
328         }
329     }
330     else if ( key > tree->key )                                // 将新结点交给右子树负责插入
331     {
332         tree->right = insert(tree->right, key);
333 
334         if ( height(tree->right) - height(tree->left) == 2 )
335         {
336             if ( key > tree->right->key )
337                 tree = rrRotation(tree);
338             else
339                 tree = rlRotation(tree);
340         }
341     }
342     else                                                    // 结点重复
343         ;//THROW_EXCEPTION(DuplicateDataException, "Can't create duplicate nodes ...");
344 
345     tree->height = max(height(tree->left), height(tree->right)) + 1;
346 
347     return tree;
348 }
349 
350 template <typename T>
351 void AVLTree<T>::insert(T key)
352 {
353     insert(mRoot, key);
354 }
355 
356 template <typename T>
357 AVLTreeNode<T>* AVLTree<T>::remove(AVLTreeNode<T>* &tree, AVLTreeNode<T>* del)
358 {
359     if ( (tree == nullptr) || (del == nullptr) )
360         return nullptr;
361 
362     if ( del->key < tree->key )                            // 交给左子树删除，最终进入最外层else
363     {
364         tree->left = remove(tree->left, del);                        // 更新可能旋转的结点
365 
366         if ( height(tree->right) - height(tree->left) == 2 )        // 删除左子树结点后如果右子树超重
367         {
368             if ( height(tree->right->left) > height(tree->right->right) )
369                 tree = rlRotation(tree);                                // 右左重
370             else
371                 tree = rrRotation(tree);                                // 右右重
372         }
373     }
374     else if ( del->key > tree->key )                    // 交给右子树删除，最终进入最外层else
375     {
376         tree->right = remove(tree->right, del);
377 
378         if ( height(tree->left) - height(tree->right) == 2 )
379         {
380             if ( height(tree->left->right) - height(tree->left->left) == 2 )
381                 tree = lrRotation(tree);
382             else
383                 tree = llRotation(tree);
384         }
385     }
386     else                                                // 找到删除节点
387     {
388         if ( (tree->left != nullptr) && (tree->right != nullptr) )    // 删除点有两个孩子，在较重的分支找替换者
389         {
390             if ( height(tree->left) > height(tree->right) )                // 左孩子重
391             {
392                 AVLTreeNode<T>* lmax = maximum(tree->left);                    // 查找左边最大者用于替换；如果用右边的最小者，当右边没有孩子就会删除自身导致不平衡
393                 tree->key = lmax->key;                                        // 采用值拷贝的方式删除，否则你还要处理子结点
394                 tree->left = remove(tree->left, lmax);                        // 更新可能旋转的结点
395             }
396             else                                                        // 右孩子重
397             {
398                 AVLTreeNode<T>* rmin = minimum(tree->right);
399                 tree->key = rmin->key;
400                 tree->right = remove(tree->right, rmin);
401             }
402         }
403         else                                                        //    删除点孩子不足两个，直接删除并用孩子替换
404         {
405             AVLTreeNode<T>* tmp = tree;
406             tree = (tree->left != nullptr) ? tree->left : tree->right;    // 替换删除结点
407             delete tmp;
408             --mCount;
409         }
410     }
411 
412     if ( tree != nullptr )
413         tree->height = max(height(tree->left), height(tree->right)) + 1;
414 
415     return tree;
416 }
417 
418 template <typename T>
419 bool AVLTree<T>::remove(T key)
420 {
421     bool ret = false;
422     AVLTreeNode<T>* tmp;
423 
424     if ( (tmp = search(mRoot, key)) != nullptr )    // 查找并删除节点
425     {
426         mRoot = remove(mRoot, tmp);                    // remove()的返回值用于不能修改参数的编程语言，函数左边的参数是左值mRoot的引用
427         ret = true;
428     }
429 
430     return ret;
431 }
432 
433 template <typename T>
434 void AVLTree<T>::printGraph(const void* Root, uint16_t m_keyStrLen) const
435 {
436     AVLTreeNode<T>const* node = static_cast<AVLTreeNode<T>const*>(Root);
437     if ( node == nullptr )
438         return;
439 
440     uint16_t height = node->height;            // 要打印的树总高度
441     uint16_t layer = 1;                        // 当前层，root为第一层
442     uint64_t i, index;
443     uint64_t keyStrLen = m_keyStrLen;    // i: 循环变量；index: 当前层最大结点数；keyStrLen: 结点输出占用字符宽度
444     queue<AVLTreeNode<T>const *> q;        // 记录每层的所有节点，包括nullptr
445     q.push(node);
446     cout << "输出树形关系图！！！" << endl;
447     while ( true )
448     {
449         cout << layer << "	" << flush;                                    // 输出当前层号和当前层满节点数
450         AVLTreeNode<T> const* tmp = nullptr;                            // 取出结点变量
451         index = 1ull<<(layer-1);
452         while ( index-- )
453         {
454             tmp = q.front();                                            // 取出结点
455             q.pop();
456             for ( i=0; i<((1ull<<(height-layer))-1ull)*keyStrLen; ++i )    // 结点前的填充
457                 cout << " ";
458             cout << flush;
459 
460             if ( tmp != nullptr )                                        // 打印有效结点
461             {
462                 cout << right << setw(keyStrLen) << setfill('0') << tmp->key << flush;
463 
464                 if ( tmp->left != nullptr )        // 加入左结点
465                     q.push(tmp->left);
466                 else
467                     q.push(nullptr);
468 
469                 if ( tmp->right != nullptr )    // 加入右节点
470                     q.push(tmp->right);
471                 else
472                     q.push(nullptr);
473             }
474             else                                                        // 打印无效结点
475             {
476                 for ( i=0; i<keyStrLen; ++i )
477                     cout << "#";
478                 cout << flush;
479 
480                 q.push(nullptr);                // 如果结点是空的则为其加入两个空子结点
481                 q.push(nullptr);
482             }
483 
484             for ( i=0; i<((1ull<<(height-layer))-1ull)*keyStrLen; ++i )    // 结点后的填充
485                 cout << " ";
486             cout << flush;
487 
488             if ( q.size() != (1ull<<(layer)) )
489                 for ( i=0; i<keyStrLen; ++i )                                // 两节点间填充，因为父节点位于两节点的中间上面，而不是其中一个的上面
490                     cout << " ";
491             else
492                 cout << "	";
493             cout << flush;
494         }
495         cout << layer << endl;                                                    // 输出一层换行
496 
497         if ( ++layer > height )    // while循环出口，当前层大于总高度时退出
498             break;
499     }
500 }
501 
502 template <typename T>
503 void AVLTree<T>::printGraph(uint16_t keyStrLen) const
504 {
505     if ( mRoot == nullptr )
506         return;
507 
508     printGraph(mRoot, keyStrLen);
509 }
510 
511 template <typename T>
512 void AVLTree<T>::printTree(AVLTreeNode<T> const* const tree, bool firstNode) const
513 {
514     if ( tree==nullptr )
515         return;
516 
517     bool static outTag[64] = {false};    // size = max layer limit;
518     uint8_t static layer = 0;
519     uint8_t i;
520     ++layer;
521 
522     if ( layer >= 2 )
523     {
524         for (i=2; i<layer; ++i )
525             if ( outTag[i] )
526                 cout << "|       ";
527             else
528                 cout << "        ";
529         if ( firstNode == true )        // 判断左右结点，非二叉树需要另外处理
530             cout << "L-------" << flush;
531         else
532             cout << "R-------" << flush;
533     }
534     cout << tree->key << endl;
535 
536     for ( i=2-1; i>0; --i)        // 从右往左输出结点，即先打印最右边结点，其次次右边的结点；此循环不输出最左边的结点
537     {
538         if ( (tree->left+i) != nullptr )    // 注意树的子结点指针必须是从左往右依次排列，中间不能有其它变量（left_1,left_2,left_3...left_n）
539         {                                    // 如果你的子结点数量不定，一定要把后面的首个指针设为nullptr
540             outTag[layer] = !firstNode;
541             printTree(tree->right, false);
542         }
543     }
544     if ( tree->left != nullptr )            // 输出最左边的结点
545     {
546         printTree(tree->left, true);
547         outTag[layer] = firstNode;
548     }
549 
550     --layer;
551 }
552 
553 template <typename T>
554 void AVLTree<T>::printTree() const
555 {
556     printTree(mRoot, true);    // 右边参数此时无意义
557 }
558 
559 template <typename T>
560 void AVLTree<T>::destroy(AVLTreeNode<T>* &tree) const
561 {
562     if ( tree == nullptr )
563         return;
564 
565     if ( tree->left != nullptr )
566         destroy(tree->left);
567     else
568         destroy(tree->right);
569 
570     delete tree;
571 }
572 
573 template <typename T>
574 void AVLTree<T>::destroy()
575 {
576     destroy(mRoot);
577     mRoot = nullptr;
578     mCount = 0;
579 }
580 
581 template <typename T>
582 uint16_t AVLTree<T>::height(AVLTreeNode<T>* tree) const
583 {
584     if ( tree != nullptr )
585         return tree->height;
586 
587     return 0;
588 }
589 
590 template <typename T>
591 uint16_t AVLTree<T>::height() const
592 {
593     return height(mRoot);
594 }
595 
596 template <typename T>
597 uint64_t AVLTree<T>::getCount() const
598 {
599     return mCount;
600 }
601 
602 template <typename T>
603 bool AVLTree<T>::rootIsNullptr() const
604 {
605     return mRoot == nullptr;
606 }
607 
608 template <typename T>
609 T AVLTree<T>::getRootKey() const
610 {
611 //    if ( mRoot == nullptr )
612 //        THROW_EXCEPTION(EmptyTreeException, "The tree is empty ...");
613 
614     return mRoot->key;
615 }
616 
617 template <typename T>
618 AVLTree<T>::~AVLTree()
619 {
620     destroy();
621 }
622 
623 }
624 
625 #endif // AVLTREE_H

main.cpp

  1 #include <iostream>
  2 
  3 #include "AVLTree.h"
  4 
  5 #include "Times.h"
  6 
  7 using namespace std;
  8 using namespace Viclib;
  9 
 10 typedef uint64_t templateType;
 11 typedef uint64_t sizeType;
 12 
 13 int main(int argc, char* argv[])
 14 {
 15     sizeType i, len = 5;
 16     //uint16_t keyStrLen = 3;    // 打印结点占用的字符宽度，printGraph(node, keyStrLen)
 17 
 18     if ( argc == 2 )
 19         len = static_cast<sizeType>(atoi(argv[1]));
 20     else {
 21         cout << "请输入结点层数，注意内存大小" << endl;
 22         cin >> len;
 23     }
 24 
 25     timingStart();
 26 
 27     templateType tmp = 0;
 28     AVLTree<templateType>* tree = new AVLTree<templateType>();
 29 
 30     cout << "添加元素：
key	count	layer" << endl;
 31     srand(static_cast<uint32_t>(time(nullptr)));
 32     i = 0;
 33     while ( tree->getCount() < (1ull<<len)-1 )
 34     {
 35         do
 36         {
 37             tmp = static_cast<templateType>(
 38                 static_cast<sizeType>(rand())
 39                 * static_cast<sizeType>(rand())
 40                 * static_cast<sizeType>(rand())
 41                 );
 42         } while(tree->iterativeSearch(tmp));
 43         tree->insert(tmp);
 44         cout << tmp << "	" << ++i << "	" << tree->height() << endl;
 45         if ( tree->height() >= static_cast<int>(len) )    // 限制树的高度
 46             break;
 47     }
 48     cout << endl;
 49 
 50     cout << "先序遍历：" << endl;
 51     tree->preOrder();
 52     cout << endl;
 53     cout << "中序遍历：" << endl;
 54     tree->inOrder();
 55     cout << endl;
 56     cout << "后序遍历：" << endl;
 57     tree->postOrder();
 58     cout << endl;
 59     cout << "广度优先：" << endl;
 60     tree->levelOrder();
 61     cout << endl;
 62 
 63     // 输出树形描述的关系图
 64 //    tree->printGraph(keyStrLen);
 65 //    cout << endl;
 66 
 67     tree->printTree();
 68     cout << endl;
 69 
 70     cout << "最小结点：" << tree->minimum() << endl;
 71     cout << "最大结点：" << tree->maximum() << endl;
 72     cout << "树的高度：" << tree->height() << endl;
 73     cout << "树的结点数：" << tree->getCount() << endl;
 74 
 75     cout << "
开始删除！！！
key	layer" << endl;
 76     while ( !tree->rootIsNullptr() )        // 随机数删除
 77     {
 78 //        tmp = static_cast<templateType>(
 79 //            static_cast<sizeType>(rand())
 80 //            * static_cast<sizeType>(rand())
 81 //            * static_cast<sizeType>(rand())
 82 //            % ( (1ull<<len)-1) );
 83         if ( tree->remove(tree->getRootKey()) )
 84             cout << tmp << "	" << tree->height() << "	" << endl;
 85     }
 86     cout << endl;
 87 
 88     cout << "删除后输出===" << endl;
 89     cout << "树的高度：" << tree->height() << endl;
 90     cout << "树的结点数：" << tree->getCount() << endl;
 91     cout << "中序遍历：" << endl;
 92     tree->inOrder();
 93 
 94     cout << "
销毁AVL树。" << endl;
 95     tree->destroy();
 96     cout << "
树的高度：" << tree->height() << endl;
 97     cout << "树的结点数：" << tree->getCount() << endl;
 98     delete tree;
 99     tree = nullptr;
100 
101     cout << endl;
102     timingEnd();
103     cout << endl;
104 
105     return 0;
106 }