FHQTreap：實現快速查找和插入操作的二叉搜索樹

一、什麼是FHQTreap

FHQTreap是一種基於Treap樹的二叉搜索樹，它在Treap樹的基礎上做了優化，可以實現快速的查找和插入操作。FHQTreap最大的特點是，它使用了兩種隨機性的策略來維護數列中的元素，一種是隨機優先順序值，一種是隨機旋轉。FHQTreap是由FHQ在2016年發明的，相較於其他數據結構而言，FHQTreap具有更優秀的時間和空間複雜度。

下面我們來看看如何實現FHQTreap。首先需要定義FHQTreap中存儲的節點結構體：

struct Node {
    int key, val;
    int size, pri;
    Node* ch[2];
    Node(int K=0, int V=0) : key(K), val(V), size(1), pri(rand()) { ch[0] = ch[1] = NULL; }
};

其中，key是存儲的關鍵字，val是存儲的值，size代表以該節點為根節點的子樹大小，pri是節點的隨機優先順序值，ch數組用來存儲該節點的左右兒子。在初始化Node結構體時，pri值為隨機生成的。

二、如何實現FHQTreap樹的查找

FHQTreap樹的查找操作和二叉搜索樹的查找操作類似，都是從根節點開始，按照二叉搜索樹的規則查找左右兒子。不同之處在於，FHQTreap樹通過比較節點的優先順序值來進行查找操作。

導航函數find操作實現如下：

Node* find(Node* u, int v) {
    while (u != NULL) {
        if (u -> val == v) return u;
        u = u -> ch[u -> key < v];
    }
    return u;
}

這是一個標準的二叉搜索樹的遞歸實現，它在每次遞歸時都會比較u節點和v的大小，返回左右子節點進行遞歸查找。不同之處在於，我們可以通過比較節點的優先順序值來判斷查找方向，先朝條件更優秀的方向查找。

三、如何實現FHQTreap樹的插入

插入操作是FHQTreap樹中的最重要操作，它使用了兩種隨機性策略：隨機優先順序值和隨機旋轉。先看看插入函數的基本寫法：

void insert(Node* &u, Node* v) {
    if (u == NULL) u = v;
    else {
        int k = (u -> key  key);
        insert(u -> ch[k], v);
        u -> size = u -> ch[0] -> size + u -> ch[1] -> size + 1; // 更新節點的size
        if (u -> ch[k] -> pri > u -> pri) rotate(u, k); // 旋轉
    }
}

這是一個遞歸操作，在每個節點上進行比較，如果該節點為空，直接將v節點插入即可。否則，遞歸查找左右兒子，同時更新節點的sizesize值，以便於後續的操作。如果該節點的子節點的優先順序大於它本身的優先順序，進行旋轉操作，使得樹的平衡性得以維護。

旋轉操作是FHQTreap樹中的核心操作，它用來保證樹的平衡性。旋轉分為左旋和右旋。左旋操作如下：

void rotate(Node* &u, int k) {
    Node* v = u -> ch[k];
    u -> ch[k] = v -> ch[k ^ 1];
    v -> ch[k ^ 1] = u;
    u -> size = u -> ch[0] -> size + u -> ch[1] -> size + 1;
    v -> size = v -> ch[0] -> size + v -> ch[1] -> size + 1;
    u = v;
}

在左旋操作中，我們先找到u節點和v節點，並將u的右節點指向v的左節點，v的左節點指向u，然後重新計算節點的size值。

右旋操作與左旋操作類似，這裡不再贅述。

四、如何實現FHQTreap樹的刪除

刪除操作是FHQTreap樹中的另外一個重要操作，它用來將數列中的元素刪除，在每次刪除操作後，我們可以確保該節點已經不存在於樹中了。

由於FHQTreap樹的刪除操作需要分為兩步：將待刪除節點旋轉到葉節點，然後將其刪除，我們需要先實現旋轉到葉節點的操作。rotateUntilLeaf如下：

Node* rotateUntilLeaf(Node* u, int k) {
    while (u -> ch[k] != NULL) {
        if (u -> ch[k] -> ch[k ^ 1] != NULL) {
            int dir = (u -> ch[k] -> ch[k ^ 1] -> pri > u -> ch[k] -> pri);
            rotate(u -> ch[k], dir ^ 1);
        }
        rotate(u, k);
    }
    return u;
}

在該操作中，我們從指定的節點開始，逐層旋轉深入直到到達終止節點（即該節點的左右兒子均為空），期間我們還需要調整節點的優先順序值，旋轉方向等信息，以達到旋轉的目的。

其中的刪除函數erase如下：

void erase(Node* &u, int v) {
    if (u == NULL) return;
    if (u -> val == v) {
        if (u -> ch[0] == NULL && u -> ch[1] == NULL) u = NULL;
        else if (u -> ch[0] == NULL) u = u -> ch[1];
        else if (u -> ch[1] == NULL) u = u -> ch[0];
        else {
            int k = (u -> ch[0] -> pri > u -> ch[1] -> pri);
            rotate(u, k);
            erase(u -> ch[k ^ 1], v);
        }
    }
    else {
        erase(u -> ch[u -> val  size = u -> ch[0] -> size + u -> ch[1] -> size + 1;
}

該函數通過比較節點的值來進行查找，如果找到了待刪除節點，那麼將其旋轉到樹的葉子節點處，然後進行刪除操作。最後更新節點的size信息即可。

五、FHQTreap的應用

FHQTreap是一種基於Treap樹的二叉搜索樹，它在Treap樹的基礎上做了優化，可以實現快速的查找和插入操作。FHQTreap最大的特點是，它使用了兩種隨機性的策略來維護數列中的元素，一種是隨機優先順序值，一種是隨機旋轉。相較於其他數據結構而言，FHQTreap具有更優秀的時間和空間複雜度。

FHQTreap的應用非常廣泛，比如說用途一：實現單調隊列。單調隊列是一種特殊的隊列，它支持兩種操作：入隊和出隊。入隊操作是將一個元素插入到隊列尾部，而出隊操作是將隊列頭部的元素彈出。FHQTreap可以使用雙端隊列來實現單調隊列，並且其時間複雜度為O(1)。

比如說用途二：統計區間內的滿足條件的元素個數。假設我們有一個序列A，需要統計A[1…n]中滿足某個條件的元素數量，那麼可以使用FHQTreap來解決。首先對序列A建立FHQTreap，然後對序列A中的每一個元素，查找FHQTreap中比它小的元素的數量，就是它在序列A中的rank值。以此來計算區間內的滿足條件的元素數量，相比於暴力查找，時間複雜度有了明顯的提升。

六、總結

本文介紹了FHQTreap的基礎知識和操作，包括何為FHQTreap樹、如何實現FHQTreap樹的查找和插入操作、如何實現FHQTreap樹的刪除操作以及FHQTreap的常見應用。值得注意的是，FHQTreap的高效性是基於它使用了兩種隨機性的策略維護數列中的元素。學習FHQTreap需要較紮實的C++編程能力，同時還需要對Treap樹的基本知識有所掌握。