AVL樹

目錄

1. AVL樹簡介

2. AVL樹添加節點

原始子樹1:

添加節點情況1(平衡):

添加節點情況2.1 (LL):

添加節點情況2.2 (LL):

添加節點情況3.1 (LR):

添加節點情況3.2 (LR):

原始子樹2:

添加節點情況1(平衡):

添加節點情況2.1(RR):

添加節點情況2.2(RR):

添加節點情況3.1(RL):

添加節點情況3.2(RL):

原始子樹3

統一所有旋轉操作

3. AVL樹删除節點

删除導緻的失衡:

LL – 右旋轉

RR – 左旋轉

LR – RR左旋轉，LL右旋轉

RL – LL右旋轉，RR左旋轉

複雜度分析

1. AVL樹簡介

AVL樹是最早發明的自平衡二叉搜尋樹之一

平衡因子(Balance Factor)：某結點的左右子樹的高度差

AVL樹的特點:

    每個節點的平衡因子隻可能是 1、0、-1（絕對值 ≤ 1，如果超過 1，稱之為“失衡”） 

    每個節點的左右子樹高度差不超過 1 

    搜尋、添加、删除的時間複雜度是 O(logn)

AVL樹中子樹失衡後, 恢複平衡,該子樹的高度前後保持一緻

2. AVL樹添加節點

AVL樹失衡情況分析:

BF: Balance Factor(該節點的平衡因子)

H: Height(節點高度)

注意: 下面在分析模型時表述旋轉時是以p為中心旋轉, 但在旋轉方法中傳入的旋轉節點是g, 因為g節點可以同時相容上層節點引用和下層節點引用

原始子樹1:

添加節點n

添加節點情況1(平衡):

添加在節點n之後, 該子樹仍然處于平衡狀态

添加節點情況2.1 (LL):

新添加節點為節點p的左節點, 而p也為節點g的左節點;

在添加節點n之後, 子樹失衡; 從節點g開始失衡, 而新添加節點作為g的Left的Left節點, 是以在旋轉時可以使用 LL-右旋

LL-右旋轉

添加節點情況2.2 (LL):

上面為添加n節點導緻g節點失衡, 也有可能是n的左子樹中添加節點導緻失衡

說明: T0,T1,T2,T3 為n,p,g節點子樹; 如果在n的平衡因子為0, p的平衡因子為0,  g的平衡因子為1的情況下, 在n的左子樹中增加一個節點, 使得n的平衡因子變為1, 則g節點将出現失衡且平衡因子變為2; 可以采用LL-右旋

節點變更操作:

1. g.left = p.right 
2. p.right = g 
3. 讓p成為這棵子樹的根節點 
4. 仍然是一棵二叉搜尋樹：T0 < n < T1 < p < T2 < g < T3 
5. 整棵樹都達到平衡

注意維護的内容:

1. T2、p、g 的 parent 屬性 
2. 先後更新 g、p 的高度

添加節點情況3.1 (LR):

新添加節點為節點p的右節點, 而p為節點g的左節點;

在添加節點n之後, 子樹失衡; 從節點g開始失衡, 而新添加節點作為g的Left的Right節點, 是以在旋轉時可以使用 LR-RR左旋, LL右旋

RR-左旋:

LL-右旋:

添加節點情況3.2 (LR):

上面為添加n節點導緻g節點失衡, 也有可能是n的右子樹中添加節點導緻失衡

說明: T0,T1,T2,T3 為n,p,g節點子樹; 如果在n的平衡因子為0, p的平衡因子為0,  g的平衡因子為1的情況下, 在n的左子樹中增加一個節點, 使得n的平衡因子變為-1, 則g節點将出現失衡且平衡因子變為2; 可以采用LR-RR左旋, LL右旋

原始子樹2:

添加節點

添加節點情況1(平衡):

添加節點n後, 子樹仍然平衡

添加節點情況2.1(RR):

新添加節點為節點p的右節點, 而p也為節點p的右節點;

