• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号
登陆 注册

平衡有序二叉树(AVLTree)的C++实现

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

　　平衡二叉树是一个重要的数据结构，它有很均衡的插入、删除以及查询性能（时间复杂度都是O(logn)）。Linux2.4以前的内核中，虚拟内存管理中用的容器就是AVL Tree，之后的版本都改成了RBTree即红黑树。AVL Tree对平衡的要求是比较严格的，它要求左右子数之间的长度差不能大于1，也正由于它的严格导致了AVL Tree的统计性能没有RBTree好。AVL Tree在插入或者删除节点时候出现不平衡情况，根据具体情况进行一次或者多次单旋或者双旋就可以使整棵树达到平衡。具体的旋转规则看这里，删除节点的算法看这里。下面是我根据AVL树的规则用C++实现的代码：

  1 #ifndef        __AVLTREE_H__
  2 #define        __AVLTREE_H__
  3 
  4 #include <stdlib.h>
  5 #include <iostream>
  6 
  7 struct AVLNode
  8 {
  9     int nData;
 10     AVLNode* pLeft;
 11     AVLNode* pRight;
 12     AVLNode* pParent;
 13     int nHeight;
 14 };
 15 
 16 class AVLTree
 17 {
 18 public:
 19     AVLTree() : pRoot(NULL), nNodeCount(0){}
 20     ~AVLTree(){ DeleteTree(&pRoot); }
 21 public:
 22     int Insert(int nData);
 23     int Delete(int nData);
 24     int Find(int nData) const;
 25     int GetNodeCount() const;
 26     void Display() const;
 27 
 28 private:
 29     int Max(int a, int b) const;
 30     int Height(const AVLNode* pNode) const;
 31     AVLNode* CreateNode(int nData);
 32     AVLNode* DeleteNode(int nData, AVLNode* pNode);
 33     AVLNode* BalanceAdjust(AVLNode* pNode);
 34     AVLNode* RotateLeft(AVLNode* pNode);
 35     AVLNode* RotateRight(AVLNode* pNode);
 36     AVLNode* RotateLeftRight(AVLNode* pNode);
 37     AVLNode* RotateRightLeft(AVLNode* pNode);
 38     void DeleteTree(AVLNode** ppRoot);
 39     void PrintTree(AVLNode* pNode) const;
 40 
 41     AVLTree(const AVLTree&) {}
 42     AVLTree& operator=(const AVLTree&) {}
 43 
 44 private:
 45     AVLNode* pRoot;
 46     int nNodeCount;
 47 };
 48 
 49 int AVLTree::Max(int a, int b) const
 50 {
 51     return (a > b ? a : b);
 52 }
 53 
 54 int AVLTree::Height(const AVLNode* pNode) const
 55 {
 56     if (NULL == pNode)
 57         return -1;
 58 
 59     return pNode->nHeight;
 60 }
 61 
 62 int AVLTree::Insert(int nData)
 63 {
 64     if(pRoot == NULL)
 65     {
 66         pRoot = CreateNode(nData);
 67 
 68         return nNodeCount;
 69     }
 70 
 71     AVLNode* pInsertNode = pRoot;
 72 
 73     while(pInsertNode != NULL)
 74     {
 75         if(nData < pInsertNode->nData)
 76         {
 77             if(pInsertNode->pLeft == NULL)
 78             {
 79                 pInsertNode->pLeft = CreateNode(nData);
 80                 pInsertNode->pLeft->pParent = pInsertNode;
 81 
 82                 pRoot = BalanceAdjust(pInsertNode->pLeft);
 83                 break;
 84             }
 85 
 86             pInsertNode = pInsertNode->pLeft;
 87         }
 88         else if(nData > pInsertNode->nData)
 89         {
 90             if(pInsertNode->pRight == NULL)
 91             {
 92                 pInsertNode->pRight = CreateNode(nData);
 93                 pInsertNode->pRight->pParent = pInsertNode;
 94 
 95                 pRoot = BalanceAdjust(pInsertNode->pRight);
 96                 break;
 97             }
 98 
 99             pInsertNode = pInsertNode->pRight;
100         }
101         else
102         {
103             return nNodeCount;
104         }
105     }
106 
107     return nNodeCount;
108 }
109 
110 int AVLTree::Delete(int nData)
111 {
112     //std::cout << "Delete nData = " << nData << std::endl;
113     //std::cout << "pNode->nData = " << pNode->nData << std::endl;
114     //std::cout << "pPNode->nData = " << pPNode->nData << std::endl;
115 
116     AVLNode* pCurNode = pRoot;
117 
118     while(pCurNode != NULL)
119     {
120         if(nData > pCurNode->nData)
121         {
122             pCurNode = pCurNode->pRight;
123         }
124         else if(nData < pCurNode->nData)
125         {
126             pCurNode = pCurNode->pLeft;
127         }
128         else
129         {
130             pRoot = DeleteNode(nData, pCurNode);
131             break;
132         }
133     }
134 
135 
136     if(pCurNode == NULL)
137         std::cout << "没有找到元素 nData = " << nData << std::endl;
138     //int x;
139     //std::cin >> x;
140 
141     return nNodeCount;//没有找到要删除的元素    
142 }
143 
144 AVLNode* AVLTree::DeleteNode(int nData, AVLNode* pNode)
145 {
146     nNodeCount--;
147 
148     if(pNode->pLeft && pNode->pRight)//删除节点有左右子树
149     {
150         AVLNode* pLMaxNode = pNode->pLeft;//删除节点左子树中最大的节点
151         AVLNode* pLMaxPNode = pNode;//删除节点左子树中最大节点的父节点
152 
153         //将删除节点左孩子的最大节点替换删除节点,然后删除该节点
154         if(pLMaxNode->pRight == NULL)
155         {
156             pNode->nData = pLMaxNode->nData;
157             pNode->pLeft = pLMaxNode->pLeft;
158 
159             if(pLMaxNode->pLeft != NULL)
160                 pLMaxNode->pLeft->pParent = pNode;
161         }
162         else
163         {
164             while(pLMaxNode->pRight)
165             {
166                 pLMaxPNode = pLMaxNode;
167                 pLMaxNode = pLMaxNode->pRight;
168             }
169             pNode->nData = pLMaxNode->nData;
170 
171             if(pLMaxNode == pLMaxPNode->pRight)//将替换后的删除节点删除
172                 pLMaxPNode->pRight = pLMaxNode->pLeft;
173             else if(pLMaxNode == pLMaxPNode->pLeft)
174                 pLMaxPNode->pLeft = NULL;
175         }
176         
177         delete pLMaxNode;
178 
179         return BalanceAdjust(pLMaxPNode);
180     }
181     else if(pNode->pLeft)//删除节点只有左子树
182     {
183         AVLNode* pLeft = pNode->pLeft;
184 
185         pNode->nData = pLeft->nData;
186 
187         pNode->pLeft = pLeft->pLeft;
188         if (pLeft->pLeft != NULL)
189             pLeft->pLeft->pParent = pNode;
190 
191         pNode->pRight = pLeft->pRight;
192         if (pLeft->pRight != NULL)
193             pLeft->pRight->pParent = pNode;
194         
195         delete pLeft;
196 
197         return BalanceAdjust(pNode);
198     }
199     else if(pNode->pRight)//删除节点只有右子树
200     {
201         AVLNode* pRight = pNode->pRight;
202 
203         pNode->nData = pRight->nData;
204 
205         pNode->pLeft = pRight->pLeft;
206         if (pRight->pLeft != NULL)
207             pRight->pLeft->pParent = pNode;
208 
209         pNode->pRight = pRight->pRight;
210         if (pRight->pRight != NULL)
211             pRight->pRight->pParent = pNode;
212         
213         delete pRight;
214 
215         return BalanceAdjust(pNode);
216     }
217     else//删除节点没有子树
218     {
219         AVLNode* pPNode = pNode->pParent;
220 
221         if(pPNode->pLeft == pNode)
222             pPNode->pLeft = NULL;
223         else if(pPNode->pRight == pNode)
224             pPNode->pRight = NULL;
225 
226         delete pNode;
227 
228         return BalanceAdjust(pPNode);
229     }
230 }
231 
232 AVLNode* AVLTree::BalanceAdjust(AVLNode* pNode)
233 {
234     AVLNode* pRoot;
235     AVLNode* pPNode;
236     
237     while(pNode != NULL)//删除节点的子节点进行平衡
238     {
239         pPNode = pNode->pParent;
240 
241         bool bIsLeft = false;
242         if(pPNode != NULL && pNode == pPNode->pLeft)
243             bIsLeft = true;
244 
245         pNode->nHeight = Max(Height(pNode->pLeft), Height(pNode->pRight)) + 1;
246 
247         if (Height(pNode->pLeft) - Height(pNode->pRight) == 2)    // AVL树不平衡  执行LL型或者LR型旋转
248         {
249             if (Height(pNode->pLeft->pLeft) - Height(pNode->pLeft->pRight) == -1)
250                 pNode = RotateLeftRight(pNode);
251             else 
252                 pNode = RotateLeft(pNode);
253 
254             if(pPNode != NULL && bIsLeft)
255                 pPNode->pLeft = pNode;
256             else if(pPNode != NULL)
257                 pPNode->pRight = pNode;
258         }
259         else if(Height(pNode->pLeft) - Height(pNode->pRight) == -2)    // AVL树不平衡  执行RR型或者RL型旋转
260         {
261             if (Height(pNode->pRight->pLeft) - Height(pNode->pRight->pRight) == 1)
262                 pNode = RotateRightLeft(pNode);
263             else
264                 pNode = RotateRight(pNode);
265 
266             if (pPNode != NULL && bIsLeft)
267                 pPNode->pLeft = pNode;
268             else if(pPNode != NULL)
269                 pPNode->pRight = pNode;
270         }
271 
272         pRoot = pNode;
273         pNode = pPNode;
274     }
275 
276     return pRoot;
277 }
278 
279 AVLNode* AVLTree::CreateNode(int nData)
280 {
281     nNodeCount++;
282 
283     AVLNode* pNewNode = new AVLNode();
284     pNewNode->nData = nData;
285     pNewNode->nHeight = 0;
286     pNewNode->pLeft = pNewNode->pRight = NULL;
287 
288     return pNewNode;
289 }
290 
291 int AVLTree::Find(int nData) const
292 {
293     AVLNode* pFindNode = pRoot;
294     while(pFindNode)
295     {
296         if(nData < pFindNode->nData)
297             pFindNode = pFindNode->pLeft;
298         else if(nData > pFindNode->nData)
299             pFindNode = pFindNode->pRight;
300         else
301             return pFindNode->nData;
302     }
303     
304     return -1;
305 }
306 
307 AVLNode* AVLTree::RotateLeft(AVLNode* pNode)//左单
308 {
309     AVLNode* pLeftChild;
310 
311     pLeftChild = pNode->pLeft;
312     pNode->pLeft = pLeftChild->pRight;
313     pLeftChild->pRight = pNode;
314 
315     pLeftChild->pParent = pNode->pParent;
316     pNode->pParent = pLeftChild;
317 
318     if(pNode->pLeft)
319         pNode->pLeft->pParent = pNode;
320 
321     // 结点的位置改变,节点高度要重新计算
322     pNode->nHeight = Max(Height(pNode->pLeft), Height(pNode->pRight)) + 1;
323     pLeftChild->nHeight = Max(Height(pLeftChild->pLeft), pNode->nHeight) + 1;
324 
325     return pLeftChild;
326 }
327 
328 AVLNode* AVLTree::RotateRight(AVLNode* pNode)//右单
329 {
330     AVLNode* pRightChild;
331 
332     pRightChild = pNode->pRight;
333     pNode->pRight = pRightChild->pLeft;
334     pRightChild->pLeft = pNode;
335 
336     pRightChild->pParent = pNode->pParent;
337     pNode->pParent = pRightChild;
338 
339     if(pNode->pRight)
340         pNode->pRight->pParent = pNode;
341 
342     // 结点的位置改变,节点高度要重新计算
343     pNode->nHeight = Max(Height(pNode->pLeft), Height(pNode->pRight)) + 1;
344     pRightChild->nHeight = Max(Height(pRightChild->pRight), pNode->nHeight) + 1;
345 
346     return pRightChild;
347 }
348 
349 AVLNode* AVLTree::RotateLeftRight(AVLNode* pNode)//左双
350 {
351     pNode->pLeft = RotateRight(pNode->pLeft);
352 
353     return RotateLeft(pNode);
354 }
355 
356 AVLNode* AVLTree::RotateRightLeft(AVLNode* pNode)//右双
357 {
358     pNode->pRight = RotateLeft(pNode->pRight);
359 
360     return RotateRight(pNode);
361 }
362 
363 // 后序遍历树以删除树
364 void AVLTree::DeleteTree(AVLNode** ppRoot)
365 {
366     if (NULL == ppRoot || NULL == *ppRoot)
367         return;
368 
369     DeleteTree(&((*ppRoot)->pLeft));
370     DeleteTree(&((*ppRoot)->pRight));
371     delete *ppRoot;
372     *ppRoot = NULL;
373 }
374 
375 int AVLTree::GetNodeCount() const
376 {
377     return nNodeCount;
378 }
379 
380 void AVLTree::Display() const
381 {
382      PrintTree(this->pRoot);
383 }
384 
385 void AVLTree::PrintTree(AVLNode* pNode) const
386 {
387     if (NULL == pRoot)
388         return;
389 
390     if (NULL == pNode)
391     {
392         return;
393     }
394 
395     static int n = 0;
396     
397     if(pNode == pRoot)
398     {
399         std::cout << "[" << ++n << "]nData = " << pNode->nData << ",nParentData= 0 ,";
400 
401         if(pNode->pLeft)
402             std::cout << "nLeftData= " << pNode->pLeft->nData << " ,";
403         if(pNode->pRight)
404             std::cout << "nRightData= " << pNode->pRight->nData << " ,";
405 
406         std::cout << "nHeight = " << pNode->nHeight << std::endl;
407     }
408     else
409     {
410         std::cout << "[" << ++n << "]nData = " << pNode->nData << ",nParentData= " << pNode->pParent->nData << " ,";
411 
412         if(pNode->pLeft)
413             std::cout << "nLeftData= " << pNode->pLeft->nData << " ,";
414         if(pNode->pRight)
415             std::cout << "nRightData= " << pNode->pRight->nData << " ,";
416 
417         std::cout << "nHeight = " << pNode->nHeight << std::endl;
418     }
419     PrintTree(pNode->pLeft);
420     PrintTree(pNode->pRight);
421 }
422 #endif        //__AVLTREE_H__

