平衡二叉树

参考: http://www.cppblog.com/cxiaojia/archive/2012/08/20/187776.html

一定义

　　平衡二叉树（Balanced Binary Tree）是二叉查找树的一个进化体，也是第一个引入平衡概念的二叉树。1962年，G.M. Adelson-Velsky 和 E.M. Landis发明了这棵树，所以它又叫AVL树。平衡二叉树要求对于每一个节点来说，它的左右子树的高度之差不能超过1，如果插入或者删除一个节点使得高度之差大于1，就要进行节点之间的旋转，将二叉树重新维持在一个平衡状态。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

　　平衡二叉树实现的大部分过程和二叉查找树是一样的（学平衡二叉树之前一定要会二叉查找树），区别就在于插入和删除之后要写一个旋转算法去维持平衡.

二难点操作

1 旋转

　　对于一棵AVL树，由于一次插入删除操作造成该树高度不平衡时，根节点的两棵子树的高度只能差2. 而不平衡的情况只能是以下四种：

　　1、6节点的左子树3节点高度比右子树7节点大2，左子树3节点的左子树1节点高度大于右子树4节点，这种情况成为左左。

　　2、6节点的左子树2节点高度比右子树7节点大2，左子树2节点的左子树1节点高度小于右子树4节点，这种情况成为左右。

　　3、2节点的左子树1节点高度比右子树5节点小2，右子树5节点的左子树3节点高度大于右子树6节点，这种情况成为右左。

　　4、2节点的左子树1节点高度比右子树4节点小2，右子树4节点的左子树3节点高度小于右子树6节点，这种情况成为右右。

　　从图2中可以可以看出，1和4两种情况是对称的，这两种情况的旋转算法是一致的，只需要经过一次旋转就可以达到目标，我们称之为单旋转。2和3两种情况也是对称的，这两种情况的旋转算法也是一致的，需要进行两次旋转，我们称之为双旋转。

(1) 单旋转

　　单旋转是针对于左左和右右这两种情况的解决方案，这两种情况是对称的，只要解决了左左这种情况，右右就很好办了。图3是左左情况的解决方案，节点k2不满足平衡特性，因为它的左子树k1比右子树Z深2层，而且k1子树中，更深的一层的是k1的左子树X子树，所以属于左左情况。

　　为使树恢复平衡，我们把k2变成这棵树的根节点，因为k2大于k1，把k2置于k1的右子树上，而原本在k1右子树的Y大于k1，小于k2，就把Y置于k2的左子树上，这样既满足了二叉查找树的性质，又满足了平衡二叉树的性质。

　　这样的操作只需要一部分指针改变，结果我们得到另外一颗二叉查找树，它是一棵AVL树，因为X向上一移动了一层，Y还停留在原来的层面上，Z向下移动了一层。使得根节点两棵子树的高度差小于2

(2) 双旋转

　　对于左右和右左这两种情况，单旋转不能使它达到一个平衡状态，要经过两次旋转。双旋转是针对于这两种情况的解决方案，同样的，这样两种情况也是对称的，只要解决了左右这种情况，右左就很好办了。图4是左右情况的解决方案，节点k3不满足平衡特性，因为它的左子树k1比右子树Z深2层，而且k1子树中，更深的一层的是k1的右子树k2子树，所以属于左右情况。

　　为使树恢复平衡，我们需要进行两步，第一步，把k1作为根，进行一次右右情况下的旋转操作，旋转之后就变成了左左情况，所以第二步再进行一次左左情况下的旋转操作，最后得到了一棵以k2为根的平衡二叉树。

2 插入

　　插入的方法和二叉查找树基本一样，区别是，插入完成后需要从插入的节点开始维护一个到根节点的路径，每经过一个节点都要维持树的平衡。维持树的平衡要根据高度差的特点选择不同的旋转算法。

3 删除

　　删除的方法也和二叉查找树的一致，区别是，删除完成后，需要从删除节点的父亲开始向上维护树的平衡一直到根节点。