在添加節點n之後, 子樹失衡; 從節點g開始失衡, 而新添加節點作為g的Right的Right節點, 是以在旋轉時可以使用RR左旋

RR-左旋

添加節點情況2.2(RR):

上面為添加n節點導緻g節點失衡, 也有可能是n的右子樹中添加節點導緻失衡

RR-左旋

說明: T0,T1,T2,T3 為n,p,g節點子樹; 如果在n的平衡因子為0, p的平衡因子為0,  g的平衡因子為-1的情況下, 在n的右子樹中增加一個節點, 使得n的平衡因子變為-1, 則g節點将出現失衡且平衡因子變為-2; 可以采用RR-左旋

節點變更操作:

1. g.right = p.left
2. p.left = g 
3. 讓p成為這棵子樹的根節點 
4. 仍然是一棵二叉搜尋樹：T0 < g < T1 < p < T2 < n < T3 
5. 整棵樹都達到平衡

注意維護的内容:

1. T1、p、g 的 parent 屬性 
2. 先後更新 g、p 的高度

添加節點情況3.1(RL):

新添加節點為節點p的左節點, 而p為節點p的右節點;

在添加節點n之後, 子樹失衡; 從節點g開始失衡, 而新添加節點作為g的Right的Left節點, 是以在旋轉時可以使用LR-LL右旋,RR左旋

LL-右旋

RR-左旋

添加節點情況3.2(RL):

上面為添加n節點導緻g節點失衡, 也有可能是n的左子樹中添加節點導緻失衡

LL-右旋

RR-左旋

說明: T0,T1,T2,T3 為n,p,g節點子樹; 如果在n的平衡因子為0, p的平衡因子為0,  g的平衡因子為-1的情況下, 在n的左子樹中增加一個節點, 使得n的平衡因子變為1, 則g節點将出現失衡且平衡因子變為-2; 可以采用LR-LL右旋,RR左旋

原始子樹3

此種情況, 在任何位置插入一個節點, 該子樹都将保持平衡

LL-右旋, RR-左旋代碼示例:

/**
 * 新增節點後的操作(更新高度或者恢複平衡)
 */
@Override
protected void afterAdd(Node<E> node) {
    while ((node = node.parent) != null) {
        if (isBalanced(node)) {
            // 更新高度
            updateHeight(node);
        } else {
            // 恢複平衡
            rebalance2(node);
            // 整棵樹恢複平衡
            break;
        }
    }
}

/**
 * 恢複平衡
 * @param grand 高度最低的那個不平衡節點
 */
@SuppressWarnings("unused")
private void rebalance2(Node<E> grand) {
    Node<E> parent = ((AVLNode<E>)grand).tallerChild();
    Node<E> node = ((AVLNode<E>)parent).tallerChild(); //node節點為新添加的節點
    if (parent.isLeftChild()) { // L
        if (node.isLeftChild()) { // LL
            rotateRight(grand);
        } else { // LR
            rotateLeft(parent);
            rotateRight(grand);
        }
    } else { // R
        if (node.isLeftChild()) { // RL
            rotateRight(parent);
            rotateLeft(grand);
        } else { // RR
            rotateLeft(grand);
        }
    }
}

/**
  * 左旋
  * @param grand 高度最低的那個不平衡節點
  */
private void rotateLeft(Node<E> grand) {
    Node<E> parent = grand.right;
    Node<E> child = parent.left;
    grand.right = child;
    parent.left = grand;
    afterRotate(grand, parent, child);
}

/**
  * 右旋
  * @param grand 高度最低的那個不平衡節點
  */
private void rotateRight(Node<E> grand) {
    Node<E> parent = grand.left;
    Node<E> child = parent.right;
    grand.left = child;
    parent.right = grand;
    afterRotate(grand, parent, child);
}

