AI 助理
备案控制台
开发者社区 云计算 文章 正文

AVL树探秘

2015-11-02 914
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 一、AVL树 　　AVL树是一种平衡查找树，在前面的两篇文章：二叉搜索树 和 红黑树 中都提到过。由于二叉搜索树在某些特殊情况下是不平衡的（任意一个结点深度过大），因此其一些动态集合操作在最坏情况下的时间复杂度为O(n)。

一、AVL树

　　AVL树是一种平衡查找树，在前面的两篇文章：二叉搜索树 和 红黑树 中都提到过。由于二叉搜索树在某些特殊情况下是不平衡的（任意一个结点深度过大），因此其一些动态集合操作在最坏情况下的时间复杂度为O(n)。因此提出一些对二叉搜索树效率改进的树结构使最坏时间复杂度降为O(lgn)，AVL树和红黑树就是其中的代表，除此之外，还有一些如AA-tree、B-tree、2-3-tree等。使不平衡树变平衡最关键的是找到“平衡条件”，我们已经在前面一篇文章中详述了红黑树的平衡条件是：对节点进行着色，并约束从根节点到任何叶子节点的长度，其中，约定了5条规定，稍显复杂。而AVL树的平衡条件则显得格外简单：只用保证左右子树的高度不超过1即可。

二、AVL树的实现

1、数据结构

节点类：因为需要控制节点的高度，所以高度是一个属性。指针域包括left、right，parent可以包括也可以不要，本文的实现中，我们包括parent。

struct AVLNode {
        AVLNode        *Parent;
        AVLNode        *Left;
        AVLNode        *Right;
        int            m_nHeight;
        int            m_nValue;
    };

2、节点的平衡

当插入新的节点或者删除节点时，会导致树的不平衡，即其中有节点的左右子树的高度相差>1，这个时候就需要调节树使之平衡。可能出现不平衡的情况总共有以下几种：

////////////////////////////////////////

       a 　　a 　　a 　　a
      /  　　/     　 \   　 \
    b   　　b      　  b   　b
   /    　　 \    　　 /     　 \
 c       　　c   　　c       　　c
LL       　 LR  　　RL      　 RR 

//////////////////////////////////////

　　总共就只会出现这四种情况，对这四种情况的分类很多书上有各自的说法。其中1、4和2、3是对称的，我们用LL、LR、RL、RR来分别表示，要使这几种情况平衡，我们只用做简单的旋转操作就OK了，针对1、4，有的说法是做单旋，有的说法是外旋，而2、3，则做双旋或内旋，不管是哪种说法，其本质是不变的。在我们的实现中，采用单旋和双旋，双旋就是做两次单旋：

//单旋
void _LeftRotation( AVLNode *node );
void _RightRotation( AVLNode *node );

//双旋
void _LeftRightRotation( AVLNode *node );
void _RightLeftRotation( AVLNode *node );

3、平衡的修复

　　在插入节点和删除节点的时候，会破坏树的平衡条件，这个时候就需要修复。我们采用尽可能少地改动原有代码的原则来修复，这个原则和红黑树的修复操作是一致的，即插入和删除操作我们依然沿用二叉搜索树的实现，只在后面添加修复的代码即可。

　　如何修复？首先，插入和删除会破坏节点的高度，所以，应更新结点的高度；其次，插入和删除破坏了树中某些节点的平衡，所以，应针对上面四种情况分别平衡节点。所以，这里就需要两个函数：一个更新结点高度的函数UpdateHeight( AVLNode *node )；一个平衡节点的函数： BalanceNode( AVLNode *node )。

