AVL树中单,双旋转的解释

 AVL树是所谓的带有平衡条件的二叉查找树.解释一下这里的两个条件:1)首先,二叉查找树要求一个树的 根节点必然大于(或小于)其左子树中的所有节点, 同时必然小于(或大于)其右子树中的所有节点,也就是说,如果按照中序遍历二叉查找树, 它必然是严格递增(或递减)的.2)AVL树的平衡条件要求任何一颗子树,其左右子树的高度差不超过1.我们要求一颗树是AVL树,必须严格符合以上的两 个条件.

    想象一个插入节点的过程, 由于是二叉查找树, 那么在插入节点之后必然满足二叉查找树的条件, 但是, 却可能打破了AVL树本身特有的平衡条件.其中可能有4种情况,但是考虑镜像对称的缘故,本质上只有两种可能,下面分别进行分析:
    1) 插入节点是父节点的左节点,而父节点是祖父节点的左节点,也就是说, 祖父孙三代节点形成的是一个"线型"的关系,比如插入节点3后形成如下的子树:

   7
  /
  5
/
3 可以看出,即使已经破坏了AVL树的平衡条件,按照中序去遍历该树还是得到一个递增序列:357的, 因此如果要符合AVL树的平衡条件, 那么这里需要做的就是将节点3"往上提", 这样节点7的左右子树就不会出现高度差大于1的情况了.同时,将3"往上提"的同时需要保持二叉查找树的条件, 那么就需要将节点3的父节点往上转,而3的祖父节点成为父节点的右结点:

  7                 5  
  /           ==>      / \
5                 3   7
/                 
3                    可以看到,插入节点3后, 通过将3的父节点上提, 3的祖父节点成为父节点的右结点,重新满足了AVL树的两个平衡条件.
这个旋转过程的代码如下:

AVLTree *  SingleRotateWithLeft(AVLTree *  pNode)
{
    AVLTree *  pNode1;

    pNode1  =  pNode -> pLeft;
    pNode -> pLeft  =  pNode1 -> pRight;
    pNode1 -> pRight  =  pNode;

     //  结点的位置变了, 要更新结点的高度值
    pNode -> nHeight  =  Max(Height(pNode -> pLeft), Height(pNode -> pRight))  +   1 ;
    pNode1 -> nHeight  =  Max(Height(pNode1 -> pLeft), pNode -> nHeight)  +   1 ;

     return  pNode1;
}

2)插入节点是父节点的右节点,而父节点是祖父节点的左节点,也就是说, 祖父孙三代形成的是一个"之字型"的关系,比如插入节点3后形成如下的子树:

   4
  /  
2
 \
   3 可以看到,单纯的将2上提已经不能解决平衡破坏问题了, 我们需要将节点3往上提两次,最后3变成了这颗树的根节点:

   4             4             3
  /             /             /  \
2       ==> e="COLOR: #000000">    3       ==>     2     4
 \          /
   3         2 首先, 将3上提一层, 父节点2成为3的左结点;再次3上提一层, 父节点4成为3的右结点.这实际上是由两次单旋转过程来组成的,代码如下:

AVLTree *  DoubleRotateWithLeft(AVLTree *  pNode)
{
    pNode -> pLeft  =  SingleRotateWithRight(pNode -> pLeft);

     return  SingleRotateWithLeft(pNode);
}