# Binary Search Tree
## 定義
```!
二元搜尋樹（英語：Binary Search Tree），也稱為有序二元樹（ordered binary tree）或排序二元樹（sorted binary tree），是指一棵空樹或者具有下列性質的二元樹：
1. 若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值；
2. 若任意節點的右子樹不空，則右子樹上所有節點的值均大於它的根節點的值；
3. 任意節點的左、右子樹也分別為二元搜尋樹；
```
## Basic operation
這些操作的複雜度都是 $\mathcal{O}(h)$
$h$ 為樹高，理想情況下是 $\log n$
### Structure
```cpp=
struct BST
{
struct node
{
LL value;
node *ln = NULL, *rn = NULL;
node(LL _v) : value(_v) {}
node() {}
};
node *rt = NULL;
};
```
### Insert
新插入的節點總是葉節點
所以根據大小關係決定應該要往哪邊插入就好
```cpp=
void Insert(LL v)
{
if (rt == NULL)
{
rt = new node(v);
return;
}
function<void(node *)> dfs = [&](node *pos)
{
if (v == pos->value)
return;
if (v > pos->value)
{
if (pos->rn != NULL)
dfs(pos->rn);
else
pos->rn = new node(v);
}
else
{
if (pos->ln != NULL)
dfs(pos->ln);
else
pos->ln = new node(v);
}
};
dfs(rt);
}
```
### Delete
找到要被刪除的節點 $p$ 之後
分三個 $\text{case}$ 討論:
1. $p$ 是葉節點(兩子樹皆為空)
2. $p$ 有一子樹為空，另一子樹不為空
3. $p$ 兩子樹皆不為空
#### case 1.
直接把 $p$ 刪除。
#### case 2.
直接把 $p$ 刪除，並把他不空的子樹接到他原本的位置上
#### case 3.
直接把 $p$ 刪除，並找他的**左子樹中最右的節點**或**右子樹中最左的節點**取代掉他
```cpp=
node *findMax(node *pos)
{
if (pos->rn == NULL)
{
return pos;
}
return findMax(pos->rn);
}
void Delete(LL v)
{
function<node *(node *)> dfs = [&](node *pos) -> node *
{
if (pos == NULL)
{
return NULL;
}
if (v == pos->value)
{
if (pos->ln == NULL)
{
if (pos->rn == NULL)
{
return NULL;
}
else
{
return pos->rn;
}
}
else
{
if (pos->rn == NULL)
{
return pos->ln;
}
else
{
node *maxnode = findMax(pos->ln);
pos->value = maxnode->value;
maxnode->value = v;
node *d = dfs(pos->ln);
pos->ln = d;
}
}
}
if (v > pos->value)
{
node *r = dfs(pos->rn);
pos->rn = r;
}
else if (v < pos->value)
{
node *l = dfs(pos->ln);
pos->ln = l;
}
return pos;
};
dfs(rt);
}
```
### Search
就 對阿
```cpp=
bool Search(LL v)
{
function<bool(node *)> dfs = [&](node *pos) -> bool
{
if (pos == NULL)
return 0;
if (pos->value == v)
return 1;
if (pos->value > v)
return dfs(pos->ln);
else
return dfs(pos->rn);
};
return dfs(rt);
}
```
## More
在某些情況下，一棵 $\text{BST}$ 會退化成一條鏈
這導致所有操作的複雜度都變成 $\mathcal{O}(n)$
而**平衡樹**應運而生
### Rotate
幾乎所有平衡樹的操作都基於樹旋轉操作，通過旋轉操作可以使得樹趨於平衡
```cpp=
void left_rotation(node *pos)
{
node *rpos = pos->rn;
node *temp = rpos->ln;
pos->rn = temp;
rpos->ln = pos;
}
```
### Treap
簡單，好寫，基本上是唯一會在比賽出現的 $\text{BST}$
只有兩種基本操作: 分裂與合併
但可以解決絕大部分的序列操作題
也可以做到一項線段樹做不到的事: 區間反轉
[**Cut and Paste**](https://cses.fi/problemset/task/2072)
[**Substring Reversals**](https://cses.fi/problemset/task/2073)
[**Reversals and Sums**](https://cses.fi/problemset/task/2074)
[**Reversal Sorting**](https://cses.fi/problemset/task/2075)
#### Structure
每個節點有兩個值: $\text{pri}$, $\text{value}$
$\text{pri}$ 是一個隨機的數，在 $\text{Treap}$ 中按照 $\text{Heap}$ 的規則排，上大下小
$\text{value}$ 照 $\text{BST}$ 的規則排
說是這樣說但沒人會在乎，因為整棵樹會保持平衡是因為 $\text{pri}$ 的隨機性
所以都會多維護一個 $\text{size}$ ，這樣比較好用，才能做到區間反轉
```cpp=
struct node
{
LL pri, sz;
LL v;
node *ln, *rn;
node(LL ch) : v(ch)
{
pri = rng();
ln = rn = NULL;
sz = 1;
}
};
```
#### Implement
```cpp=
struct node
{
LL pri, sz;
LL v;
node *ln, *rn;
node(LL ch) : v(ch)
{
pri = rng();
ln = rn = NULL;
sz = 1;
ans = v;
}
};
void pull(node *x)
{
if (!x)
return;
LL s = 1;
if (x->ln)
s += x->ln->sz;
if (x->rn)
s += x->rn->sz;
x->sz = s;
}
node *merge(node *a, node *b)
{
if (!a || !b)
return a ? a : b;
if (a->pri > b->pri)
{
a->rn = merge(a->rn, b);
pull(a);
return a;
}
else
{
b->ln = merge(a, b->ln);
pull(b);
return b;
}
}
void split(node *x, LL k, node *&a, node *&b)
{
if (x == NULL)
{
a = b = NULL;
return;
}
LL s = 1;
if (x->ln)
{
s += x->ln->sz;
}
if (s <= k)
{
a = x;
split(x->rn, k - s, a->rn, b);
}
else
{
b = x;
split(x->ln, k, a, b->ln);
}
pull(a);
pull(b);
}
```
要做區間反轉就打個懶標，然後直接把左右子樹交換
#### Ans
[**Cut and Paste**](https://cses.fi/problemset/task/2072)
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define LL long long
mt19937 rng(time(NULL));
struct node
{
char c;
LL sz = 1, pri;
node *ln, *rn;
node(char v)
{
c = v;
ln = rn = NULL;
pri = rng();
}
void pull()
{
sz = 1;
if (ln)
{
sz += ln->sz;
}
if (rn)
{
sz += rn->sz;
}
}
};
node *merge(node *a, node *b)
{
if (!a || !b)
return a ? a : b;
if (a->pri > b->pri)
{
a->rn = merge(a->rn, b);
a->pull();
return a;
}
else
{
b->ln = merge(a, b->ln);
b->pull();
return b;
}
}
void spilt(node *x, LL k, node *&a, node *&b)
{
if (x == NULL)
{
a = b = NULL;
return;
}
LL t = 1;
x->pull();
if (x->ln)
{
t += x->ln->sz;
}
if (t <= k)
{
a = x;
spilt(x->rn, k - t, a->rn, b);
a->pull();
}
else
{
b = x;
spilt(x->ln, k, a, b->ln);
b->pull();
}
}
void out(node *a)
{
if (a->ln)
out(a->ln);
cout << a->c;
if (a->rn)
out(a->rn);
}
int main()
{
LL n, q;
cin >> n >> q;
string s;
cin >> s;
node *rt = NULL;
for (int i = 0; i < n; i++)
{
rt = merge(rt, new node(s[i]));
}
while (q--)
{
LL l, r;
cin >> l >> r;
--l;
node *a, *b, *c, *d;
spilt(rt, r, a, b);
spilt(a, l, c, d);
rt = merge(merge(c, b), d);
}
out(rt);
cout << endl;
}
```
[**Substring Reversals**](https://cses.fi/problemset/task/2073)
```cpp=
#include <bits/stdc++.h>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;
#define LL int_fast64_t
#define pLL pair<long long, long long>
#define F first
#define S second
#define pb push_back
#define rz resize
#define all(x) x.begin(), x.end()
#define DEBU
#ifndef DEBUG
#define endl '\n'
#endif
const LL inv2 = 500000004;
void Star_Brust_Stream()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
mt19937 rng(time(0));
struct node
{
LL pri;
char v;
LL sz;
bool rev;
node *ln, *rn;
node(char vv) : v(vv)
{
sz = 1;
ln = rn = NULL;
pri = rng();
rev = 0;
}
void pull()
{
sz = 1;
if (ln)
sz += ln->sz;
if (rn)
sz += rn->sz;
}
void push()
{
if (rev)
{
if (ln)
{
ln->rev ^= 1;
swap(ln->ln, ln->rn);
}
if (rn)
{
rn->rev ^= 1;
swap(rn->ln, rn->rn);
}
rev = 0;
}
}
};
void rev(node *x)
{
if (x)
{
x->rev ^= 1;
swap(x->ln, x->rn);
}
}
node *merge(node *a, node *b)
{
if (!a || !b)
return a ? a : b;
b->push();
a->push();
if (a->pri > b->pri)
{
a->rn = merge(a->rn, b);
a->pull();
return a;
}
else
{
b->ln = merge(a, b->ln);
b->pull();
return b;
}
}
void spilt(node *x, LL k, node *&a, node *&b)
{
if (x == NULL)
{
a = b = NULL;
return;
}
LL t = 1;
if (x->ln)
t += x->ln->sz;
x->push();
if (t <= k)
{
a = x;
spilt(x->rn, k - t, a->rn, b);
a->pull();
}
else
{
b = x;
spilt(x->ln, k, a, b->ln);
b->pull();
}
}
void out(node *a)
{
if (!a)
return;
a->push();
if (a->ln)
out(a->ln);
cout << a->v;
if (a->rn)
out(a->rn);
}
int main()
{
LL n, q;
cin >> n >> q;
string v;
cin >> v;
node *rt = NULL;
for (int i = 0; i < n; i++)
{
rt = merge(rt, new node(v[i]));
}
while (q--)
{
LL l, r;
cin >> l >> r;
if (r == l)
{
continue;
}
l--;
r--;
node *a, *b, *c, *d;
spilt(rt, l, a, b);
spilt(b, r - l + 1, c, d);
rev(c);
rt = merge(a, merge(c, d));
}
out(rt);
cout << endl;
#ifdef DEBUG
system("pause");
#endif
return 0;
}
```
[**Reversals and Sums**](https://cses.fi/problemset/task/2074)
```cpp=
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_cxx;
using namespace std;
#define LL long long
#define pLL pair<LL, LL>
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define rz resize
#define DEBU
#ifndef DEBUG
#define endl '\n'
#endif
mt19937 rng(time(0));
void Star_Brust_Stream()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
const LL MOD = 1e9 + 7;
const LL INF = 1e18;
struct node
{
LL pri, sz, lz, ans;
LL v;
node *ln, *rn;
node(LL ch) : v(ch)
{
lz = 0;
pri = rng();
ln = rn = NULL;
sz = 1;
ans = v;
}
};
void pull(node *x)
{
if (!x)
return;
LL s = 1;
x->ans = x->v;
if (x->ln)
{
s += x->ln->sz;
x->ans += x->ln->ans;
}
if (x->rn)
{
s += x->rn->sz;
x->ans += x->rn->ans;
}
x->sz = s;
}
void rev(node *x)
{
if (x)
{
x->lz ^= 1;
swap(x->ln, x->rn);
pull(x);
}
}
void push(node *x)
{
if (x->lz == 0)
return;
rev(x->ln);
rev(x->rn);
x->lz = 0;
}
node *merge(node *a, node *b)
{
if (!a || !b)
return a ? a : b;
push(a);
push(b);
if (a->pri > b->pri)
{
a->rn = merge(a->rn, b);
pull(a);
return a;
}
else
{
b->ln = merge(a, b->ln);
pull(b);
return b;
}
}
void spilt(node *x, LL k, node *&a, node *&b)
{
if (x == NULL)
{
a = b = NULL;
return;
}
push(x);
LL s = 1;
if (x->ln)
{
s += x->ln->sz;
}
if (s <= k)
{
a = x;
spilt(x->rn, k - s, a->rn, b);
}
else
{
b = x;
spilt(x->ln, k, a, b->ln);
}
pull(a);
pull(b);
}
int main()
{
Star_Brust_Stream();
LL n, q;
cin >> n >> q;
vector<LL> s(n);
for (int i = 0; i < n; i++)
{
cin >> s[i];
}
node *rt = new node(s[0]);
for (int i = 1; i < n; i++)
{
rt = merge(rt, new node(s[i]));
}
while (q--)
{
LL t;
cin >> t;
if (t == 1)
{
LL l, r;
cin >> l >> r;
if (r == l)
continue;
--l;
--r;
node *a, *b, *c, *d;
spilt(rt, l, a, b);
spilt(b, r - l + 1, c, d);
rev(c);
rt = merge(a, merge(c, d));
}
else
{
LL l, r;
cin >> l >> r;
--l;
--r;
node *a, *b, *c, *d;
spilt(rt, l, a, b);
spilt(b, r - l + 1, c, d);
if (c != NULL)
{
pull(c);
cout << c->ans << endl;
}
else
{
cout << 0 << endl;
}
rt = merge(a, merge(c, d));
}
}
#ifdef DEBUG
system("pause");
#endif
return 0;
}
```
[**Reversal Sorting**](https://cses.fi/problemset/task/2075)
```cpp=
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
#define LL int
#define pLL pair<LL, LL>
#define F first
#define S second
#define pb push_back
#define rz resize
#define all(x) x.begin(), x.end()
#define CH cout << "I am here!" << endl;
// here!!!
#define DEBUG
#ifndef DEBUG
#define endl '\n'
#endif
const long long inv2 = 500000004; // mod 1e9+7
const long long MOD = 1e9 + 7;
const long long INF = 1e18;
void Moto_Hai_ya_ku()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
template <typename T>
void ls(T &v)
{
for (auto i : v)
cout << i << " ";
cout << endl;
}
template <typename T, typename... Args>
void ls(T &v, const Args &...args)
{
for (auto i : v)
cout << i << " ";
cout << endl;
ls(args...);
}
mt19937 rng(time(0));
struct node
{
node *ln = NULL, *rn = NULL;
LL v, ans, pri, sz = 1, lz = 0;
node(LL _v) : v(_v), ans(_v) { pri = rng(); }
};
void pull(node *x)
{
if (!x)
return;
LL temp = x->v;
x->sz = 1;
if (x->ln)
{
temp = min(temp, x->ln->ans);
x->sz += x->ln->sz;
}
if (x->rn)
{
temp = min(temp, x->rn->ans);
x->sz += x->rn->sz;
}
x->ans = temp;
}
void rev(node *x)
{
if (x)
{
x->lz ^= 1;
swap(x->ln, x->rn);
pull(x);
}
}
void push(node *x)
{
if (!x || x->lz == 0)
return;
rev(x->ln);
rev(x->rn);
x->lz = 0;
}
node *merge(node *a, node *b)
{
if (!a || !b)
return a ? a : b;
push(a);
push(b);
if (a->pri > b->pri)
{
a->rn = merge(a->rn, b);
pull(a);
return a;
}
else
{
b->ln = merge(a, b->ln);
pull(b);
return b;
}
}
void split(node *x, LL k, node *&a, node *&b)
{
if (x == NULL)
{
a = b = NULL;
return;
}
push(x);
LL s = 1;
if (x->ln)
{
s += x->ln->sz;
}
if (s <= k)
{
a = x;
split(x->rn, k - s, a->rn, b);
}
else
{
b = x;
split(x->ln, k, a, b->ln);
}
pull(a);
pull(b);
}
LL ask(node *x, LL k)
{
push(x);
pull(x);
if (x->v == k)
return (x->ln ? x->ln->sz : 0) + 1;
if (x->ln)
{
if (x->ln->ans == k)
{
return ask(x->ln, k);
}
}
if (x->rn)
{
if (x->rn->ans == k)
{
return ask(x->rn, k) + x->sz - x->rn->sz;
}
}
}
void sol()
{
LL n;
cin >> n;
vector<LL> v(n);
for (int i = 0; i < n; i++)
{
cin >> v[i];
}
node *p = NULL;
for (int i = 0; i < n; i++)
{
p = merge(p, new node(v[i]));
}
cout << n << endl;
for (int i = 0; i < n; i++)
{
node *a, *b, *c, *x;
split(p, i, a, b);
LL r = ask(b, i + 1);
split(b, r, x, c);
rev(x);
p = merge(a, merge(x, c));
cout << i + 1 << " " << i + r << endl;
}
}
int main()
{
Moto_Hai_ya_ku();
LL t = 1;
// cin >> t;
while (t--)
{
sol();
}
#ifdef DEBUG
system("pause");
#endif
return 0;
}
```
### AVL Tree
從這裡開始可以當聽故事就好
AVL樹是中最早被發明的自平衡二元搜尋樹。在AVL樹中，任一節點對應的兩棵子樹的最大高度差為 $1$，因此它也被稱為高度平衡樹。
寫起來很麻煩，光 $\text{BST}$ 就夠麻煩了還要左旋右旋，還要分四個情況看怎麼轉
```cpp=
struct node
{
node *l, *r;
LL v, h, re;
node(node *_l, node *_r, LL _v, LL _h, LL _re) : l(_l), r(_r), v(_v), h(_h), re(_re) {}
};
node *nullnode = new node(nullnode, nullnode, 0, -1, 0);
node *left_rotation(node *pos)
{
node *rpos = pos->r;
node *temp = rpos->l;
pos->r = temp;
rpos->l = pos;
pos->h = max(pos->l->h, pos->r->h) + 1;
rpos->h = max(rpos->l->h, rpos->r->h) + 1;
return rpos;
}
node *right_rotation(node *pos)
{
node *lpos = pos->l;
pos->l = lpos->r;
lpos->r = pos;
pos->h = max(pos->l->h, pos->r->h) + 1;
lpos->h = max(lpos->l->h, lpos->r->h) + 1;
return lpos;
}
node *findMax(node *pos)
{
if (pos->r == nullnode)
{
return pos;
}
return findMax(pos->r);
}
node *update(node *pos)
{
LL bf = pos->l->h - pos->r->h;
if (bf < -1)
{
if (pos->r != nullnode && pos->r->r != nullnode)
{
return left_rotation(pos);
}
else
{
pos->r = right_rotation(pos->r);
return left_rotation(pos);
}
}
if (bf > 1)
{
if (pos->l != nullnode && pos->l->l != nullnode)
{
return right_rotation(pos);
}
else
{
pos->l = left_rotation(pos->l);
return right_rotation(pos);
}
}
return pos;
}
node *AVL_insert(node *pos, LL tar)
{
if (pos == nullnode)
{
return new node(nullnode, nullnode, tar, 0, 1);
}
if (tar > pos->v)
{
node *r = AVL_insert(pos->r, tar);
pos->r = r;
}
else if (tar < pos->v)
{
node *l = AVL_insert(pos->l, tar);
pos->l = l;
}
else
{
pos->re++;
}
pos->h = max(pos->l->h, pos->r->h) + 1;
pos = update(pos);
return pos;
}
node *AVL_delete(node *pos, LL tar)
{
if (pos == nullnode)
{
return nullnode;
}
if (tar == pos->v)
{
if (pos->l == nullnode)
{
if (pos->r == nullnode)
{
return nullnode;
}
else
{
return pos->r;
}
}
else
{
if (pos->r == nullnode)
{
return pos->l;
}
else
{
node *maxnode = findMax(pos->l);
pos->v = maxnode->v;
maxnode->v = tar;
node *d = AVL_delete(pos->l, tar);
pos->l = d;
}
}
}
if (tar > pos->v)
{
node *r = AVL_delete(pos->r, tar);
pos->r = r;
}
else if (tar < pos->v)
{
node *l = AVL_delete(pos->l, tar);
pos->l = l;
}
pos->h = max(pos->l->h, pos->r->h) + 1;
pos = update(pos);
return pos;
}
LL AVL_search(node *pos, LL tar)
{
if (pos == nullnode)
{
return 0;
}
if (pos->v == tar)
{
return pos->re;
}
if (tar > pos->v)
{
AVL_search(pos->r, tar);
}
else
{
AVL_search(pos->l, tar);
}
}
node *rt = nullnode;
```
### Red–black tree
除了 $\text{BST}$ 的限制外還加了以下五條
1. 節點是紅色或黑色。
2. 根是黑色。
3. 所有葉子都是黑色（葉子是 $\text{NIL}$ 節點）。
4. 每個紅色節點必須有兩個黑色的子節點。
5. 從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點。
比剛剛還麻煩 插入要分 $5$ 個狀況，刪除要分 $6$ 個
還要牽扯到一大堆節點和旋轉
你有聽說過叔父節點的嗎
$\text{STL}$ 中的 $\text{Map}$ 內部就是一顆紅黑樹
沒有 $\text{Code}$
### Scapegoat tree
替罪羊樹，在每次操作後檢查路徑，如果有一個點不平衡就整個子樹打掉重蓋成完全二叉樹
更精確地說，找到最高的節點滿足 $\max(size(ln),size(rn)) \gt \alpha \times size(self)$，並把他拆掉重蓋
$\alpha$ 一般會選擇 $0.7$ 左右
### Splay tree
伸展樹是一種自調整形式的二元搜尋樹，它會沿著從某個節點到樹根之間的路徑，通過一系列的旋轉把這個節點搬移到樹根去。
[**直接偷學長的講義**](https://hackmd.io/-J-B0fdRRSSJ-vccsiE8bw?view#Splay-Tree)
### Heap (雖然他不是 BST)
$\text{Heap}$ (堆積) 有分成兩種
一種是最小堆積 $\text{Min Heap}$，另一種是最大堆積 $\text{Max Heap}$。
如下圖，完全二元樹所有的父節點都比子節點要小，就屬於最小堆積。
而最大堆積則相反
[什麼是完全二元樹](https://zh.wikipedia.org/zh-tw/%E4%BA%8C%E5%8F%89%E6%A0%91#%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91)
$\text{STL}$ 中的 $\text{Priority queue}$ 內部就是一個 $\text{Heap}$
#### Insert
以最小堆積 $\text{Min Heap}$ 為例:
先接在葉節點的位置，然後開始往上比較，如果比父節點還小就將兩者交換，直到碰到根結點為止
#### pop
拿最右下的節點放到根的位置，然後開始往下比較
如果比自己子節點大的話就和兩者之間小的那個交換
直到成為葉節點為止
#### Time complexity
兩種操作皆為 $O(\log n)$
## 沒了
Sign in with Wallet
Connect another wallet