AVL樹是所謂的帶有平衡條件的二叉查找樹.解釋一下這里的兩個條件:1)首先,二叉查找樹要求一個樹的根節(jié)點必然大于(或小于)其左子樹中的所有節(jié)點, 同時必然小于(或大于)其右子樹中的所有節(jié)點,也就是說,如果按照中序遍歷二叉查找樹, 它必然是嚴格遞增(或遞減)的.2)AVL樹的平衡條件要求任何一顆子樹,其左右子樹的高度差不超過1.我們要求一顆樹是AVL樹,必須嚴格符合以上的兩個條件.
想象一個插入節(jié)點的過程, 由于是二叉查找樹, 那么在插入節(jié)點之后必然滿足二叉查找樹的條件, 但是, 卻可能打破了AVL樹本身特有的平衡條件.其中可能有4種情況,但是考慮鏡像對稱的緣故,本質(zhì)上只有兩種可能,下面分別進行分析:
1) 插入節(jié)點是父節(jié)點的左節(jié)點,而父節(jié)點是祖父節(jié)點的左節(jié)點,也就是說, 祖父孫三代節(jié)點形成的是一個"線型"的關(guān)系,比如插入節(jié)點3后形成如下的子樹:
7
/
5
/
3
可以看出,即使已經(jīng)破壞了AVL樹的平衡條件,按照中序去遍歷該樹還是得到一個遞增序列:357的, 因此如果要符合AVL樹的平衡條件, 那么這里需要做的就是將節(jié)點3"往上提", 這樣節(jié)點7的左右子樹就不會出現(xiàn)高度差大于1的情況了.同時,將3"往上提"的同時需要保持二叉查找樹的條件, 那么就需要將節(jié)點3的父節(jié)點往上轉(zhuǎn),而3的祖父節(jié)點成為父節(jié)點的右結(jié)點:
7 5
/ ==> / \
5 3 7
/
3
可以看到,插入節(jié)點3后, 通過將3的父節(jié)點上提, 3的祖父節(jié)點成為父節(jié)點的右結(jié)點,重新滿足了AVL樹的兩個平衡條件.
這個旋轉(zhuǎn)過程的代碼如下:
AVLTree* SingleRotateWithLeft(AVLTree* pNode)
{
AVLTree* pNode1;
pNode1 = pNode->pLeft;
pNode->pLeft = pNode1->pRight;
pNode1->pRight = pNode;
// 結(jié)點的位置變了, 要更新結(jié)點的高度值
pNode->nHeight = Max(Height(pNode->pLeft), Height(pNode->pRight)) + 1;
pNode1->nHeight = Max(Height(pNode1->pLeft), pNode->nHeight) + 1;
return pNode1;
}
2)插入節(jié)點是父節(jié)點的右節(jié)點,而父節(jié)點是祖父節(jié)點的左節(jié)點,也就是說, 祖父孫三代形成的是一個"之字型"的關(guān)系,比如插入節(jié)點3后形成如下的子樹:
4
/
2
\
3
可以看到,單純的將2上提已經(jīng)不能解決平衡破壞問題了, 我們需要將節(jié)點3往上提兩次,最后3變成了這顆樹的根節(jié)點:
4 4 3
/ / / \
2 ==> 3 ==> 2 4
\ /
3 2
首先, 將3上提一層, 父節(jié)點2成為3的左結(jié)點;再次3上提一層, 父節(jié)點4成為3的右結(jié)點.這實際上是由兩次單旋轉(zhuǎn)過程來組成的,代碼如下:
AVLTree* DoubleRotateWithLeft(AVLTree* pNode)
{
pNode->pLeft = SingleRotateWithRight(pNode->pLeft);
return SingleRotateWithLeft(pNode);
}