1、二叉搜索樹的復(fù)雜度分析

• 1、如果按照7、4、9、2、5、8、11順序添加節(jié)點（添加順序和層序遍歷的結(jié)果一致），則構(gòu)造成的二叉搜索樹如下圖：
  
  image.png
  
  在二叉搜索樹中我們講述了添加、刪除和查詢的實現(xiàn)。

• 1、添加：比如添加一個值為12的節(jié)點，則會先和根節(jié)點7進(jìn)行比較，然后和9比較，最后和11進(jìn)行比較，大于11，添加到11的右邊。從上面添加過程可以看到，添加的復(fù)雜度是和樹的高度相關(guān)，復(fù)雜度為O(h)。而對于滿二叉樹來說O(h)==O(logn)。
• 2、刪除和查詢：對于刪除和查詢來說，也是需要去查找元素，和添加相同，其復(fù)雜度為O(h)==O(logn)。

• 2、如果按照從小到大的順序添加節(jié)點

  
  
  image.png
• 3、這樣一來二叉樹就退化成了鏈表，那么此時二叉搜索樹的搜索、添加、刪除的復(fù)雜度就變成了O(h)==O(n)。
  對于上面兩種二叉搜索樹來說，如果n比較大時，兩者的性能差別還是很大的。
• 4、二叉搜索樹在刪除節(jié)點時，也可能會造成二叉樹退化成鏈表。
  那么能不能保證在添加、刪除節(jié)點時，二叉樹不退化成鏈表，讓添加、刪除、搜索的復(fù)雜度保持在O(logn)?

2、平衡

想要讓二叉搜索樹在添加和刪除之后，不退化成鏈表，就需要保證它的平衡。

• 平衡：當(dāng)節(jié)點數(shù)量固定，左右子樹的高度越接近，這顆二叉樹就越平衡。高度也會越低。
  
  image.png
• 最理想的平衡：相同節(jié)點數(shù)量，完全二叉樹或滿二叉樹就會越平衡。這也是最理想的平衡。
  
  image.png

3、如何改進(jìn)二叉搜索樹

• 首先，我們不可能限制添加、刪除的順序。

• 所以改進(jìn)方案是：在添加、刪除后，想辦法讓二叉搜索樹恢復(fù)平衡，也就是減少樹的高度。

  
  
  image.png
  
  

  可以看到經(jīng)過操作將上圖中的樹的高度減少1，其實可以繼續(xù)減少樹的高度

  
  
  image.png
• 如果繼續(xù)調(diào)整節(jié)點的位置，完全可以達(dá)到最理想平衡的狀態(tài)，但是要付出的代價可能比較大。
  - 比如調(diào)整的次數(shù)太多，反而增加了時間復(fù)雜度。
• 所以，比較合理的解決方案：用盡量少的調(diào)整次數(shù)來達(dá)到適度平衡。
• 一棵達(dá)到適度平衡的二叉樹稱為平衡二叉搜索樹。

4、平衡二叉搜索樹（Balanced Binary Search Tree）

英文簡稱為BBST，常見的平衡二叉搜索樹有：AVL樹和紅黑樹。
一般也稱它們?yōu)?strong>自平衡的二叉搜索樹（Self-balancing Binary Search Tree）。
下面主要來看下AVL樹。

5、AVL樹

先來看一些基本概念：

• 1、平衡因子（Balance Factor）：一個節(jié)點的左右子樹的高度差。
• 2、AVL樹的特點：
  • 1、每個節(jié)點的平衡因子只能是1、0、-1，絕對值<=1，如果平衡因子的絕對值大于1，則樹失衡。
  • 2、每個節(jié)點的左右子樹高度差小于等于1。

  • 3、AVL樹的搜索、添加、刪除的時間復(fù)雜度為O(logn)。

    
    
    image.png
    
    

    左側(cè)二叉搜索樹沒有滿足每個節(jié)點的平衡因子的絕對值不大于1，右側(cè)二叉搜索樹每個平衡因子的絕對值不大于1，所以右側(cè)樹是AVL樹。

