一、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_
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 }
