Size Balanced Tree (SBT) 詳細實現：平衡二叉查找樹的另一種選擇

什麼是 SBT

Size Balanced Tree 是一種以「子樹節點數」為平衡條件的二叉查找樹。由陳勁 (Chen Jin) 於 2007 年提出，性能接近紅黑樹、AVL 樹，但代碼極其簡潔 (核心 < 100 行)，被譽為「最適合比賽現場手寫的平衡樹」。

核心不變量

對任意節點 x：

• size[x] = size[left[x]] + size[right[x]] + 1
• 左子樹不小於右子樹的右子樹：size[left[left[x]]] >= size[right[x]]
• 右子樹不小於左子樹的左子樹：size[right[right[x]]] >= size[left[x]]

違反時通過旋轉恢復，均攤 O(1) 維護代價。

基本操作：旋轉

// 左旋：x 的右孩子 k 上旋
void Left_Rotate(int &x) {
    int k = right[x];
    right[x] = left[k];
    left[k] = x;
    size[k] = size[x];
    size[x] = size[left[x]] + size[right[x]] + 1;
    x = k;
}

// 右旋：x 的左孩子 k 上旋
void Right_Rotate(int &x) {
    int k = left[x];
    left[x] = right[k];
    right[k] = x;
    size[k] = size[x];
    size[x] = size[left[x]] + size[right[x]] + 1;
    x = k;
}

維護函數

插入/刪除後自底向上調用 Maintain(x, flag)，flag 指示操作在左/右子樹。

void Maintain(int &x, bool Right) {
    if (!x) return;
    if (!Right) { // 在左子樹操作
        if (size[left[left[x]]] > size[right[x]])
            Right_Rotate(x);                     // LL 型
        else if (size[right[left[x]]] > size[right[x]]) {
            Left_Rotate(left[x]); Right_Rotate(x); // LR 型
        } else return;
    } else { // 在右子樹操作
        if (size[right[right[x]]] > size[left[x]])
            Left_Rotate(x);                      // RR 型
        else if (size[left[right[x]]] > size[left[x]]) {
            Right_Rotate(right[x]); Left_Rotate(x); // RL 型
        } else return;
    }
    // 遞歸向上修正
    Maintain(left[x], false);
    Maintain(right[x], true);
    Maintain(x, false);
    Maintain(x, true);
}

插入操作

void Insert(int &x, int key) {
    if (!x) {
        x = ++NEW;
        size[x] = 1; key[x] = val;
        return;
    }
    size[x]++;
    if (val < key[x]) Insert(left[x], val);
    else Insert(right[x], val);
    Maintain(x, val >= key[x]);
}

刪除操作

標準 BST 刪除：找到節點，若有雙子樹則用左子樹最大節點 (或右子樹最小) 替換，再遞歸刪除該替換節點。

int Delete(int &x, int val) {
    if (!x) return 0;
    size[x]--;
    if (val == key[x] || (val < key[x] && !left[x]) || (val > key[x] && !right[x])) {
        if (left[x] && right[x]) {
            int p = Delete(left[x], val+1); // 找左子樹最大 (val+1 假設 key 唯一)
            key[x] = key[p];
            return p;
        } else {
            int p = x;
            x = left[x] + right[x]; // 非 0 即為唯一孩子
            return p;
        }
    }
    if (val < key[x]) Delete(left[x], val);
    else Delete(right[x], val);
    return 0;
}

第 K 大/小查詢

// 第 K 大 (按 key 遞減序)
int Select_Max(int x, int k) {
    if (!x) return -1;
    int r = size[right[x]] + 1;
    if (r < k) return Select_Max(left[x], k - r);
    if (r > k) return Select_Max(right[x], k);
    return key[x];
}

// 第 K 小
int Select_Min(int x, int k) {
    if (!x) return -1;
    int l = size[left[x]] + 1;
    if (l < k) return Select_Min(right[x], k - l);
    if (l > k) return Select_Min(left[x], k);
    return key[x];
}

完整可運行框架 (解決動態第 K 小問題)

#include 
using namespace std;
const int MAXN = 100005;
int size[MAXN], left[MAXN], right[MAXN], key[MAXN], NEW = 0;

// ... 以上所有函數 ...

int main() {
    int n, m; scanf("%d%d", &n, &m);
    int root = 0;
    for (int i = 1; i <= n; i++) {
        int x; scanf("%d", &x);
        Insert(root, x);
    }
    while (m--) {
        int op, x; scanf("%d%d", &op, &x);
        if (op == 1) Insert(root, x);
        else if (op == 2) Delete(root, x);
        else if (op == 3) printf("%d\n", Select_Min(root, x));
    }
    return 0;
}

SBT vs AVL vs 紅黑樹

總結

SBT 以「尺度平衡」替代「高度平衡」，用子樹大小作為決策指標，實現了驚人的代碼簡潔度與性能平衡。對於算法競賽、嵌入式系統、教學演示，SBT 是平衡二叉查找樹的最佳選擇之一。