5.1、AVL樹添加導(dǎo)致的失衡

先看下圖中的二叉搜索樹的子樹

image.png

image.png

• 1、添加節(jié)點，在最壞的情況下，會導(dǎo)致添加節(jié)點的所有祖父節(jié)點都失衡。

由于上圖是二叉樹的一部分，在添加節(jié)點之后，這個子樹的高度增加了1，假設(shè)該子樹是節(jié)點9的父節(jié)點的右子樹，如果在添加之前9的父節(jié)點平衡因子為-1，那么在添加之后其平衡因子變成了-2。以此類推，最壞情況下會導(dǎo)致所有祖父節(jié)點都失衡。

• 2、父節(jié)點和非祖父節(jié)點，都不可能失衡。

• 1、父節(jié)點在添加之前無非就有兩種情況：a、度為1；2、度為0，在這兩種情況下，添加節(jié)點都不會導(dǎo)致父節(jié)點失衡。
• 2、添加節(jié)點只會影響父節(jié)點以及祖父節(jié)點的平衡因子，并不會影響其他節(jié)點的平衡因子。這種情況自己想下很好理解。

下面看下添加導(dǎo)致失衡的四種情況。

5.1.1、LL-右旋轉(zhuǎn)（單旋）

image.png

• 上圖中紅色塊代表的要添加的節(jié)點
• T0、T1、T2、T3表示的是子樹，可能為空。
• g是祖父節(jié)點，表示失衡的節(jié)點；p是父節(jié)點，祖父節(jié)點的左子樹的根節(jié)點；n表示node節(jié)點，父節(jié)點的左子樹的根節(jié)點。
• 從上圖可以看出要添加的節(jié)點是在祖父節(jié)點g的left-left，所以稱為LL。
• 針對LL的情況，需要將祖父節(jié)點g進(jìn)行右旋轉(zhuǎn)，來恢復(fù)平衡。
• 添加一個節(jié)點，在最壞的情況下會導(dǎo)致所有祖父節(jié)點失衡，從要添加的節(jié)點的node.parent.parent....祖父節(jié)點中去找失衡節(jié)點，找到第一個失衡的祖父節(jié)點，使其恢復(fù)平衡，這樣整棵樹都會恢復(fù)平衡。

添加節(jié)點導(dǎo)致其祖父節(jié)點失衡的原因是祖父節(jié)點的子樹的高度增加了，在經(jīng)過右旋轉(zhuǎn)后，子樹的高度會變成添加前子樹的高度，所以整棵樹都恢復(fù)了平衡。

右旋的偽代碼實現(xiàn)：

• 1、g.left=p.right;
• 2、p.right=g;
• 3、讓p稱為子樹的根節(jié)點；
• 4、旋轉(zhuǎn)之后仍然是一棵二叉搜索樹：T0 < n < T1 < p < T2 < g < T3
• 5、維護(hù)T2、g、p的parent屬性
• 6、按順序維護(hù)g、p的高度

由于右旋之后，p變成了根節(jié)點，而g變成了p的子節(jié)點，所以需要p的高度==p的高度+1。所以需要先維護(hù)g的高度。

5.1.2、RR-左旋轉(zhuǎn)（單旋）

image.png

• 要添加的節(jié)點在祖父節(jié)點的right-right，屬于RR情況。
• 需要將祖父節(jié)點g進(jìn)行左旋，恢復(fù)樹的平衡。
  左旋的偽代碼實現(xiàn)
• 1、g.right=p.left;
• 2、p.left=g;
• 3、讓p成為子樹的根節(jié)點；
• 4、旋轉(zhuǎn)之后仍然是一棵二叉搜索樹T0 < g < T1 < p < T2 < n < T3
• 5、維護(hù)g、p、T1的parent屬性。
• 6、按順序更新g、p的高度
• 7、整棵樹都恢復(fù)平衡

5.1.3、LR：RR先左旋轉(zhuǎn)，LL右旋轉(zhuǎn)（雙旋）