void AVLTree::_UpdateHeight( AVLNode *node )
{
    AVLNode *l = node->Left, *r = node->Right;

    if ( l && r )
        node->m_nHeight = max( l->m_nHeight, r->m_nHeight ) + 1;
    else if ( l )
        node->m_nHeight = l->m_nHeight + 1;
    else if ( r )
        node->m_nHeight = r->m_nHeight + 1;
    else node->m_nHeight = 0;
}

 

 1 //////////////////////////////////////////////////////////////////////////
 2 //        a    a    a    a
 3 //       /   /     \   \
 4 //    b   b       b   b
 5 //   /     \     /     \
 6 //  c       c   c       c
 7 // LL       LR  RL      RR
 8 //////////////////////////////////////////////////////////////////////////
 9 void AVLTree::_BalanceNode( AVLNode *node )
10 {
11     int nBlance = _GetBalanceFactor( node );
12     if ( nBlance > 1 ) { //L
13         //(1)
14         //if ( _GetBalanceFactor( node->Left ) < 0 ) //LR 
15         //    _LeftRightRotation( node ); //双旋
16         //else _RightRotation( node ); //LL //单旋
17 
18         //(2)
19         if ( _GetBalanceFactor( node->Left ) < 0 )
20             _LeftRotation( node->Left );
21         _RightRotation( node );
22     }
23     if ( nBlance < -1 ) { //R
24         if ( _GetBalanceFactor( node ) > 0 ) { //RL
25             _RightRotation( node->Right );
26         }
27         _LeftRotation( node );
28     }
29 }
30 
31 //平衡因子(左右子树的高度差)
32 int AVLTree::_GetBalanceFactor( AVLNode *node )
33 {
34     AVLNode *l = node->Left, *r = node->Right;
35 
36     if ( l && r )
37         return l->m_nHeight - r->m_nHeight;
38     else if ( l )
39         return l->m_nHeight + 1;
40     else if ( r )
41         return -r->m_nHeight - 1;
42     else return 0;
43 }

