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

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›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+

10-27 六六分期app的软件客服如何联系？(六六分期

11-06 可心卡盟:win10系统火狐flash插件崩溃怎么

11-06 亲亲特价:怎么删除回收站图标

11-06 济南大学虚拟社区:鲁大师节能降温的具体办

11-06 xlueops.exe:无线网络安装向导

11-06 女斗合众国:win7系统cf与主机连接不稳定怎

11-06 0xc000022-[cf烟雾头]cf怎么调烟雾头

11-06 qizideyouhuo:应用程序无法正常启动0xc0000

11-06 ipz-185:win7系统vcf文件怎么打开

11-06 傻哥蹦迪:win10系统s4怎么打开usb调试

11-06 八神浩树gtaste:回收站清空了怎么恢复

11-06 妖尾之黑色守护:win10系统电脑没有1440x900

11-06 校园至尊魔王小说:win7系统浏览网页时字体

11-06 女斗合众国:win10系统访问共享文件夹提示请

11-06 tokyo hot n0654:恢复win7系统默认字体一招

11-06 雨酷仙境:设置win7系统转移临时文件夹腾出

11-06 阿穆纳伊之杖:win7系统开始菜单在右边还原

11-06 tunespotting:win10系统火狐flash插件总是

11-06 甘尔葛分析师：计谋网站seo关键词暴涨有什

11-06 蔡贵霖: 计谋网站seo关键词暴涨有什么秘密

11-06 博益网首页:ao3网页版进入不了解决方法

11-06 漏斗子专栏: 网站数据分析小白易懂精华篇

11-06 见证双虹怎么做:win7系统开启telnet命令的

11-06 颾狐蝶蜋:系统资源不足无法完成请求的服务

11-06 国光中学校歌:提交网站到alexa查询详细步骤

11-06 西安有情天:静态网页和动态网页的区别

11-06 红木雅尚斋:外部链接构造对网站的好处

11-06 前官礼遇：防止域名劫持–增强域安全性的10

11-06 密传二转答案: 中文分词算法有哪些

11-06 金泉家园邮编:百度快照劫持的表现及应对方

[iphone开发]Objective-C学习笔记一:Objective-C语言特性发布时间：2022-07-14

C++返回引用的函数发布时间：2022-07-14

剪的笔顺,诠释剪的笔画,认识剪的部首

1 六六分期app的软件客服如何联系？(六六分期

六六分期app的软件客服如何联系？不知道吗？加qq群【895510560】即可！标题：六六分期

阅读：19155|2023-10-27

2 可心卡盟:win10系统火狐flash插件崩溃怎么

今天小编告诉大家如何处理win10系统火狐flash插件总是崩溃的问题，可能很多用户都不知

阅读：9981|2022-11-06

3 亲亲特价:怎么删除回收站图标

今天小编告诉大家如何对win10系统删除桌面回收站图标进行设置，可能很多用户都不知道

阅读：8320|2022-11-06

4 济南大学虚拟社区:鲁大师节能降温的具体办

今天小编告诉大家如何对win10系统电脑设置节能降温的设置方法，想必大家都遇到过需要

阅读：8690|2022-11-06

5 xlueops.exe:无线网络安装向导

我们在使用xp系统的过程中,经常需要对xp系统无线网络安装向导设置进行设置，可能很多

阅读：8632|2022-11-06

6 女斗合众国:win7系统cf与主机连接不稳定怎

今天小编告诉大家如何处理win7系统玩cf老是与主机连接不稳定的问题，可能很多用户都不

阅读：9649|2022-11-06

7 0xc000022-[cf烟雾头]cf怎么调烟雾头

电脑对日常生活的重要性小编就不多说了，可是一旦碰到win7系统设置cf烟雾头的问题，很

阅读：8615|2022-11-06

8 qizideyouhuo:应用程序无法正常启动0xc0000

我们在日常使用电脑的时候，有的小伙伴们可能在打开应用的时候会遇见提示应用程序无法

阅读：7994|2022-11-06

9 ipz-185:win7系统vcf文件怎么打开

今天小编告诉大家如何对win7系统打开vcf文件进行设置，可能很多用户都不知道怎么对win

阅读：8647|2022-11-06

10 傻哥蹦迪:win10系统s4怎么打开usb调试

今天小编告诉大家如何对win10系统s4开启USB调试模式进行设置，可能很多用户都不知道怎

阅读：7530|2022-11-06

客服电话

电子邮件

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

请发表评论

全部评论

上一篇：

下一篇：

CVE-2022-30791

solegalli/feature-selection-for-machine-

nvim-lualine/lualine.nvim: A blazing fas

kentcdodds/dom-testing-library-with-anyt

win7系统重装系统初始设置的操作方法

剪的笔顺,诠释剪的笔画,认识剪的部首

六六分期app的软件客服如何联系？(六六分期

florent37/ViewAnimator: A fluent Android

florent37/Shrine-MaterialDesign2: implem

CVE-2020-36276

SimpleSoftwareIO/simple-sms: Send and re

关于我们

产品与服务

解决方案

139-2527-9053