image.png

• 添加的節(jié)點在祖父節(jié)點的left-right，情況為LR。
• LR需要先對p進(jìn)行左旋轉(zhuǎn)，然后對g進(jìn)行右旋轉(zhuǎn)

• 1、針對p、n、T2來說屬于RR，所以對節(jié)點p進(jìn)行左旋轉(zhuǎn)
• 2、旋轉(zhuǎn)后屬于LL情況，所以對節(jié)點g進(jìn)行右旋轉(zhuǎn)。

5.1.4、RL：LL先右旋轉(zhuǎn)，RR左旋轉(zhuǎn)（雙旋）

image.png

5.1.5、添加之后的恢復(fù)

上面已經(jīng)講解了添加之后失衡的四種情況，下面看下代碼的具體實現(xiàn)。
由于AVL樹也是二叉搜索樹，所以繼承關(guān)系如下：

image.png

public class AVLTree<E> extends BST<E> {
}

由于添加邏輯是在BST中實現(xiàn)的，所以在BST中定義方法afterAdd(root);

// 添加元素
public void add(E element) {
    // 由于二叉搜索樹添加的元素不能為null
    elementNotNullCheck(element);

    // root等于null 第一次添加
    if (root == null) {
        root = createNode(element, null);
        afterAdd(root);
        size++;
        return;
    }
    // 非第一次添加 元素添加的步驟
    // 1、找到要添加節(jié)點的parent節(jié)點
    Node<E> node = root;
    Node<E> parent = root;
    int cmp = 0;
    while (node != null) {
        cmp = compare(element, node.element);
        parent = node;
        if (cmp > 0) {
            node = node.right;
        } else if (cmp < 0) {
            node = node.left;
        } else {
            // 當(dāng)元素的值相等時進(jìn)行覆蓋
            node.element = element;
            return;
        }
    }
    // 2、創(chuàng)建新的節(jié)點
    Node<E> newNode = createNode(element, parent);
    // 3、該節(jié)點是parent的左子節(jié)點還是右子節(jié)點
    if (cmp > 0) {
        parent.right = newNode;
    } else if (cmp < 0) {
        parent.left = newNode;
    }
    afterAdd(newNode);
    size++;
}

protected Node<E> createNode(E element, Node<E> parent) {
    return new Node<>(element, parent);
}

/**
 * @param node 新添加的節(jié)點
 */
protected void afterAdd(Node<E> node) {

}

需要在第一次添加根節(jié)點和添加其他節(jié)點時調(diào)用方法afterAdd()，具體的實現(xiàn)在AVLTree類中。

@Override
protected Node<E> createNode(E element, Node<E> parent) {
    return new AVLNode(element, parent);
}

@Override
protected void afterAdd(Node<E> node) {
    while ((node = node.parent) != null) {
        if (isBalanced(node)) { // 平衡
            // 更新高度
            updateHeight(node);
        } else { // 失衡
            // 恢復(fù)平衡
            rebalance(node);
                        break;
        }
    }
}

由于添加節(jié)點只會導(dǎo)致祖父節(jié)點失衡，父節(jié)點和非祖父節(jié)點不會失衡，所以我們需要找到最先失衡的祖父節(jié)點，并對其進(jìn)行旋轉(zhuǎn)，使得整棵樹都恢復(fù)平衡。
判斷節(jié)點是否失衡，就需要判斷節(jié)點的左右子樹的高度，所以需要在Node中增加高度屬性，但是height屬性只是AVLTree使用的，所以在AVLTree中定義一個AVLNode繼承Node，并在其中定義height屬性。并在其中添加判斷是否失衡的方法isBalanced(node)

public static class AVLNode<E> extends Node<E> {
    private int height ;
    // 判斷是否失衡
    public boolean isBalanced() {
        int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
        int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
        return Math.abs(leftHeight - rightHeight) < 2;
    }
}

