---
tags: 基礎資料結構
title: Treap
---
# treap
### tree + heap = treap

### 樹性質 + 堆性質
:::success
在二元搜尋樹的右節點$key$恆大於左節點$key$的規則上 再加上堆的父節點$priority$恆大於或小於子節點$priority$

註 : 紅字代表priority 藍字代表key
註 : treap節點內的priority是隨機產生的
:::

### 樹長相唯一性證明
:::success

- 對Treap中的結點個數進行歸納證明。
- 當Treap中只有一個結點或沒有結點時形態是唯一的，易得。

- 當Treap中結點個數大於1時，基於我們的假設，結點的priority兩兩不同，所以priority最小的結點一定是Treap的根。那麽根結點的鍵值被確定了，則其左子樹有哪些結點，右子樹有哪些結點也被確定了。基於歸納法，左子樹和右子樹的形態是唯一的，所以該Treap的形態是唯一的。 證畢。
:::

### 期望深度為 $\log_2 n$ 證明
:::spoiler 證明1
- 假設：Treap 滿足大根堆性質。$n$ 個點標號為 $1, 2, 3, ..., n$，第 $i$ 個點的隨機權值為 $w(i)，w(i)$ 在 $[0, 1]$ 均勻隨機，$w(1), w(2), w(3), ..., w(n)$ 互相獨立。如果認為權值為實數（實際應用中 $w(i)$ 值域範圍遠大於 $n$），則兩個點權值相同的概率為 $0$，而深度有限，故可以認為所有點權值兩兩不同，而不影響答案。

- 設 $I(u,\; v)$ 表示 $u$ 是 $v$ 的祖先的事件。如果 $u$ 是 $v$ 的祖先則 $I(u,\; v)=1$，否則為 $0$。
- 則 $v$ 的深度可以寫成 $d(v) = Sum[I(u,\; v),\; {u\in [1,\; n]}]$。利用期望的線性性。計算 $v$ 的期望深度 $:E[d(v)] = Sum[E[I(u,\; v)],\; {u\in [ 1,\; n]}]$, $E[I(u,\; v)] = P([I(u,\; v) = 1])$，即計算 $u$ 是 $v$ 的祖先的概率。不難發現 $u$ 是 $v$ 的祖先當且僅當 $w(u)$ 是 $w(u), w(u+1), w(u+2), ..., w(v)$ 中的最大值（$u < v$。$u > v$ 時類似），可以想象一下 $LCA(u, v)$ 與 $u、v$ 的位置關係。
- $k$ 個 $[0, 1]$ 上均勻隨機的獨立隨機變量中，某一個是最大值的概率為 $\lfloor [(1 - x)^{k - 1}, x\in [0, 1]]\rfloor = \frac{1}{k}$, 即 $E[I(u, v)] = \frac{1}{(|u - v| + 1)}$, 所以 $d(v) <= Sum[\frac{1}{k}, {k\in [1,\; n]}] = O(\log_2 n)$
:::
:::spoiler 證明2
- 令$T(n)為n個節點的Treap的期望深度$
$$T(n)=n+\frac{\sum_{i=1}^{n}T(i-1)+T(n-i)}{n}=n+\frac{2}{n}\sum_{i=0}^{n}T(i)$$

- 將n-1的式子寫出後，兩式相減
$$T(n)-T(n-1)=\frac{2}{n}\sum_{i=0}^{n}T(i)-\frac{2}{n-1}\sum_{i=0}^{n-2}T(i)\leq 1+\frac{2}{n}T(n-1)$$
- 化簡後
$$\frac{T(n)}{n+1}\leq \frac{1}{n+1} + \frac{T(n-1)}{n}\leq \frac{1}{n+1} + \frac{1}{n} + \frac{T(n-2)}{n-1} \leq ...\leq \sum_{i=2}^{n+1}\frac{1}{i} \sim o(\log n) $$
:::

### 實作
:::success
#### treap class

struct Treap {
    Treap* l, *r;
    int pri, key;
    Treap(int _key) {
        l = r = nullptr;
        pri = rand(), key = _key;
    }
};

#### 合併 merge
- 滿足Treap a 中所有的 $key$ 都小於 Treap b 中所有的 $key$

Treap* merge(Treap *a, Treap *b) {
    if (!a || !b) return (a ? a : b); //做完了嗎?
    if (a->pri > b->pri) { //誰要當根?
        a->r = merge(a->r, b); //哪邊還沒做完
        return a;
    }
    else {
        b->l = merge(a, b->l); //哪邊還沒做完
        return b;
    }
} 

- 第三行 `if (a->pri > b->pri)`決定誰當根結點, 假設`a->pri > b->pri`, 則 a 為根節點, 且 b 的 key 都大於 a 的 key, 所以 a 的左子樹就確定是合併後樹堆的左子樹
- 剩下只需處理 a 的右子樹和 b 樹堆(`a->r = merge(a->r, b)`), 反之, `b->l = merge(a, b->l)`
#### 分裂 spilt
- 將樹堆 t 分成 key 皆 $\leq k$ 的樹堆 a 和 $\ k$

void spilt(Treap *t, int k, Treap *&a, Treap *&b) {
    
}

:::