樹堆 Treap

各位應該都知道鏈結串列（linked list）吧？Linked list 是順序資料結構，他不支援隨機存取，但是卻能在中間任何地方插入/刪除元素。現在問題來了，現在想要對一個有序序列動態的插入刪除，這時用 linked list 來時做的話一定 TLE 啊！

為了彌補 linked list 不能隨機存取的缺點，於是有人發明了二元搜尋樹，在資料是隨機的情況下，平均插入刪除查詢只花費 $O(\log n)$ 的時間。但是一般的二元搜尋樹在一些特殊的情況下時查詢還是會花 $O(n)$ 的時間，於是又有人發明了 AVL 樹、紅黑樹等「保證平衡」的平衡樹，不過實作非常繁瑣。今天要教大家的是在實作和效能中達到平衡的樹堆（Treap）。

通常在需要用到 Treap 的時候都是為了找元素的排名或是第 $k$ 大的元素，因為如果只是單純想動態插入刪除的話 STL 就已經有提供 set、map 等工具了。支援找元素的排名或是第 $k$ 大的元素的平衡樹我們通常稱之為名次樹，這邊列出名次樹的幾個操作：

• Insert($T, x$): 插入一個元素到名次樹 $T$ 裡頭。
• Delete($T,x$): 從名次樹 $T$ 裡頭移除元素 $x$。
• Find($T,x$): 從名次樹 $T$ 裡頭查詢元素 $x$ 是否存在。
• rank($T,x$): 查找元素x和名次樹 $T$ 裡頭所有元素比較後的排名。
• Kth_smallest_element($T,k$): 查找名次樹 $T$ 裡頭所有元素中排名第 $k$ 的元素是誰。
• predecessor($T,x$): 從名次樹 $T$ 裡頭查找元素 $x$ 的前驅（即鍵值小於 $x$ 但最接近的資料）。
• successor($T,x$): 從名次樹 $T$ 裡頭查找元素 $x$ 的後繼（即鍵值超過 $x$ 但最接近的資料）。

以下我們只關注於Insert和Delete這兩個操作，其他的操作對Treap來說並不是特有的因此不討論

1 Treap的特性

Treap = Tree + Heap 為了讓樹的深度保持平衡，於是引入堆的概念，我們每個節點除了鍵值(key)之外，還多附加了一個修正值(fix)，修正值會在節點剛形成的時候隨機生成一個值，在之後的操作中都不會改變。修正值還滿足了最小(最大)堆性質，於是Treap可以被定義為有以下性質的二元搜尋樹:

1. 若它的左子樹不空，則左子樹上所有結點的值均小於它的根結點的值，而且它的根節點的修正值小於等於左子樹根節點的修正值
2. 若它的右子樹不空，則右子樹上所有結點的值均大於它的根結點的值，而且它的根節點的修正值小於等於右子樹根節點的修正值
3. 若它存在左右子樹，則它的左右子樹也是Treap

為什麼這樣Treap就會平衡呢？隨機生成修正值的操作本身是在模擬整棵樹的鍵值是在隨機排列的情況被插入的，有人證明過鍵值在隨機排列的情況被插入二元搜尋樹中後，樹的深度大於$24\ln n$的機率$\leq\frac{1}{n^2}$，因此在大部分的情況下整棵樹的深度都是$O(\log n)$等級的。

一個Treap的節點定義如下:

struct node{
    node *left, *right; //左右子節點
    int key; //鍵值
    int fix; //修正值
    node( int _key ):left( NULL ), right( NULL ), key( _key ), fix( random() ){}
};

2 如何構造Treap

旋轉

為了讓Treap滿足他的性質，不可避免地一定要調整它的結構，調整的方式被稱為旋轉，在維護Treap的過程中只會用到兩種旋轉，分別是左旋和右旋。

• 旋轉的性質 1
  • 左旋一個子樹，會把它的根節點旋轉到根的左子樹位置，同時根節點的右子節點成為子樹的根；右旋一個子樹，會把它的根節點旋轉到根的右子樹位置，同時根節點的左子節點成為子樹的根。
• 旋轉的性質 2
  • 對子樹旋轉後，子樹仍然滿足二元搜尋樹的性質。

旋轉可以使不滿足堆性質的兩個節點通過調整位置，重新滿足堆的性質，而不改變二元搜尋樹的性質。

• 左旋的code

void left_rotate( node *&a ){
    node *b = a->right;
    a->right = b->left;
    b->left = a;
    a = b;
}

• 右旋的code

void right_rotate( node *&a ){
    node *b = a->left;
    a->left = b->right;
    b->right = a;
    a = b;
}

插入

在Treap中插入元素，與一般二元搜尋樹方法類似，具體方法如下:

1. 從根節點開始插入
2. 如果要插入的值小於等於當前節點的值，在當前節點的左子樹中插入，插入後如果左子節點的修正值小於當前節點的修正值，對當前節點進行右旋
3. 如果要插入的值大於當前節點的值，在當前節點的右子樹中插入，插入後如果右子節點的修正值小於當前節點的修正值，對當前節點進行左旋
4. 如果當前節點為空節點，在此建立新的節點，該節點的值為要插入的值，其修正值為隨機產生，左右子樹為空，插入成功

因為在隨機的情況下，Treap的高度是$O(\log n)$等級的，因此在Treap中插入元素的期望複雜度為$O(\log n)$，以下提供code:

void insert( node *&u, int key ){
    if( u == NULL ) {
        u = new node( key );
    }else if( key < u->key ){
        insert( u->left, key );
        if( u->left->fix < u->fix ){
            right_rotate( u );
        }
    }else{
        insert( u->right, key );
        if( u->right->fix < u->fix ){
            left_rotate( u );
        }
    }
}

刪除

關於Treap的刪除，我們可以先二分查找到要刪除的節點後，在分成兩個case來討論:

1. 該節點為葉節點或鏈節點，則該節點是可以直接刪除的節點，就直接刪除吧
2. 節點有兩個非空子節點。我們可以通過旋轉，使該節點變為可以直接刪除的節點。
   • 如果該節點的左子節點的修正值小於右子節點的修正值，右旋該節點，使該節點降為右子樹的根節點，然後訪問右子樹的根節點，繼續討論
   • 反之，左旋該節點，使該節點降為左子樹的根節點，然後訪問左子樹的根節點，繼續討論，直到變成可以直接刪除的節點。

因為在隨機的情況下，Treap的高度是$O(\log n)$等級的，因此在Treap中刪除元素的期望複雜度為$O(\log n)$，以下提供code:

bool erase( node *&u, int key ){
    if( u == NULL ){ //遇到空節點表示要刪除的鍵值不在Treap中，查詢失敗
        return false;
    }else if( key == u->key ){
        if( u->left == NULL || u->right == NULL ){ //情況1
            node *tmp = u;
            if( u->left == NULL ){
                u = u->left;
            }else{
                u = u->right;
            }
            delete tmp;
            return true; //刪除成功
        }else{ //情況2
            if( u->left->fix < u->right->fix ){
                right_rotate( u );
                return erase( u->right );
            }else{
                left_rotate( u );
                return erase( u->left );
            }
        }
    }else if( key < u->key ){
        return erase( u->left, key );
    }else{
        return erase( u->right, key );
    }
}

結語

我們已經學會Treap的插入刪除了，但是在競賽來說，我們手寫平衡樹的目的就是為了實作名次樹。為了達到名次樹的功能，我們會在每個子樹的根紀錄其子樹大小，在插入刪除的時候進行維護。

名次樹的實作請參考日月卦長的模板庫──Treap：http://sunmoon-template.blogspot.tw/2015/01/treap.html