但是此時高度屬性還沒有設(shè)置，所以此時調(diào)用isBalanced()并沒有任何意義。我們知道新添加的節(jié)點一定是葉子節(jié)點，所以可以將AVLNode中的屬性height默認(rèn)設(shè)置為1。
然后調(diào)用isBalanced()方法判斷節(jié)點是否失衡，如果是平衡的則調(diào)用updateHeight(node)進(jìn)行更新高度(這樣操作就避免了使用遞歸來計算高度)，否則執(zhí)行恢復(fù)平衡的操作（恢復(fù)平衡后再次更新高度）。這樣以來就能做到所有節(jié)點的高度都被設(shè)置了。*

public static class AVLNode<E> extends Node<E> {
    private int height ;
    //.....
    public void updateHeight() {
        int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
        int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
        height = 1 + Math.max(leftHeight, rightHeight);
    }
}

恢復(fù)平衡操作rebalance()

在這里我們需要判斷LL、RR、RL、LR四種情況。

/**
 * 恢復(fù)平衡
 * 
 * @param grand 高度最低的那個祖父節(jié)點
 */
private void rebalance(Node<E> grand) {
    // 進(jìn)行旋轉(zhuǎn)處理：LL、RR、LR、RL
    /**
     * 那么如何找到parent和node節(jié)點呢? 其實parent節(jié)點就是祖父節(jié)點左右子樹中高度較高的子樹的根節(jié)點
     * node節(jié)點是parent節(jié)點左右子樹中高度較高的子樹的根節(jié)點
     */
    Node<E> parent = getTallerChildNode(grand);
    Node<E> node = getTallerChildNode(parent);
    // 由于添加之后失衡的一定是祖父節(jié)點，所以grand、parent、node一定不會null。
    if (parent == grand.left) { // L
        if (node == parent.left) { // LL
            // 進(jìn)行右旋
            rotateRight(grand);
        } else { // LR
            rotateLeft(parent);
            rotateRight(grand);
        }
    } else { // R
        if (node == parent.left) {// RL
            rotateRight(parent);
            rotateLeft(grand);
        } else {// RR
            rotateLeft(grand);
        }
    }
}

• 1、rebalance(Node<E> grand)方法接收的節(jié)點就是最先失衡的祖父節(jié)點grand，那么如何找到parent和node節(jié)點？

觀察我們上面講述的四種情況，你會發(fā)現(xiàn)parent節(jié)點其實就是grand節(jié)點左右子樹中高度較高的子樹的根節(jié)點。
node節(jié)點其實就是parent節(jié)點左右子樹中高度較高的子樹的根節(jié)點。而且grand、node、parent節(jié)點不可能為空的。

獲取較高的子樹的根節(jié)點

public static class AVLNode<E> extends Node<E> {
    //.....

    public AVLNode<E> getTallerChildNode() {
        int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
        int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
        if (leftHeight > rightHeight)
            return (AVLNode<E>) left;
        if (leftHeight < rightHeight)
            return (AVLNode<E>) right;
        /**
         * 在leftHeight == rightHeight時，如果節(jié)點是父節(jié)點的左子節(jié)點，那么返回左子樹 反之則返回父節(jié)點的右子節(jié)點
         * 注意：在左右子樹高度相等時，返回左右子樹都是可以的，看自己怎么設(shè)計
         */
        return isLeftChild() ? (AVLNode<E>) left : (AVLNode<E>) right;
    }
}

• 2、需要注意的是進(jìn)行左旋、右旋的節(jié)點：

• LL、RR情況下，旋轉(zhuǎn)的是grand節(jié)點
• RL、LR情況下，先旋轉(zhuǎn)的是parent節(jié)點，然后再旋轉(zhuǎn)grand節(jié)點

rotateLeft()方法的實現(xiàn)

/**
 * 左旋
 * 
 * @param grand 要旋轉(zhuǎn)的節(jié)點
 */
private void rotateLeft(Node<E> grand) {
    Node<E> parent = grand.right;
    Node<E> child = parent.left;

    grand.right = child;
    parent.left = grand;

    // 讓parent成為根節(jié)點
    parent.parent = grand.parent;
    if (grand.isLeftChild()) {
        grand.parent.left = parent;
    } else if (grand.isRightChild()) {
        grand.parent.right = parent;
    } else { // 根節(jié)點
        root = parent;
    }

    // 設(shè)置grand的parent
    grand.parent = parent;
    // 設(shè)置child的parent
    if (child != null)
        child.parent = grand;

    // 設(shè)置高度
    updateHeight(grand);
    updateHeight(parent);
}

rotateLeft(Node<E> grand)接收的可能是parent節(jié)點或grand節(jié)點，那在方法中如何得到對應(yīng)節(jié)點的parent節(jié)點，既然是左旋，那么就可以參照RR情況。所以可以得到

Node<E> parent = grand.right;

具體旋轉(zhuǎn)的邏輯見上面方法，注釋的很清晰。

rotateRight()方法的實現(xiàn)

/**
 * 右旋
 * 
 * @param grand 要旋轉(zhuǎn)的節(jié)點
 */
private void rotateRight(Node<E> grand) {
    Node<E> parent = grand.left;
    Node<E> child = parent.right;

    grand.left = child;
    parent.right = grand;

    // 讓parent成為子樹的根節(jié)點
    parent.parent = grand.parent;
    if (grand.isLeftChild()) {
        grand.parent.left = parent;
    } else if (grand.isRightChild()) {
        grand.parent.right = parent;
    } else { // 根節(jié)點
        root = parent;
    }
    // 更新grand的parent
    grand.parent = parent;
    // 更新child的parent
    if (child != null)
        child.parent = grand;

    // 更新高度
    updateHeight(grand);
    updateHeight(parent);
}

可以發(fā)現(xiàn)左旋和右旋，在旋轉(zhuǎn)之后的都是將parent變成子樹的根節(jié)點，維護(hù)grand、parent、child的parent屬性、先更新grand的高度、再更新parent的高度。

5.2、統(tǒng)一添加節(jié)點失衡的所有情況

image.png

從上圖可以看到，無論哪種情況下的最終形態(tài)都是一樣的：

d作為根節(jié)點，其左右子樹的根節(jié)點都是b、f；
b的左右子樹為a、c，f的左右子樹為e、g；
所以可以對上述四種情形進(jìn)行統(tǒng)一處理。

/**
 * 對4種情形進(jìn)行統(tǒng)一處理
 * @param grand
 */
private void rebalance(Node<E> grand) {
    Node<E> parent = getTallerChildNode(grand);
    Node<E> node = getTallerChildNode(parent);
    if (parent == grand.left) { // L
        if (node == parent.left) { // LL
            rotate(grand, node, parent, grand, node.left, node.right, parent.right, grand.right);
        } else { // LR
            rotate(grand, parent, node, grand, parent.left, node.left, node.right, grand.right);
        }
    } else { // R
        if (node == parent.left) {// RL
            rotate(grand, grand, node, parent, grand.left, node.left, node.right, parent.right);
        } else {// RR
            rotate(grand, grand, parent, node, grand.left, parent.left, node.left, node.right);
        }
    }
}

private void rotate(
        Node<E> r,// 子樹的根節(jié)點
        Node<E> b,Node<E> d,Node<E> f,
        Node<E> a,Node<E> c,Node<E> e,Node<E> g
        ) {
    
    //將d作為根節(jié)點
    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.parent=d;
    b.right=c;
    if(c!=null)
        c.parent=b;
    
    
    // e-f
    f.parent=d;
    f.left=e;
    if(e!=null)
        e.parent=f;
    
    //b d f
    d.left=b;
    d.right=f;
    
    updateHeight(f);
    updateHeight(b);
    updateHeight(d);
}

5.3、刪除導(dǎo)致的失衡

image.png

刪除導(dǎo)致失衡肯定是刪除的節(jié)點所在的子樹的高度較低，而高度較高的子樹并沒有變化，所以不會影響其他節(jié)點。

5.3.1、LL-右旋轉(zhuǎn)(單旋)

image.png

