2014-10-12

建造二元搜尋樹 O(n log n)

1. Problem
2. Sample Input
3. Sample Output
4. Solution
1. 4.1. 核心
2. 4.2. 補充

Problem

參照 Zerojudge d526: Binary Search Tree (BST) 按照插入的順序，建造一棵二元搜尋樹，原則上很簡單，但是很容易遇到極端的偏斜情況，如果插入順序很接近已經排序過的順序，則複雜度最慘為 O(n^2)。

Sample Input

11
368 115 121 88 741 762 801 34 41 511 60
6
5 2 10 4 9 15

Sample Output

1 2	368 115 88 34 41 60 121 741 511 762 801 5 2 4 10 9 15

Solution

核心

先稍微認識一下笛卡爾樹 (一種二元樹)，每個節點為 <key, value>，只看 key 時，笛卡爾樹是一棵二元搜尋樹，而看 value 時，它是一個最大堆 (或者是最小堆)。

在建造前，先撇清一點，笛卡爾樹的深度可能到達 n，與一般平衡樹不同。

笛卡爾樹如何建造 ? 假使已經對於 key 值由小到大排序 (升排序)，那麼將點依序插入笛卡爾樹，能保證的是－由於要符合二元搜尋樹，新加入的點一定是這棵樹某個節點的右節點。知道這一點後，再往前考慮前一次插入的點(它原本也符合再某節點的右節點)，往這個節點往上爬，直到符合最大堆(性質 node.v > new_insert.v)，這時將這個節點的右子樹移到新加入節點的左子樹 (此時符合二元搜尋樹的性質，也保有原本堆的性質)。就這麼持續入點下去。

這麼發現，往上爬的次數不超過節點個數，因為每個節點只會從右子樹換到左子樹。均攤下 O(n) (每個節點只會從右子樹推到左子樹一次，因此最多 n 次)

我們接著將 “按照順序插入的 BST” 轉換成建造笛卡爾樹，key 值依舊為輸入的元素大小，而 value 則訂為輸入順序，根據 key 值為一個二元搜尋樹，根據 value 建造一個最小堆，那麼仔細思考可以得到與原本相同的二元搜尋樹。

建造笛卡爾樹只需要花 O(n) 時間，但建造前必須根據 key 排序 O(n log n)，所以複雜度為 O(n log n)。

在這樣的方式建造有一個缺點，並不知道途中插入的情況，只會在最後得到一樣的二元搜尋樹。假使要得到途中插入的情況，考慮離線處理，將所有操作儲存起來，而二元樹的節點位置並不會更動的情況下，事先建造一個靜態樹，隨後使用一個懶標記存在與否即可。

補充

如何利用這個笛卡爾樹解決最簡單的 RMQ 問題？
對於 <key, value> = <i, A[i]> 所建造的笛卡爾樹，可以利用 LCA 的 tarjan 算法(離線作法) 在 O(n) 時間內完成。RMQ 假使查找 [l, r] 的最小值，又因為我們根據 value 建造最小堆，則根據 tarjan 的搜索順序，拜訪右子樹時(對於區間的 r 來說)，左子樹將會跟其 LCA 合併，而 LCA 的 index 肯定比左子樹來得大 (大於等於 l)，又根據最小堆保證是大於等於 l 且小於等於 r 的最小值。
只有笛卡爾樹可以做到建造二元搜尋樹嗎？
其實並不然，還可以藉由一個額外的平衡樹來完成，效率一樣在 O (n log n)，但是親自撰寫平衡樹本身就本末倒置，如果藉由 STL 提供的平衡樹，代碼量會比笛卡爾樹好寫多。具體而言使用 lower_bound 查找當前插入的元素位在哪兩個元素之間，一定符合在右子樹或者是左子樹。

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
struct Node {
    int key, value;
    int lson, rson, parent;
};
Node D[65536];
void insertCartesianTree(int index, Node D[]) {
    int p = index - 1;
    while(D[p].value > D[index].value)
        p = D[p].parent;
    D[D[p].rson].parent = index;
    D[index].lson = D[p].rson;
    D[p].rson = index;
    D[index].parent = p;
}
void dfsPrint(int node) {
    if(node == 0)    return;
    printf("%d ", D[node].key);
    dfsPrint(D[node].lson);
    dfsPrint(D[node].rson);
}
int main() {
    int N, x;
    pair<int, int> A[65536];
    while(scanf("%d", &N) == 1 && N) {
        for(int i = 1; i <= N; i++) {
            scanf("%d", &x);
            A[i] = make_pair(x, i);
        }
        sort(A+1, A+1+N);
        D[0].value = -1;
        D[0].lson = D[0].rson = D[0].parent = 0;
        for(int i = 1; i <= N; i++) {
            D[i].lson = D[i].rson = D[i].parent = 0;
            D[i].value = A[i].second, D[i].key = A[i].first;
        }
        for(int i = 1; i <= N; i++) {
            insertCartesianTree(i, D);
        }
        dfsPrint(D[0].rson);
        puts("");
    }
    return 0;
}

Morris' Blog

建造二元搜尋樹 O(n log n)

contents

Problem

Sample Input

Sample Output

Solution

核心

補充