c/c++语言开发共享图解数据结构树之AVL树

avl树(平衡二叉树)：

avl树本质上是一颗二叉查找树，但是它又具有以下特点：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。在avl树中任何节点的两个子树的高度最大差别为一，所以它也被称为平衡二叉树。下面是平衡二叉树和非平衡二叉树对比的例图：

平衡因子(bf)：结点的左子树的深度减去右子树的深度，那么显然-1<=bf<=1;

avl树的作用：

我们知道，对于一般的二叉搜索树（binary search tree），其期望高度（即为一棵平衡树时）为log2n，其各操作的时间复杂度（o(log2n)）同时也由此而决定。但是，在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即o(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况，但是在进行了多次的操作之后，由于在删除时，我们总是选择将待删除节点的后继代替它本身，这样就会造成总是右边的节点数目减少，以至于树向左偏沉。这同时也会造成树的平衡性受到破坏，提高它的操作的时间复杂度。

例如：我们按顺序将一组数据1,2,3,4,5,6分别插入到一颗空二叉查找树和avl树中，插入的结果如下图：

由上图可知，同样的结点，由于插入方式不同导致树的高度也有所不同。特别是在带插入结点个数很多且正序的情况下，会导致二叉树的高度是o(n)，而avl树就不会出现这种情况，树的高度始终是o(lgn).高度越小，对树的一些基本操作的时间复杂度就会越小。这也就是我们引入avl树的原因

avl树的基本操作：

avl树的操作基本和二叉查找树一样，这里我们关注的是两个变化很大的操作：插入和删除！

我们知道，avl树不仅是一颗二叉查找树，它还有其他的性质。如果我们按照一般的二叉查找树的插入方式可能会破坏avl树的平衡性。同理，在删除的时候也有可能会破坏树的平衡性，所以我们要做一些特殊的处理，包括：单旋转和双旋转！

avl树的插入，单旋转的第一种情况—右旋：

由上图可知：在插入之前树是一颗avl树，而插入之后结点t的左右子树高度差的绝对值不再 < 1,此时avl树的平衡性被破坏，我们要对其进行旋转。由上图可知我们是在结点t的左结点的左子树上做了插入元素的操作，我们称这种情况为左左情况，我们应该进行右旋转(只需旋转一次，故是单旋转)。具体旋转步骤是：

t向右旋转成为l的右结点，同时，y放到t的左孩子上。这样即可得到一颗新的avl树，旋转过程图如下：

左左情况的右旋举例：

avl树的插入，单旋转的第一种情况—左旋：

由上图可知：在插入之前树是一颗avl树，而插入之后结点t的左右子树高度差的绝对值不再 < 1,此时avl树的平衡性被破坏，我们要对其进行旋转。由上图可知我们是在结点t的右结点的右子树上做了插入元素的操作，我们称这种情况为右右情况，我们应该进行左旋转(只需旋转一次，故事单旋转)。具体旋转步骤是：

t向右旋转成为r的左结点，同时，y放到t的左孩子上。这样即可得到一颗新的avl树，旋转过程图如下：

右右情况的左旋举例：

以上就是插入操作时的单旋转情况！我们要注意的是：谁是t谁是l，谁是r还有谁是x,y,z!t始终是开始不平衡的左右子树的根节点。显然l是t的左结点，r是t的右节点。x、y、y是子树当然也可以为null.null归null，但不能破坏插入时我上面所说的左左情况或者右右情况。

avl树的插入，双旋转的第一种情况—左右(先左后右)旋：

由　　上图可知，我们在t结点的左结点的右子树上插入一个元素时，会使得根为t的树的左右子树高度差的绝对值不再 < 1，如果只是进行简单的右旋，得到的树仍然是不平衡的。我们应该按照如下图所示进行二次旋转：

左右情况的左右旋转实例：

avl树的插入，双旋转的第二种情况—右左(先右后左)旋：

由上图可知，我们在t结点的右结点的左子树上插入一个元素时，会使得根为t的树的左右子树高度差的绝对值不再 < 1，如果只是进行简单的左旋，得到的树仍然是不平衡的。我们应该按照如下图所示进行二次旋转：

右左情况的右左旋转实例：

avl树的插入代码实现:(仅供参考)

懂了以上单旋转和双旋转的原理之后，那么代码写起来也就比较简单了，以下是我写的代码，如果有错还望大家不吝指正。（参考数据结构与算法分析-weiss著）

#include <iostream> #include <stdlib.h>  using namespace std;  #define datatype int  /*     定义avl树的结构体，链式 */ typedef struct avlnode{     datatype    data;     avlnode    * m_pleft;     avlnode    * m_pright;     int height; }*avltree,*position,avlnode;  //求两个数的最大值 int max(int a,int b) {     return a>b?a:b; } //求树的高度 int height( avltree t) {     if(null == t)         return -1;     else         return t->height; }  //单旋转右旋 avltree singlerotatewithright(avltree t) {     avltree l = t->m_pleft;     t->m_pleft = l->m_pright;     l->m_pright = t;     t->height = max( height(t->m_pleft),height(t->m_pright) ) + 1;     l->height = max( height(l->m_pleft),height(l->m_pright) ) + 1;     return l;    //此时l成为根节点了（可参考avl的插入的左左情况的右旋图） } //单旋转左旋 avltree singlerotatewithleft(avltree t) {     avltree r = t->m_pright;     t->m_pright = r->m_pleft;     r->m_pleft = t;     t->height = max( height(t->m_pleft),height(t->m_pright) ) + 1;     r->height = max( height(r->m_pleft),height(r->m_pright) ) + 1;     return r;    //此时r成为根节点了（可参考avl的插入的左左情况的左旋图） } //双旋转，先左后右 avltree doublerotatewithleft(avltree t)        //先左后右 {     t->m_pleft = singlerotatewithleft(t->m_pleft);     return singlerotatewithright(t); } //双旋转，先右后左 avltree doublerotatewithright(avltree t)    //先右后左 {     t->m_pright = singlerotatewithright(t->m_pright);     return singlerotatewithleft(t); } avltree avltreeinsert(avltree t, datatype x) {     if(t == null)    //如果树为空     {         t = (avlnode *)malloc(sizeof(struct avlnode));         if(t)         {             t->data = x;             t->m_pleft    = null;             t->m_pright = null;             t->height = 0;         }         else         {             cout << "空间不够" << endl;             exit(0);         }     }     else if( x < t->data)        //如果插入到t结点的左子树上     {         t->m_pleft = avltreeinsert(t->m_pleft,x);    //先插入，后旋转         if(height(t->m_pleft) - height(t->m_pright) == 2) //只有可能是这个         {             if(x < t->m_pleft->data)        //左左情况，只需要右旋转             {                 t = singlerotatewithright( t );             }             else                            //左右情况，双旋转,先左             {                 t = doublerotatewithleft( t );             }         }     }     else if( x > t->data )     {         t->m_pright = avltreeinsert(t->m_pright,x);         if(height(t->m_pright) - height(t->m_pleft) == 2)         {             if(x > t->m_pright->data)        //右右情况，进行左旋             {                 t = singlerotatewithleft( t );             }             else                            //左右情况，双旋转,先右             {                 t = doublerotatewithright( t );             }         }     }     //如果这个数已经存在，那么不进行插入     t->height = max(height(t->m_pleft),height(t->m_pright)) + 1;     return t; } //递归实现中序遍历 void inordervisituserecur(const avltree pcurrent) {     if(pcurrent)     {         inordervisituserecur(pcurrent->m_pleft);         cout << pcurrent->data << " ";         if(pcurrent->m_pleft)             cout << " leftchild: "<<pcurrent->m_pleft->data;         else             cout << " leftchild: "<<"null" ;         if(pcurrent->m_pright)             cout << " rightchild: "<<pcurrent->m_pright->data;         else             cout << " rightchild: "<< "null";         cout << endl;         inordervisituserecur(pcurrent->m_pright);     } } int main() {     avltree root = null;     root = avltreeinsert(root,1);     root = avltreeinsert(root,2);     root = avltreeinsert(root,3);     root = avltreeinsert(root,4);     root = avltreeinsert(root,5);     root = avltreeinsert(root,6);     root = avltreeinsert(root,7);     root = avltreeinsert(root,8);     root = avltreeinsert(root,9);     root = avltreeinsert(root,10);     root = avltreeinsert(root,11);     root = avltreeinsert(root,12);     root = avltreeinsert(root,13);     root = avltreeinsert(root,14);     root = avltreeinsert(root,15);     inordervisituserecur(root);     return 0; }