　　将上面的文件复制保存成文件AVLTree.h。然后将下面的复制到Test.cpp文件中。Test.cpp文件是简单的测试案例。

 1 #include "AVLTree.h"
 2 #include <iostream>
 3 #include <exception>
 4 
 5 int main()
 6 {
 7     try
 8     {
 9         AVLTree avl;
10         for(int i = 1; i < 10; i++)
11         {
12             avl.Insert(i);
13         }
14         
15         avl.Delete(4);
16         avl.Display();
17     }
18     catch (std::exception& e)
19     {
20         std::cout << e.what() << std::endl;
21     }
22 }

　　输入g++ -o Test Test.cpp然后回车就可以编译运行了。运行结果如下：

 1 [kiven@localhost Test]$ g++ -o Test Test.cpp
 2 [kiven@localhost Test]$ ./Test
 3 [1]nData = 3,nParentData= 0 ,nLeftData= 2 ,nRightData= 6 ,nHeight = 3
 4 [2]nData = 2,nParentData= 3 ,nLeftData= 1 ,nHeight = 1
 5 [3]nData =

鲜花
握手
雷人
路过
鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
More+
上一篇：
[iphone开发]Objective-C学习笔记一:Objective-C语言特性发布时间：2022-07-14
下一篇：
C++返回引用的函数发布时间：2022-07-14
热门推荐
More+
热门话题
More+
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服（服务时间 9:00～18:00）

在线QQ客服
地址：深圳市南山区西丽大学城创智工业园
电邮：jeky_zhao#qq.com
移动电话：139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap