大家好，

前段時間我更新過AVL、紅黑樹以及搜索二叉樹的簡單講解，今天我們還是圍繞著平衡樹的話題，來講解一個很牛逼的平衡樹結構，這種結構是我國的一位大牛：陳啟峰，在2006年，他還在讀高中階段，所發明的一種平衡樹結構，叫Size Balanced Tree（SBT），根據節點的個數，來調整平衡性，一直到今天，這種平衡樹結構，在演算法競賽領域是非常常用的，雖然SBT的時間復雜度跟AVL、紅黑樹這些平衡樹一樣，但是SBT是比較好寫，比較好改的，所以在演算法競賽時，是最常用的一種演算法，陳啟峰SBT論文（譯）

本期文章原始碼：GitHub

前期文章：

二叉樹的概念以及搜索二叉樹

AVL平衡樹

淺析紅黑樹

一、左右旋轉

還是老樣子，為了維持平衡性，SBT也是需要進行旋轉操作的，只是說，呼叫旋轉操作的時機，跟其他的平衡樹有點區別而已，講解旋轉之前，我們先來認識SBT的節點：

//可以直接改為泛型，這里為了理解這種結構，就忽略了
public class SBTNode {
    public int val; //值域
    public SBTNode left, right; //左右孩子
    public int size; //節點數
    
    public SBTNode(int val) {
        this.val = val;
        size = 1; //默認節點大小是1
    }
}

SBT的節點，只是多了一個size域，用于表示以當前節點為根節點時，這顆子樹的節點數，整棵樹的平衡性，就是根據這個size來調整的，

右旋轉：(LL型)

旋轉操作的指標，相互之間的轉換，我相信以前了解過平衡樹的同學，應該是知道的（如果不知道，請翻閱前期文章），問題就在于如何，如何修改這些節點的size？

看上圖，T1-T3，表示子樹，另外兩個表示節點，旋轉之后，我們會發現，T1和T2和T3這三顆子樹，他們下面的節點是沒有發生改變的，也就是說T1-T3，這三個是不需要再次計算size的，我們只需要計算上圖那兩個白色的節點的size即可！

又因為，旋轉之后，新的根節點的節點數，還應該是原根節點的節點數，所以最后我們只需要計算旋轉之后，原根節點的節點數即可，也就等于該節點的左子樹節點數加上右子樹的節點數，再加自己本身這個節點，

//SBT右旋轉
private SBTNode R_Rotate(SBTNode node) {
    SBTNode newRoot = node.left;
    node.left = newRoot.right;
    newRoot.right = node; 
    
    //計算size
    newRoot.size = node.size; //新根節點的節點數，等于原根節點的節點數
    node.size = (node.left != null? node.left.size : 0) + 
        (node.right != null? node.right.size : 0) + 1;
    return newRoot; //回傳新的根節點
}

左旋轉：(RR型)

跟上面的旋轉一樣，每個節點之間的指標指向，這里就不深究了，同學可以看看我前期的文章，有講解，主要還是size的計算，同樣的，T1~T3的節點數，都是沒有變，所以不用管，只需計算原根節點和新根節點的節點數，切新根節點的節點數，就是原根節點的節點數，

//SBT左旋轉操作
private SBTNode L_Rotate(SBTNode node) {
    SBTNode newRoot = node.right;
    node.right = newRoot.left;
    newRoot.left = node;
    
    //計算size
    newRoot.size = node.size; //繼承原根節點的節點數
    node.size = (node.left != null? node.left.size : 0) + 
        (node.right != null? node.right.size : 0) + 1;
    return newRoot; //回傳新的根節點
}

以上兩種就是最基本的LL型和RR型，在SBT中，也是有LR型和RL型的，跟AVL中一樣，不需要再寫額外的代碼，只需要呼叫兩次左旋轉或者右旋轉，如下：

• 假設A節點需要進行LR型的旋轉，則只需A.left = 左旋轉一次，再A= 右旋轉一次，
• 同理，假設B節點需要進行RL型的旋轉，則只需B.right = 右旋轉一次，再B = 左旋轉一次，

具體在什么時候需要呼叫旋轉函式，我們在接下來的Maintain方法里講解，

二、Maintain方法

Maintain方法，就是SBT樹，最核心的地方，也就是這個方法，能夠保證一棵樹具有平衡性的，

首先，我們需要知道，在什么時候，才需要進行旋轉操作，在AVL中，是通過判斷平衡因子來處理平衡性；在左傾紅黑樹中，則是根據每個節點顏色來處理平衡性，而SBT是：

首先看這張圖：

上面的四種旋轉（LL、LR、RR、RL），分別對于一下四點：

• LL型：T1的size > 二叔的size
• LR型：T2的size > 二叔的size
• RL型：T3的size > 大叔的size
• RR型：T4的size > 大叔的size

以上四點，就是觸發機關，只要滿足這四點的某一個條件，則需要進行旋轉操作，總結起來就一句話：叔叔的節點數，必須大于等于侄子的節點數，不然的話，就需要進行平衡調整，具體是為什么這種機制，就能夠保證平衡性，請翻閱文章開頭，陳啟峰的那篇論文，

到目前為止，我們就知道了SBT的核心，代碼寫起來就簡單多了，分別計算叔叔節點和侄子節點的節點數，if判斷即可，值得注意的是，旋轉操作之后，還需要遞回呼叫Maintain方法，遞回呼叫的物件，就是：哪個節點的子樹被換了，則需要呼叫這個Maintain（新子樹）；舉個例子：原先A節點的右子樹是T2，旋轉操作之后，A節點的右子樹變為了T3，那么就需要遞回呼叫Maintain（T3），

