二叉查找树系列六：AVL树

动态符号表可以用二叉查找树表示，最坏情况下，二叉查找树可完全偏斜，高度为n，其平均和最坏查找时间都是O(n)；最好情况下，二叉查找树的结点尽可能靠近根节点，其平均和最坏查找时间都是O(log2n)。因而，为了得到较好的查询效率，最理想的情况是时刻保持树是一棵完全二叉树，然而，为了达到这种要求就会使插入和删除的操作付出很高的代价。对此，人们设计出在高度上相对平衡的二叉查找树，其查找、插入和删除的时间都是O(log2n)。

AVL树是有Adelson-Velskii和Landis提出的，一种在高度上相对平衡的二叉查找树。由于该树的平衡性，其平均和最坏查找时间都是O(log2n)，且插入和删除也只需O(log2n)时间，插入和删除后的树仍是高度上相对平衡的。

（1）AVL树的定义

空二叉树是AVL树，如果T是一棵非空二叉查找树，其左子树为TL，右子树为TR，TL的高度为HL，TR的高度为HR，则T是AVL树当且仅当:

a. TL和TR是AVL树;

b. |HL-HR|<=1.

或者说：AVL树是每个结点的左右子树高度最多差1的二叉查找树。

由斐波那契数可以推出AVL树的高度最多为1.44log(N+2)-1.328，它只比logN多一点。

（2）AVL树的插入

当向AVL树中插入新的结点时，需要更新通向根结点路径上那些结点的所有平衡信息，此外，插入可能会破坏AVL树的平衡特性，通常需要在插入后通过修正来保持AVL树的特性，对此常用的方法是旋转。

假如插入新结点后结点A的两棵子树的高度差为2，那么可以推断插入应是下列四种情况中的一种：

LL：对A的左儿子的左子树进行一次插入

LR：对A的左儿子的右子树进行一次插入

RL：对A的右儿子的左子树进行一次插入

RR：对A的右儿子的右子树进行一次插入

上面的情形中LL和RR是对称的，LR和RL是对称的，对于前者，可以通过单旋转恢复AVL树的特性，对于后者可以通过双旋转恢复AVL树的平衡性。

a. 单旋转

LL情形下：

如下图所示：结点k2不满足AVL平衡特性，左子树比右子树的高度高2。通过调整之后，k1成了树根，二叉查找树的性质又使k2成为了k1的右儿子，Y成为了k2的左儿子，二叉查找树的性质没有被破坏，且AVL的特性也恢复了。

对应的，RR情形的单旋转如下：其中k1成为k2的左儿子，Y成为k1的右儿子

b. 双旋转

LR情形：如果插入是在结点的左儿子的右子树中，那么通过单旋转并不能恢复AVL树的平衡特性，如下图：

此时就需要双旋转，如下图所示，调整的过程中首先找出不平衡点k3，顺着k3依次找出3个点：k3,k1,k2，k2是最后一个点，它将成为旋转后的新的根结点，并根据二叉查找树的性质让k1，k3分别成为k2的左右儿子，B和C分别成为k1和k3的右儿子和左儿子：

对应的，对于RL情形，旋转如下：

（3）AVL树插入C++实现

