首页 > 代码库 > 平衡二叉树
平衡二叉树
参考: 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 if (!root->lson_ && !root->rson_) 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 }
平衡二叉树