基本上该注意的点都提到了，下面附上详细代码实现：

 1 #ifndef __AVL_TREE_H_
 2 #define __AVL_TREE_H_
 3 
 4 class AVLTree 
 5 {
 6 private:
 7     struct AVLNode {
 8         AVLNode        *Parent;
 9         AVLNode        *Left;
10         AVLNode        *Right;
11         int            m_nHeight;
12         int            m_nValue;
13     };
14 public:
15     AVLTree(AVLNode *root = NULL):m_pRoot(root) {}
16     ~AVLTree() {
17         _RecursiveDeleteNode(m_pRoot);
18     }
19 
20     bool Search( const int search_value ) const;
21     bool Insert( const int value );
22     bool Delete( const int delete_value );
23 
24     void Print() const;
25 
26 private:
27     void _RecursiveDeleteNode(AVLNode *node) {
28         if ( node ) {
29             _RecursiveDeleteNode( node->Left );
30             _RecursiveDeleteNode( node->Right );
31             delete node;
32         }
33         node = NULL;
34     }
35 
36     void _DeleteNode( AVLNode *delete_node );
37     void _Delete_Transplant( AVLNode *unode, AVLNode *vnode );
38     void _InsertNode( const int insert_value );
39     AVLNode * _SearchNode( AVLNode *node, const int search_value ) const;
40 
41     //单旋
42     void _LeftRotation( AVLNode *node );
43     void _RightRotation( AVLNode *node );
44 
45     //双旋
46     void _LeftRightRotation( AVLNode *node );
47     void _RightLeftRotation( AVLNode *node );
48 
49     AVLNode* Minimum( AVLNode *node );
50 
51     //树高
52     int _Height ( AVLNode *node );
53     void _UpdateHeight( AVLNode *node );
54     //平衡因子
55     int _GetBalanceFactor( AVLNode *node );
56     //平衡失去平衡的节点
57     void _BalanceNode( AVLNode *node );
58 
59     void _Print ( AVLNode *node ) const;
60 
61 private:
62     AVLNode *m_pRoot;
63 
64 };
65 #endif//__AVL_TREE_H_
View Code 
  1 #include <iostream>
  2 #include <algorithm>
  3 using namespace std;
  4 
  5 #include "AVL_Tree.h"
  6 
  7 bool AVLTree::Search( const int search_value ) const
  8 {
  9     return _SearchNode( m_pRoot, search_value ) != NULL;
 10 }
 11 
 12 AVLTree::AVLNode * AVLTree::_SearchNode( AVLNode *node, const int search_value ) const
 13 {
 14     while ( node && search_value != node->m_nValue ) {
 15         if ( search_value < node->m_nValue )
 16             node = node->Left;
 17         else
 18             node = node->Right;
 19     }
 20     return node;
 21 }
 22 
 23 bool AVLTree::Insert( const int value )
 24 {
 25     //该值已存在
 26     if ( Search( value ) )
 27         return false;
 28     else {
 29         _InsertNode( value );
 30         return true;
 31     }
 32 }
 33 
 34 void AVLTree::_InsertNode( const int insert_value )
 35 {
 36     AVLNode *node = m_pRoot;
 37     AVLNode *temp_node = NULL;
 38 
 39     //先找到待插入节点的位置
 40     while ( node ) {
 41         temp_node = node;
 42         node = ( insert_value < node->m_nValue )?node->Left:node->Right;
 43     }
 44 
 45     AVLNode *insert_node = new AVLNode();
 46     insert_node->m_nValue = insert_value;
 47 
 48     insert_node->Parent = temp_node;
 49 
 50     //空树
 51     if ( temp_node == NULL )
 52         m_pRoot = insert_node;
 53     else {
 54         if ( insert_value < temp_node->m_nValue )//左子树
 55             temp_node->Left = insert_node;
 56         else
 57             temp_node->Right = insert_node; //右子树
 58     }
 59     
 60     //更新插入节点的高度和平衡节点
 61     while ( insert_node ) {
 62         _UpdateHeight( insert_node );
 63         _BalanceNode( insert_node );
 64         insert_node = insert_node->Parent;
 65     }
 66 }
 67 
 68 bool AVLTree::Delete( const int delete_value )
 69 {
 70     AVLNode *delete_node = _SearchNode( m_pRoot, delete_value );
 71 
 72     //节点不存在
 73     if ( delete_node == NULL )
 74         return false;
 75     else {
 76         _DeleteNode( delete_node );
 77         return true;
 78     }
 79 }
 80 
 81 void AVLTree::_DeleteNode( AVLNode *delete_node )
 82 {
 83     if ( delete_node->Left == NULL )
 84         _Delete_Transplant( delete_node, delete_node->Right );
 85     else if ( delete_node->Right == NULL )
 86         _Delete_Transplant( delete_node, delete_node->Left );
 87     else {
 88         AVLNode *min_node = Minimum( delete_node->Right );
 89         if ( min_node->Parent != delete_node ) {
 90             _Delete_Transplant( min_node, min_node->Right );
 91             min_node->Right = delete_node->Right;
 92             min_node->Right->Parent = min_node;
 93         }
 94         _Delete_Transplant( delete_node, min_node );
 95         min_node->Left = delete_node->Left;
 96         min_node->Left->Parent = min_node;
 97     }
 98 
 99     //更新结点的高度和平衡节点
100     while ( delete_node ) {
101         _UpdateHeight( delete_node );
102         _BalanceNode( delete_node );
103         delete_node = delete_node->Parent;
104     }
105 }
106 
107 void AVLTree::_Delete_Transplant( AVLNode *unode, AVLNode *vnode )
108 {
109     if ( unode->Parent == NULL )
110         m_pRoot = vnode;
111     else if ( unode == unode->Parent->Left )
112         unode->Parent->Left = vnode;
113     else
114         unode->Parent->Right = vnode;
115     if ( vnode )
116         vnode->Parent = unode->Parent;
117 }
118 
119 AVLTree::AVLNode* AVLTree::Minimum( AVLNode *node )
120 {
121     while ( node->Left )
122         node = node->Left;
123     return node;
124 }
125 
126 //树高
127 int AVLTree::_Height( AVLNode *node )
128 {
129     return node->m_nHeight;
130 }
131 
132 //平衡因子(左右子树的高度差)
133 int AVLTree::_GetBalanceFactor( AVLNode *node )
134 {
135     AVLNode *l = node->Left, *r = node->Right;
136 
137     if ( l && r )
138         return l->m_nHeight - r->m_nHeight;
139     else if ( l )
140         return l->m_nHeight + 1;
141     else if ( r )
142         return -r->m_nHeight - 1;
143     else return 0;
144 }
145 
146 void AVLTree::_UpdateHeight( AVLNode *node )
147 {
148     AVLNode *l = node->Left, *r = node->Right;
149 
150     if ( l && r )
151         node->m_nHeight = max( l->m_nHeight, r->m_nHeight ) + 1;
152     else if ( l )
153         node->m_nHeight = l->m_nHeight + 1;
154     else if ( r )
155         node->m_nHeight = r->m_nHeight + 1;
156     else node->m_nHeight = 0;
157 }
158 
159 //////////////////////////////////////////////////////////////////////////
160 //        a    a    a    a
161 //       /   /     \   \
162 //    b   b       b   b
163 //   /     \     /     \
164 //  c       c   c       c
165 // LL       LR  RL      RR
166 //////////////////////////////////////////////////////////////////////////
167 void AVLTree::_BalanceNode( AVLNode *node )
168 {
169     int nBlance = _GetBalanceFactor( node );
170     if ( nBlance > 1 ) { //L
171         //(1)
172         //if ( _GetBalanceFactor( node->Left ) < 0 ) //LR 
173         //    _LeftRightRotation( node ); //双旋
174         //else _RightRotation( node ); //LL //单旋
175 
176         //(2)
177         if ( _GetBalanceFactor( node->Left ) < 0 )
178             _LeftRotation( node->Left );
179         _RightRotation( node );
180     }
181     if ( nBlance < -1 ) { //R
182         if ( _GetBalanceFactor( node ) > 0 ) { //RL
183             _RightRotation( node->Right );
184         }
185         _LeftRotation( node );
186     }
187 }
188 
189 //单旋
190 //左旋
191 void AVLTree::_LeftRotation( AVLNode *node )
192 {
193     if ( node->Right == NULL )
194         return;
195 
196     AVLNode *temp_node = node->Right;
197     
198     //补
199     node->Right = temp_node->Left;
200     if ( temp_node->Left )
201         temp_node->Left->Parent = node;
202     
203     //提
204     temp_node->Parent = node->Parent;
205     if ( node->Parent == NULL )
206         m_pRoot = temp_node;
207     else if ( node == node->Parent->Left )
208         node->Parent->Left = temp_node;
209     else node->Parent->Right = temp_node;
210 
211     //降
212     temp_node->Left = node;
213     node->Parent = temp_node;
214 
215     _UpdateHeight( node );
216     _UpdateHeight( temp_node );
217 }
218 
219 //右旋
220 void AVLTree::_RightRotation( AVLNode *node )
221 {
222     if ( node->Left == NULL )
223         return;
224 
225     AVLNode *temp_node = node->Left;
226 
227     //补
228     node->Left = temp_node->Right;
229     if ( temp_node->Right )
230         temp_node->Right->Parent = node;
231 
232     //提
233     temp_node->Parent = node->Parent;
234     if ( node->Parent == NULL )
235         m_pRoot = temp_node;
236     else if ( node == node->Parent->Left )
237         node->Parent->Left = temp_node;
238     else node->Parent->Right = temp_node;
239 
240     //降
241     temp_node->Right = node;
242     node->Parent = temp_node;
243 
244     _UpdateHeight( node );
245     _UpdateHeight( temp_node );
246 }
247 
248 //双旋
249 //LR
250 void AVLTree::_LeftRightRotation( AVLNode *node )
251 {
252     _LeftRotation( node->Left );
253     _RightRotation( node );
254 }
255 
256 //RL
257 void AVLTree::_RightLeftRotation( AVLNode *node )
258 {
259     _RightRotation( node->Right );
260     _RightRotation( node );
261 }
262 
263 void AVLTree::Print() const
264 {
265     _Print(m_pRoot);
266 }
267 //打印
268 void AVLTree::_Print ( AVLNode *node ) const
269 {
270     if ( node->Parent == NULL )
271         cout << "root: " << node->m_nValue << endl;
272     else if ( node == node->Parent->Left ) 
273         cout << "left: " << node->m_nValue << ", parent: " << node->Parent->m_nValue << endl;
274     else cout << "right: " << node->m_nValue << ", parent: " << node->Parent->m_nValue << endl;
275     if ( node->Left )
276         _Print( node->Left );
277     if ( node->Right )
278         _Print( node->Right );
279 }
280 
281 int main()
282 {
283     AVLTree al;
284     for (int i = 1; i < 10; i ++) {
285         al.Insert(i);
286         
287     }
288     al.Print();
289     for (int i = 1; i < 10; i += 2) {
290         al.Delete(i);
291         al.Print();
292     }
293     return 0;
294 }
View Code

 