• 左圖是刪除前的狀態(tài)
• 右圖是右旋后的結(jié)果
• 紅色部分是要刪除的節(jié)點
• 綠色部分可能不存在
  如果刪除紅色部分后，發(fā)現(xiàn)節(jié)點g的平衡因子變成了2，節(jié)點g失衡，進(jìn)行右旋，如果綠色部分不存在，發(fā)現(xiàn)右旋之后，整個子樹的高度減少了1，這樣就會導(dǎo)致更高層的祖先節(jié)點失衡，需要再次恢復(fù)平衡，然后又可能導(dǎo)致更高層的祖先節(jié)點失衡。。。。
  極端情況下，如果所有祖先節(jié)點都需要進(jìn)行恢復(fù)平衡的操作，共O(logn)次調(diào)整。

5.3.2、RR-左旋轉(zhuǎn)(單旋)

image.png

5.3.3、LR-RR左旋轉(zhuǎn)，LL右旋轉(zhuǎn)（雙旋）

image.png

5.3.4、RL-LL右旋轉(zhuǎn)，RR左旋轉(zhuǎn)（雙旋）

image.png

5.4、刪除之后的修復(fù)

經(jīng)過上面的分析可知，刪除之后的修復(fù)和添加后的修復(fù)是相同的，只不過添加后的修復(fù)只需要進(jìn)行一次恢復(fù)平衡即可，而刪除后的修復(fù)在極端情況下可能需要進(jìn)行l(wèi)ogn次的平衡操作。
刪除操作是在BST中實現(xiàn)的，同樣需要在其中創(chuàng)建一個afterRemove(node)方法，然后在AVLTree中進(jìn)行具體實現(xiàn)。
BST##remove()

private void remove(Node<E> node) {
    if (node == null)
        return;
    // 刪除度為2的節(jié)點
    if (node.hasTwoChildren()) {
        // 找到前驅(qū)節(jié)點
        Node<E> precurNode = precursor(node);
        // 用前驅(qū)節(jié)點的值覆蓋要刪除節(jié)點的值
        node.element = precurNode.element;
        // 刪除前驅(qū)節(jié)點
        node = precurNode;
    }

    // 刪除的node節(jié)點的度為1或0
    Node<E> child = node.left != null ? node.left : node.right;
    if (child != null) { // 度為1的節(jié)點
        // 使用子節(jié)點替代要刪除節(jié)點的位置
        child.parent = node.parent;
        if (node.parent == null)
            root = child;
        else if (node == node.parent.left)
            node.parent.left = child;
        else if (node == node.parent.right)
            node.parent.right = child;
    } // 刪除葉子節(jié)點
    else if (node.parent == null)
        root = null;
    else if (node == node.parent.left)
        node.parent.left = null;
    else if (node == node.parent.right)
        node.parent.right = null;
    size--;
    afterRemove(node);
}

AVLTree中的具體實現(xiàn)

@Override
protected void afterRemove(Node<E> node) {
    while ((node=node.parent)!=null) {
        if (isBalanced(node)) { // 平衡
            // 更新高度
            updateHeight(node);
        } else { // 失衡
            // 恢復(fù)平衡
            rebalance(node);
        }
    }
}

5.5、總結(jié)

5.5.1、添加

• 1、添加可能會導(dǎo)致所有祖父節(jié)點失衡
• 2、只要讓高度最低的失衡節(jié)點恢復(fù)平衡，整棵樹就恢復(fù)平衡了

5.5.2、刪除

• 1、刪除可能會導(dǎo)致父節(jié)點或祖父節(jié)點失衡，只有一個節(jié)點會失衡
• 2、恢復(fù)平衡后可能會導(dǎo)致更高層祖父節(jié)點失衡，最多需要調(diào)整logn次。

5.5.3、時間復(fù)雜度

• 1、搜索：O(logn)
• 2、添加：O(logn)，僅需O(1)次旋轉(zhuǎn)操作
• 3、刪除：O(logn)，最多需要O(logn)次旋轉(zhuǎn)操作。