private void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
    // 讓parent稱為子樹的根節點
    parent.parent = grand.parent;
    if (grand.isLeftChild()) {
        grand.parent.left = parent;
    } else if (grand.isRightChild()) {
        grand.parent.right = parent;
    } else { // grand是root節點
        root = parent;
    }
    
    // 更新child的parent
    if (child != null) {
        child.parent = grand;
    }
    
    // 更新grand的parent
    grand.parent = parent;
    
    // 更新高度
    updateHeight(grand);
    updateHeight(parent);
}
           

統一所有旋轉操作

根據四種旋轉平衡初始與結果情況可以看出, 在進行不同的旋轉操作後, 所有子樹的排列保持一緻, 其中, 節點a與節點g未發生變化,是以可以統一四種旋轉操作....

/**
 * 恢複平衡
 * @param grand 高度最低的那個不平衡節點
 */
private void rebalance(Node<E> grand) {
    Node<E> parent = ((AVLNode<E>)grand).tallerChild();
    Node<E> node = ((AVLNode<E>)parent).tallerChild();
    if (parent.isLeftChild()) { // L
        if (node.isLeftChild()) { // LL
            rotate(grand, node, node.right, parent, parent.right, grand);
        } else { // LR
            rotate(grand, parent, node.left, node, node.right, grand);
        }
    } else { // R
        if (node.isLeftChild()) { // RL
            rotate(grand, grand, node.left, node, node.right, parent);
        } else { // RR
            rotate(grand, grand, parent.left, parent, node.left, node);
        }
    }
}

private void rotate(
        Node<E> r, // 子樹的根節點
        Node<E> b, Node<E> c,
        Node<E> d,
        Node<E> e, Node<E> f) {
    // 讓d成為這棵子樹的根節點
    d.parent = r.parent;
    if (r.isLeftChild()) {
        r.parent.left = d;
    } else if (r.isRightChild()) {
        r.parent.right = d;
    } else {
        root = d;
    }
    
    //b-c
    b.right = c;
    if (c != null) {
        c.parent = b;
    }
    updateHeight(b);
    
    // e-f
    f.left = e;
    if (e != null) {
        e.parent = f;
    }
    updateHeight(f);
    
    // b-d-f
    d.left = b;
    d.right = f;
    b.parent = d;
    f.parent = d;
    updateHeight(d);
}
           

3. AVL樹删除節點

删除導緻的失衡:

示例：删除子樹中的 16

可能會導緻父節點或祖先節點失衡(隻有1個節點會失衡)，其他節點，都不可能失衡

LL – 右旋轉

如果綠色節點不存在，更高層的祖先節點可能也會失衡，需要再次恢複平衡，然後又可能導緻更高層的祖先節點失衡...

極端情況下，所有祖先節點都需要進行恢複平衡的操作，共 O(logn) 次調整 

RR – 左旋轉

LR – RR左旋轉，LL右旋轉

RL – LL右旋轉，RR左旋轉

删除節點後恢複平衡代碼示例:

//node為真正删除的節點(因為删除度為2的節點時, 真正删除的節點時該節點的前驅節點或者後繼節點)
protected void afterRemove(Node<E> node) {
    while ((node = node.parent) != null) {
        if (isBalanced(node)) {
            // 更新高度
            updateHeight(node);
        } else {
            // 恢複平衡
            rebalance(node);
        }
    }
}
           

複雜度分析

添加 

可能會導緻所有祖先節點都失衡 

隻要讓高度最低的失衡節點恢複平衡，整棵樹就恢複平衡【僅需 O(1) 次調整】

删除 

可能會導緻父節點或祖先節點失衡（隻有1個節點會失衡）

恢複平衡後，可能會導緻更高層的祖先節點失衡【最多需要 O(logn) 次調整】

平均時間複雜度 

搜尋：O(logn) 

添加：O(logn)，僅需 O(1) 次的旋轉操作 

删除：O(logn)，最多需要 O(logn) 次的旋轉操作

參考資料:  小碼哥教育<<戀上資料結構與算法>>