设计两个类AVLNode和AVLTree，其中AVLTree为AVLNode的友元：

  1 /***********AVLNode.h***********/
  2 #ifndef AVLNODE_H
  3 #define AVLNODE_H
  4 
  5 template<class T> class AVLTree;
  6 template<class T>
  7 class AVLNode
  8 {
  9 friend class AVLTree<T>;
 10 public:
 11     AVLNode()
 12     {
 13         data = 0;
 14         left = NULL;
 15         right = NULL;
 16         height = 0;
 17     }
 18     AVLNode(T val)
 19     {
 20         data = val;
 21         left = NULL;
 22         right = NULL;
 23         height = 0;
 24     }
 25 
 26 public:
 27     T data;
 28     AVLNode* left;
 29     AVLNode* right;
 30     int height;
 31 };
 32 
 33 #endif
 34 
 35 /************AVLTree.h**************/
 36 #ifndef AVLTREE_H
 37 #define AVLTREE_H
 38 
 39 #include "AVLNode.h"
 40 
 41 template<class T>
 42 class AVLTree
 43 {
 44 public:
 45     AVLTree();
 46     AVLNode<T>* Insert(const T data, AVLNode<T>* node);
 47     void LevelOrder(AVLNode<T>* root);
 48 private:
 49     AVLNode<T>* root;
 50 };
 51 
 52 #endif
 53 
 54 /************AVLTree.CPP**************/
 55 #include "AVLNode.h"
 56 #include "AVLTree.h"
 57 #include<queue>
 58 #include<iostream>
 59 using namespace std;
 60 
 61 template<class T>
 62 AVLTree<T>::AVLTree()
 63 {
 64     root = NULL;
 65 }
 66 
 67 template<class T>
 68 int Height(AVLNode<T>* node)
 69 {
 70     if(node != NULL)
 71         return node->height;
 72     return -1;
 73 }
 74 
 75 template<class T>
 76 AVLNode<T>* SingleRotateWithLeft(AVLNode<T>* node)
 77 {
 78     if(node != NULL)
 79     {
 80         AVLNode<T>* k;
 81         k = node->left;
 82         node->left = k->right;
 83         k->right = node;
 84 
 85         node->height = max(Height(node->left),Height(node->right)) + 1;
 86         k->height = max(Height(k->left),Height(k->right)) + 1;
 87 
 88         return k;
 89     }
 90     return NULL;
 91 }
 92 
 93 template<class T>
 94 AVLNode<T>* SingleRotateWithRight(AVLNode<T>* node)
 95 {
 96     if(node != NULL)
 97     {
 98         AVLNode<T>* k;
 99         k = node->right;
100         node->right = k->left;
101         k->left = node;
102 
103         node->height = max(Height(node->left),Height(node->right)) + 1;
104         k->height = max(Height(k->left),Height(k->right)) + 1;    
105 
106         return k;
107     }
108     return NULL;
109 }
110 
111 template<class T>
112 AVLNode<T>* DoubleRotateWithLeft(AVLNode<T>* node)
113 {
114     node->left = SingleRotateWithRight(node->left);
115     return SingleRotateWithLeft(node);
116 }
117 
118 template<class T>
119 AVLNode<T>* DoubleRotateWithRight(AVLNode<T>* node)
120 {
121     node->right = SingleRotateWithLeft(node->right);
122     return SingleRotateWithRight(node);
123 }
124 
125 template<class T>
126 void AVLTree<T>::LevelOrder(AVLNode<T>* root)
127 {
128     if(root != NULL)
129     {    
130         queue<AVLNode<T>*> q;
131         AVLNode<T>* curr = root;
132         AVLNode<T>* temp = root;
133         while(curr)
134         {
135             cout<<curr->data<<"("<<curr->height<<")"<<endl;
136             if(curr->left)
137                 q.push(curr->left);
138             if(curr->right)
139                 q.push(curr->right);
140             if(!q.empty())
141             {
142                 curr = q.front();
143                 q.pop();
144             }
145             else
146                 curr = NULL;
147         }
148     }
149 }
150 
151 template<class T>
152 AVLNode<T>* AVLTree<T>::Insert(const T data, AVLNode<T>* root)
153 {
154     if(root == NULL)
155         return root = new AVLNode<T>(data);
156     else
157     {
158         AVLNode<T>* node = root;
159         if(node->data > data)
160         {
161             node->left = Insert(data,node->left);
162             if(Height(node->left) - Height(node->right) == 2)
163             {
164                 if(data < node->left->data)
165                     node = SingleRotateWithLeft(node);
166                 else
167                     node = DoubleRotateWithLeft(node);
168             }            
169         }
170         else if(node->data < data)
171         {
172             node->right = Insert(data,node->right);
173             if(Height(node->right) - Height(node->left) == 2)
174             {
175                 if(data > node->right->data)
176                     node = SingleRotateWithRight(node);
177                 else
178                     node = DoubleRotateWithRight(node);
179             }
180         }
181         node->height = max(Height(node->left),Height(node->right))+1;
182         return node;
183     }
184     
185 }
186 
187 // AVL.cpp : 定义控制台应用程序的入口点。
188 //
189 
190 #include "stdafx.h"
191 #include "AVLNode.h"
192 #include "AVLTree.h"
193 #include "AVLTree.cpp"
194 
195 #include <iostream>
196 
197 using namespace std;
198 
199 
200 int _tmain(int argc, _TCHAR* argv[])
201 {
202     AVLTree<int> avl;
203     AVLNode<int>* root = avl.Insert(3,NULL);
204     root = avl.Insert(2,root);
205     root = avl.Insert(1,root);
206 
207     avl.LevelOrder(root);
208 
209      system("pause");
210     return 0;
211 }

View Code