下面是完整的代码展示

  1 #include<iostream>
  2 //AVL树节点信息
  3 template<typename T>
  4 class TreeNode
  5 {
  6 public:
  7     TreeNode() :
  8         lson_(NULL), rson_(NULL)
  9     {
 10 
 11     }
 12     T data_;//值
 13     TreeNode* lson_;//指向左儿子的地址
 14     TreeNode* rson_;//指向右儿子的地址
 15 };
 16 //AVL树类的属性和方法声明
 17 template<typename T>
 18 class AVLTree
 19 {
 20 public:
 21     AVLTree(); 
 22     ~AVLTree();
 23     void insert(T x);//插入接口
 24     TreeNode<T>* find(T x);//查找接口
 25     void Delete(T x);//删除接口
 26     void traversal();//遍历接口
 27 
 28 private:
 29     void insertpri(TreeNode<T>* &node, T x);//插入
 30     void Deletepri(TreeNode<T>* &node, T x);//删除
 31 
 32     TreeNode<T>* findpri(TreeNode<T>* node, T x);//查找
 33     void insubtree(TreeNode<T>* node);//中序遍历
 34 
 35     int height(TreeNode<T>* node);//求树的高度
 36 
 37     void SingRotateLeft(TreeNode<T>* &k2);//左左情况下的旋转
 38     void SingRotateRight(TreeNode<T>* &k2);//右右情况下的旋转
 39     void DoubleRotateLR(TreeNode<T>* &k3);//左右情况下的旋转
 40     void DoubleRotateRL(TreeNode<T>* &k3);//右左情况下的旋转
 41 
 42     void Delete(TreeNode<T>* &root);
 43 private:
 44     TreeNode<T>* root_;//根节点
 45 };
 46 template<typename T>
 47 AVLTree<T>::AVLTree()
 48     : root_(NULL)
 49 {
 50 }
 51 template<typename T>
 52 AVLTree<T>::~AVLTree()
 53 {
 54     Delete(root_);
 55 }
 56 //计算节点的高度
 57 template<typename T>
 58 int AVLTree<T>::height(TreeNode<T>* node)
 59 {
 60     if (node != NULL)
 61     {
 62         int lh = height(node->lson_);
 63         int rh = height(node->rson_);
 64         return lh >= rh ? (lh + 1) : (rh + 1);
 65     }
 66     return -1;
 67 }
 68 template<typename T>
 69 void AVLTree<T>::Delete(TreeNode<T>* &root)
 70 {
 71     if (root->lson_)
 72     {
 73         Delete(root->lson_);
 74         root->lson_ =nullptr;
 75     }
 76     if (root->rson_)
 77     {
 78         Delete(root->rson_);
 79         root->rson_ = nullptr;
 80     }
 81        
 82     
 83     delete root;
 84     root = nullptr;
 85            
 86 }
 87 //左左情况下的旋转
 88 template<typename T>
 89 void AVLTree<T>::SingRotateLeft(TreeNode<T>* &k2)
 90 {
 91     if (!k2)
 92         return;
 93 
 94     TreeNode<T> *k1 = k2->lson_;
 95     if (k1)
 96     {
 97         k2->lson_ = k1->rson_;
 98         k1->rson_ = k2;
 99         k2 = k1;
100     }
101 
102 }
103 //右右情况下的旋转
104 template<typename T>
105 void AVLTree<T>::SingRotateRight(TreeNode<T>* &k2)
106 {
107     if (!k2)
108         return;
109 
110     TreeNode<T> *k1 = k2->rson_;
111     if (k1)
112     {
113         k2->rson_ = k1->lson_;
114         k1->lson_ = k2;
115         k2 = k1;
116     }
117 }
118 //左右情况的旋转
119 template<typename T>
120 void AVLTree<T>::DoubleRotateLR(TreeNode<T>* &k3)
121 {
122     if (!k3)
123         return;
124 
125     SingRotateRight(k3->lson_);
126     SingRotateLeft(k3);
127 }
128 //右左情况的旋转
129 template<typename T>
130 void AVLTree<T>::DoubleRotateRL(TreeNode<T>* &k3)
131 {
132     if (!k3)
133         return;
134 
135     SingRotateLeft(k3->rson_);
136     SingRotateRight(k3);
137 }
138 //插入
139 template<typename T>
140 void AVLTree<T>::insertpri(TreeNode<T>* &node, T x)
141 {
142     if (node == NULL)//如果节点为空,就在此节点处加入x信息
143     {
144         node = new TreeNode<T>();
145         node->data_ = x;
146     }
147     else if (node->data_ >= x)//如果x小于节点的值,就继续在节点的左子树中插入x
148     {
149         insertpri(node->lson_, x);
150         if (2 == height(node->lson_) - height(node->rson_))
151         {
152             if (x < node->lson_->data_)
153                 SingRotateLeft(node);
154             else
155                 DoubleRotateLR(node);
156         }
157     }
158     else//如果x大于节点的值,就继续在节点的右子树中插入x
159     {
160         insertpri(node->rson_, x);
161         if (2 == height(node->rson_) - height(node->lson_))//如果高度之差为2的话就失去了平衡,需要旋转
162         {
163             if (x > node->rson_->data_)
164                 SingRotateRight(node);
165             else
166                 DoubleRotateRL(node);
167         }
168     }
169 }
170 //插入接口
171 template<typename T>
172 void AVLTree<T>::insert(T x)
173 {
174     insertpri(root_, x);
175     int lh = height(root_);
176 }
177 //查找
178 template<typename T>
179 TreeNode<T>* AVLTree<T>::findpri(TreeNode<T>* node, T x)
180 {
181     if (!node)//如果节点为空说明没找到,返回NULL
182         return NULL;
183     if (node->data_ > x)//如果x小于节点的值,就继续在节点的左子树中查找x
184         return findpri(node->lson_, x);
185     else if (node->data_ < x)//如果x大于节点的值,就继续在节点的右子树中查找x
186         return findpri(node->rson_, x);
187     else//如果相等,就找到了此节点
188         return node;
189 }
190 //查找接口
191 template<typename T>
192 TreeNode<T>* AVLTree<T>::find(T x)
193 {
194     return findpri(root_, x);
195 }
196 //删除
197 template<typename T>
198 void AVLTree<T>::Deletepri(TreeNode<T>* &node, T x)
199 {
200     if (!node)
201         return;//没有找到值是x的节点
202 
203     if (x < node->data_)
204     {
205         Deletepri(node->lson_, x);//如果x小于节点的值,就继续在节点的左子树中删除x
206         if (height(node->rson_) - height(node->lson_) == 2)
207         {
208             if (height(node->rson_->lson_)>height(node->rson_->rson_))
209                 DoubleRotateRL(node);
210             else
211                 SingRotateRight(node);
212         }
213     }
214     else if (x > node->data_)
215     {
216         Deletepri(node->rson_, x);//如果x大于节点的值,就继续在节点的右子树中删除x
217         if (height(node->lson_) - height(node->rson_) == 2)
218         {
219             if (height(node->lson_->rson_) > height(node->lson_->lson_))
220                 DoubleRotateLR(node);
221             else
222                 SingRotateLeft(node);
223         }
224     }
225     else//如果相等,此节点就是要删除的节点
226     {
227         if (node->lson_&&node->rson_)//此节点有两个儿子
228         {
229             TreeNode<T>* temp_fathor = node;
230             TreeNode<T>* temp = node->rson_;//temp指向节点的右儿子
231             while (temp->lson_)//找到右子树中值最小的节点
232             {
233                 temp_fathor = temp;
234                 temp = temp->lson_;
235             }
236 
237             //把右子树中最小节点的值赋值给本节点
238             node->data_ = temp->data_;
239             delete temp_fathor->lson_;
240             temp_fathor->lson_ = nullptr;
241 
242             if (2 == height(node->lson_) - height(node->rson_))
243             {
244                 if (height(node->lson_->rson_) > height(node->lson_->lson_))
245                     DoubleRotateLR(node);
246                 else
247                     SingRotateLeft(node);
248             }
249         }
250         else//此节点有1个或0个儿子
251         {
252             TreeNode<T>* temp = node;
253             if (node->lson_ == NULL)//有右儿子或者没有儿子
254                 node = node->rson_;
255             else if (node->rson_ == NULL)//有左儿子
256                 node = node->lson_;
257             delete(temp);
258             temp = NULL;
259         }
260     }
261 }
262 //删除接口
263 template<typename T>
264 void AVLTree<T>::Delete(T x)
265 {
266     Deletepri(root_, x);
267 }
268 //中序遍历函数
269 template<typename T>
270 void AVLTree<T>::insubtree(TreeNode<T>* node)
271 {
272     if (node == NULL) 
273         return;
274     insubtree(node->lson_);//先遍历左子树
275     std::cout << node->data_ << " ";//输出根节点
276     insubtree(node->rson_);//再遍历右子树
277 }
278 //中序遍历接口
279 template<typename T>
280 void AVLTree<T>::traversal()
281 {
282     insubtree(root_);
283 }