二叉树之AVL树

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

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