查找-AVL查找樹

1 思想

二叉樹查找樹在插入時沒有對二叉樹的深度和結構做一個調整，使得葉子結點深度不一，在查找時深度越深的結點時間複雜度越高。為了改進查找的時間時間複雜度，於是出現了平衡二叉樹(AVL).

2 查找

查找與二叉查找樹一樣。

3 插入

<code>當在AVL中插入新的結點時，需要根據實際情況對AVL中的某些結點做單旋轉或雙旋轉操作，單旋轉表示做一次順時針或逆時針的旋轉操作，而雙旋轉則做兩次單旋轉操作（先順時針後逆時針，或者先逆時針後順時針），單旋轉發生在LL型插入和RR型插入，而雙旋轉則發生在LR型插入和RL型插入。以下的失去平衡點都指的是離插入點最近的那個失去平衡的結點。
/<code>

LL型：插入點位於失去平衡點的左孩子的左子樹上； RR型：插入點位於失去平衡點的右孩子的右子樹上； LR型：插入點位於失去平衡點的左孩子的右子樹上； RR型：插入點位於失去平衡點的右孩子的左子樹上。

插入思路 和二叉搜索樹的插入一樣，首先在樹中找到對應的位置然後插入，接著自底向上向根節點折回，於在插入期間成為不平衡的所有節點上進行旋轉來完成。因為折回到根節點的路途上最多有 1.5 乘 log n 個節點，而每次AVL 旋轉都耗費恆定的時間，插入處理在整體上耗費 O(log n) 時間。　 具體插入過程如下:

1. 如果當前結點為空，創建新結點返回.
2. 如果當前結點值和插入值相同，不做處理返回。
3. 如果插入值大於當前結點則插入到右其右孩子結點中。插入完成後比較左右孩子結點進行判斷樹是否失去平衡。如果是判斷屬於那種類型(RR, RL),並響應的旋轉。最後更新當前結點的深度(孩子結點的最大深度加1，默認null深度為-1)。
4. 否則插入到其做孩子上。 同樣比較左右孩子的深度判斷是否平衡，對於失去平衡的情況下做出調整。

<code>private AvlNode<anytype> insert(AnyType x, AvlNode<anytype> t) {
    if (t == null)
        return new AvlNode<anytype>(x, null, null);
    int compareResult = myCompare(x, t.element);
    if (compareResult < 0) {
        t.left = insert(x, t.left);
        if (height(t.left) - height(t.right) == 2) {
            if (myCompare(x, t.left.element) < 0)     //左左情況
                t = rotateWithLeftChild(t);
            else                                    //左右情況
                t = doubleWithLeftChild(t);
        }
    } else if (compareResult > 0) {
        t.right = insert(x, t.right);
        if (height(t.right) - height(t.left) == 2) {
            if (myCompare(x, t.right.element) < 0)        //右左情況
                t = doubleWithRightChild(t);
            else                                        //右右情況
                t = rotateWithRightChild(t);
        } 

    }
    //完了之後更新height值
    t.height = Math.max(height(t.left), height(t.right)) + 1;
    return t;
}/<anytype>/<anytype>/<anytype>/<code>

4 刪除

從AVL樹中刪除可以通過把要刪除的節點向下旋轉成一個葉子節點，接著直接剪除這個葉子節點來完成。因為在旋轉成葉子節點期間最多有 log n個節點被旋轉，而每次 AVL 旋轉耗費恆定的時間，刪除處理在整體上耗費 O(log n) 時間。 a.當被刪除節點n是葉子節點，直接刪除 b.當被刪除節點n只有一個孩子，刪除n，用孩子替代該節點的位置 c.當被刪除結點n存在左右孩子時，真正的刪除點應該是n的中序遍在前驅，或者說是左子樹最大的節點，之後n的值替換為真正刪除點的值。這就把c歸結為a，b的問題。

從刪除的結點處自低向上向根結點折回，根據當前結點的左右孩子深度判斷是否平衡，如果不平衡則按選擇規則進行旋轉。最後更新當前結點深度，如此遞歸折回到根結點。

http://blog.csdn.net/xiaofan086/article/details/8294382 http://blog.csdn.net/liyong199012/article/details/29219261 http://www.mamicode.com/info-detail-90162.html

閱讀更多 醉人Ryu 的文章

關鍵字: 不完美媽媽 節點 折回