伍工
目录
相关文章
懒懒学c
|
8月前
|
存储 C++ 容器
c++的学习之路：26、AVL树
c++的学习之路：26、AVL树
懒懒学c
59 0
toKeep
|
8月前
AVL树的原理以及实现
AVL树的原理以及实现
toKeep
73 4
快捷资讯
|
7月前
|
算法 架构师 NoSQL
「AVL平衡树专项」带你领略常用的AVL树与红黑树的奥秘（规则篇）
原先属于X的空结点被A“继承”。如果被删除结点是黑色结点，则可能造成树的黑色高度变化。
快捷资讯
454 0
稻草人敲代码
|
8月前
AVL树的原理及其实现
AVL树的原理及其实现
稻草人敲代码
60 0
Dio夹心小面包
|
8月前
|
存储 C++ 索引
『 C++ 』AVL树详解 ( 万字 )
『 C++ 』AVL树详解 ( 万字 )
Dio夹心小面包
89 0
游客r4atdh62mlxec
|
Java
Java数据结构——平衡二叉树(AVL树)
Java数据结构——平衡二叉树(AVL树)
游客r4atdh62mlxec
270 1
Java数据结构——平衡二叉树(AVL树)
流烟默
|
数据可视化
认真学习数据结构之AVL树
认真学习数据结构之AVL树
流烟默
72 0
枫叶先生_
|
C++ 容器
【C++进阶】五、AVL树
目录 前言 一、AVL树的概念 二、AVL树节点的定义 三、AVL树的插入 四、AVL树的旋转 4.1 左单旋 4.2 右单旋 4.3 左右双旋 4.4 右左双旋 五、AVL树的验证 六、AVL树的性能 七、完整代码
枫叶先生_
107 0
【C++进阶】五、AVL树
水滴技术
|
算法 Java
Java数据结构与算法分析（九）AVL树（平衡二叉树）
AVL（Adelson-Velskii 和 Landis）树是带有平衡条件的二叉查找树，又叫做平衡二叉树。在AVL树中任何节点的两个子树高度差最多为1，所以它又被称为高度平衡树。
水滴技术
116 0
后端开发技术
|
存储 缓存 算法
从二叉查找树到B*树，一文搞懂搜索树的演进！
本文从二分查找讲起，讲解了BST、AVL、红黑树、B树、B+树最后到B*树的演进过程，知其所以然！
后端开发技术
263 0
从二叉查找树到B*树，一文搞懂搜索树的演进！