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);
}