//Maintain方法
private SBTNode maintain(SBTNode cur) {
    if (cur == null) {
        return null;
    }

    //計算對應節點的節點數，null的話，就是0
    int leftSize = cur.left != null ? cur.left.size : 0;
    int rightSize = cur.right != null ? cur.right.size : 0;
    int leftLeftSize = cur.left != null ? (cur.left.left != null ? cur.left.left.size : 0) : 0;
    int leftRightSize = cur.left != null ? (cur.left.right != null ? cur.left.right.size : 0) : 0;
    int rightLeftSize = cur.right != null ? (cur.right.left != null ? cur.right.left.size : 0) : 0;
    int rightRightSize = cur.right != null ? (cur.right.right != null ? cur.right.right.size : 0) : 0;

    if (leftLeftSize > rightSize) { //LL型
        cur = R_Rotate(cur);//右旋
        
        cur.right = maintain(cur.right);
        cur = maintain(cur);
    } else if (leftRightSize > rightSize) { //LR型
        cur.left = L_Rotate(cur.left);
        cur = R_Rotate(cur);
        
        cur.left = maintain(cur.left);
        cur.right = maintain(cur.right);
        cur = maintain(cur);
    } else if (rightLeftSize > leftSize) { //RL型
        cur.right = R_Rotate(cur.right);
        cur = L_Rotate(cur);
        
        cur.left = maintain(cur.left);
        cur.right = maintain(cur.right);
        cur = maintain(cur);
    } else if (rightRightSize > leftSize) { //RR型
        cur = L_Rotate(cur);
        
        cur.left = maintain(cur.left);
        cur = maintain(cur);
    }
    return cur;
}

切記：遞回呼叫Maintain時，一定是先呼叫cur的左右子樹，然后才是呼叫cur，因為cur的處理，是依賴于他的左右孩子的，

可能有同學就會疑惑了，這么多遞回函式，這個代碼能跑完嗎？

當然能夠跑完，因為旋轉操作之后，遞回呼叫Maintain，能夠在O(1)的時間內完成，

三、add方法和delete方法

Maintain方法之后，SBT的就算掌握大部分的代碼了，其余的添加和洗掉代碼，完全跟搜索二叉樹的增加洗掉，一模一樣，只是需要在添加洗掉之后，呼叫Maintain方法，用于調整平衡性即可，

//add方法
public void add(int val) {
    this.root = add(this.root, val);
}
//方法多載
private SBTNode add(SBTNode cur, int val) {
    if (cur == null) {
        return new SBTNode(val);
    } else {
        cur.size++; //沿途節點的節點數加1
        if (val < cur.val) {
            cur.left = add(cur.left, val);
        } else {
            cur.right = add(cur.right, val);
        }
    }
    //添加之后，需要呼叫maintain，進行平衡操作
    return maintain(cur); 
}

在SBT中，delete的時候，在大多時候，是不需要進行平衡調整的，why？

是因為沒必要，假設當前SBT樹的高度是H，現在洗掉一個節點后，高度可能還是H，又或者是H- 1，此時調整平衡與不調整平衡，都不影響后續的操作，比如洗掉之后，高度還是H，下次查找或者添加時，時間復雜度還是O(H)，影響因素還是高度值，所以在一些比賽中，為了達到優化，在delete中，不進行平衡性的調整，而是把平衡性的調整，放在了add方法里，

//delete方法
public void delete(int val) {
    if (contains(val)) { //包含當前值得話，就遞回洗掉
        root = delete(root, val);
    }
}

private SBTNode delete(SBTNode cur, int val) {
    cur.size--; //沿途節點的節點數-1
    if (cur.val > val) {
        cur.left = delete(cur.left, val);
    } else if (cur.val < val) {
        cur.right = delete(cur.right, val);
    } else {
        if (cur.left == null && cur.right == null) { //沒有左右子樹
            cur = null;
        } else if (cur.left == null && cur.right != null) { //只有右子樹
            cur = cur.right;
        } else if (cur.left != null && cur.right == null) { //只有左子樹
            cur = cur.left;
        } else {
            //左右兩個子樹都有的情況
            SBTNode pre = null;
            SBTNode des = cur.right; //向右子樹查找最左節點
            des.size--;
            while (des.left != null) {
                pre = des;
                des = des.left;
                des.size--; //最終的des節點，會重新計算節點數
            }
            if (pre != null) {
                pre.left = des.right;
                des.right = cur.right; //將des節點，替換cur節點
            }
            des.left = cur.left;//連接原先的左子樹
            des.size = des.left.size + (des.right != null ? des.right.size : 0) + 1;
            cur = des;
        }
    }
    
    //cur = maintain(cur); //平衡調整
    return cur;
}

特別需要注意的是，就是被洗掉節點的左右子樹都不為null時，需要找一個節點來替換當前被洗掉的節點，一般都是在被洗掉節點的右子樹上，查找最小（最左）的節點進行替換，這一點，也是搜索二叉樹的洗掉操作，最容易出錯的一個點，值得重點關注，

還有一些簡單的方法沒寫，大家自主實作即可，比如contains、isEmpty等等，

好啦，本期更新就到此結束啦！SBT樹學好之后，可以幫助你在一些演算法題上得到更好的幫助，這種結構也算比較好改，可能根據SBT改其他的結構，總之，這種結構，值得好好學習，

我們下期見吧！！！