那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……

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     ==>   3     ==>   2   4
 \         
/
  
3       2
首先, 将3上提一层, 父节点2成为3的左结点;再次3上提一层, 父节点4成为3的右结点.这实际上是由两次单旋转过程来组成的,代码如下:
AVLTree* DoubleRotateWithLeft(AVLTree* pNode)
{
    pNode
->pLeft = SingleRotateWithRight(pNode->pLeft);

    
return SingleRotateWithLeft(pNode);
}

posted on 2008-09-08 00:23 那谁 阅读(5402) 评论(3)  编辑 收藏 引用 所属分类: 算法与数据结构

评论

# re: AVL树中单,双旋转的解释  回复  更多评论   

一语点醒梦中人啊,书上太过形式化,不好看懂。
2011-10-05 11:32 | 泰剑

# re: AVL树中单,双旋转的解释  回复  更多评论   

@泰剑

大哥。这些代码都是书上的。。。
2012-08-15 17:27 | BYHH

# re: AVL树中单,双旋转的解释[未登录]  回复  更多评论   

突然明白。。。
2014-10-14 15:31 | 菜鸟

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理