## 定義

二叉搜索樹是一種二叉樹的樹形數(shù)據(jù)結(jié)構(gòu)。定義如下：

- 空樹或左右子樹都是二叉搜索樹的二叉樹是二叉搜索樹。

- 二叉搜索樹的左子樹上的結(jié)點(diǎn)的權(quán)值都小于其根節(jié)點(diǎn)的權(quán)值。

- 二叉搜索樹的右子樹上的結(jié)點(diǎn)的權(quán)值都大于其根節(jié)點(diǎn)的權(quán)值。

而一個有 $n$ 個結(jié)點(diǎn)的二叉搜索樹的時間復(fù)雜度最優(yōu)情況下為 $O(\log n)$。但當(dāng)二叉搜索樹為鏈狀時時間復(fù)雜度最壞，為 $O(n)$。

## 存儲

我的寫法（其實(shí)是 wx 和鍬的）是用結(jié)構(gòu)體，分別存儲一個結(jié)點(diǎn)的父親、左右兒子和權(quán)值。

```c++

const int SON=2;

struct BST

{

int fa,ch[SON];//ch[0]為左兒子，ch[1]為右兒子。

int val;

}bst[MAXN];

```

## 詳細(xì)操作

### 1.遍歷

這里主要寫的是前序遍歷和中序遍歷。

前序非常簡單啊，根據(jù)定義就可以了。先輸出當(dāng)前結(jié)點(diǎn)的權(quán)值，再通過遞歸先遍歷左子樹，再遍歷右子樹。中序就是先左子樹，再輸出當(dāng)前結(jié)點(diǎn)，再右子樹。

```c++

void Love_Theory(int x)

{//前序。

if(!x) return ;//遇到葉結(jié)點(diǎn)就返回。

printf(" %lld",bst[x].val);

Love_Theory(bst[x].ch[0]);

Love_Theory(bst[x].ch[1]);

}

void Love_Elegia(int x)

{//中序。

if(!x) return ;

Love_Elegia(bst[x].ch[0]);

printf(" %lld",bst[x].val);

Love_Elegia(bst[x].ch[1]);

}

```

### 2.查找

根據(jù)二叉搜索樹的定義，我們只需要先比較根節(jié)點(diǎn)與要查找的元素的值。如果小于根節(jié)點(diǎn)，就跳到左子樹。大于就跳到右子樹，一直這樣下去直到找到這個元素。

然而查找的寫法肯定是先想到的遞歸，這里寫的是用 `while` 的方法。

```c++

int find(int v)

{

int x=root;

if(!x) return x;

bool temp=v>bst[x].val;//temp存儲要查找的元素是否大于當(dāng)前結(jié)點(diǎn)的權(quán)值。

while(v!=bst[x].val&&bst[x].ch[temp])

{

x=bst[x].ch[temp];//更新x找到下一個結(jié)點(diǎn)。

temp=v>bst[x].val;//更新temp。

}

return x;

}

```

### 3.插入

想要在二叉搜索樹中插入一個元素，首先應(yīng)該找到在哪插。這只需要用到前面查找時用的方法，一直找直到為空。而 `while` 循環(huán)會直到為空才會退出，所以在循環(huán)時需要另定義一個變量 $y$ 來更新當(dāng)前結(jié)點(diǎn) $x$ 的父親。

找到位置后，我們先需要初始化。將它的權(quán)值賦為插入的值，將它的父親、左右兒子初始化為 $0$，同時增加結(jié)點(diǎn)數(shù)。這個可以寫成一個函數(shù)。

```c++

int new_node(int v)

{

int x=++bst_cnt;

bst[x].val=v;

bst[x].fa=bst[x].ch[0]=bst[x].ch[1]=0;

return x;//這里返回的是新的結(jié)點(diǎn)數(shù)量，用于插入時更新

}

```

之后我們要分類討論。當(dāng)是空樹的情況時，故當(dāng) $y$ 等于 $0$ 時，這需要更新根節(jié)點(diǎn)為 $x$。另外就只需判斷 $x$ 與要插入的值的大小就行了，即判斷是插在左子樹還是右子樹。最后更新新結(jié)點(diǎn)的父親。

完整代碼：

```c++

void insert(int v)

{

int x=root,y=0;//從根節(jié)點(diǎn)開始找。

while(x&&bst[x].val!=v)

{

y=x;

bool temp=v>bst[x].val;

x=bst[x].ch[temp];

}

x=new_node(v);

if(!y) root=x;

else

{

bool temp=v>bst[y].val;

bst[y].ch[temp]=x;

}

bst[x].fa=y;

}

```

### 4.刪除

啊首先就是要分類討論，分別是刪除的結(jié)點(diǎn)沒有兒子、有一個兒子，有兩個兒子。

如果該結(jié)點(diǎn)沒有兒子，則將它的父親的子節(jié)點(diǎn)改為 $0$。

如果只有一個兒子，連接該結(jié)點(diǎn)的父親和它的子節(jié)點(diǎn)。

如果該結(jié)點(diǎn)有兩個兒子，找到該結(jié)點(diǎn)的后繼，刪除其后繼，將該結(jié)點(diǎn)的“遺產(chǎn)”都轉(zhuǎn)給它的后繼。

啊那要怎么找后繼呢。

一個結(jié)點(diǎn)的后繼的定義是在整棵樹中大于該結(jié)點(diǎn)的最小結(jié)點(diǎn)，在結(jié)合二叉搜索樹的定義，我們可以發(fā)現(xiàn)，要找一個結(jié)點(diǎn)的后繼，首先找到它的右兒子（右子樹上的所有結(jié)點(diǎn)一定大于它的根節(jié)點(diǎn)），再一直往左兒子方向遍歷，直到?jīng)]有左兒子（深度越大的左兒子越?。?。

```c++

int successor(int x)

{

x=bst[x].ch[1];//先往右。

while(bst[x].ch[0]) x=bst[x].ch[0];//然后一直往左跑，直到?jīng)]有左兒子。

return x;

}

```

啊這樣的話刪除操作的代碼我們也可以寫出來了。

```c++

int x=read();

x=find(x);

int y=bst[x].fa;

if((!bst[x].ch[0])&&(!bst[x].ch[1]))

{//沒有兒子。

bool temp=bst[x].val>bst[y].val;

bst[y].ch[temp]=0;//把它爹砍了。

}

else if(bst[x].ch[0]&&bst[x].ch[1])

{//有兩個兒子。

int z=successor(x);//找后繼

int z_fa=bst[z].fa;

bool temp=bst[z].val>bst[z_fa].val;

bst[z_fa].ch[temp]=bst[z].ch[1];

if(bst[z].ch[1]) bst[bst[z].ch[1]].fa=z_fa;//刪除后繼。

bst[z].fa=bst[x].fa;

? ? bst[z].ch[0]=bst[x].ch[0];

? ? bst[z].ch[1]=bst[x].ch[1];

? ??

? ? temp=bst[x].val>bst[y].val;

? ? if(y) bst[y].ch[temp]=z;

? ? if(bst[z].ch[0]) bst[bst[z].ch[0]].fa=z;

? ? if(bst[z].ch[1]) bst[bst[z].ch[1]].fa=z;//用后繼替代要刪除的結(jié)點(diǎn)。

}

else?

{//只有一個兒子。

int z;

? ? if(bst[x].ch[0]) z=bst[x].ch[0];

? ? else z=bst[x].ch[1];//判一下是有左兒子還是右兒子。

? ? bool temp=bst[x].val>bst[y].val;

? ? bst[y].ch[temp]=z;

? ? bst[z].fa=y;//連接它的父親與它的兒子（也就是直接跳過該結(jié)點(diǎn)，不看它）。

}

```

## 總結(jié)

啊這樣的話二叉搜索樹的板子最終版就完成了?。?！

```c++

/*

ID: enderch1

PROG:

LANG: C++

*/

#include<bits/stdc++.h>

#define change_max(a,b) a=max(a,b)

#define change_min(a,b) a=min(a,b)

#define int long long

using namespace std;

const int MAXN=500005;

const int SON=2;

struct BST

{

int fa,ch[SON];

int val;

}bst[MAXN];

int root,bst_cnt;

int new_node(int v)

{

int x=++bst_cnt;

bst[x].val=v;

bst[x].fa=bst[x].ch[0]=bst[x].ch[1]=0;

return x;

}

void insert(int v)

{

int x=root,y=0;

while(x&&bst[x].val!=v)

{

y=x;

bool temp=v>bst[x].val;

x=bst[x].ch[temp];

}

x=new_node(v);

if(!y) root=x;

else

{

bool temp=v>bst[y].val;

bst[y].ch[temp]=x;

}

bst[x].fa=y;

}

int find(int v)

{

int x=root;

if(!x) return x;

bool temp=v>bst[x].val;

while(v!=bst[x].val&&bst[x].ch[temp])

{

x=bst[x].ch[temp];

temp=v>bst[x].val;

}

return x;

}

void Love_Theory(int x)

{

if(!x) return ;

printf(" %lld",bst[x].val);

Love_Theory(bst[x].ch[0]);

Love_Theory(bst[x].ch[1]);

}

void Love_Elegia(int x)

{

if(!x) return ;

Love_Elegia(bst[x].ch[0]);

printf(" %lld",bst[x].val);

Love_Elegia(bst[x].ch[1]);

}

int successor(int x)

{

x=bst[x].ch[1];

while(bst[x].ch[0]) x=bst[x].ch[0];

return x;

}

int read()

{

? ? int s=0,w=1;

? ? char ch=getchar();

? ? while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}

? ? while(ch>='0'&&ch<='9') {s=s*10+ch-'0';ch=getchar();}

? ? return s*w;

}

void solve()

{

int T=read();

while(T--)

{

string s;

cin>>s;

if(s=="insert")

{

int x=read();

insert(x);

}

else if(s=="find")

{

int x=read();

int temp=find(x);

if(x==bst[temp].val) puts("yes");

else puts("no");

}

else if(s=="delete")

{

int x=read();

x=find(x);

int y=bst[x].fa;

if((!bst[x].ch[0])&&(!bst[x].ch[1]))

{

bool temp=bst[x].val>bst[y].val;

bst[y].ch[temp]=0;

}

else if(bst[x].ch[0]&&bst[x].ch[1])

{

int z=successor(x);

int z_fa=bst[z].fa;

bool temp=bst[z].val>bst[z_fa].val;

bst[z_fa].ch[temp]=bst[z].ch[1];

if(bst[z].ch[1]) bst[bst[z].ch[1]].fa=z_fa;

? ? ? ? ? ? ? ? bst[z].fa=bst[x].fa;

? ? ? ? ? ? ? ? bst[z].ch[0]=bst[x].ch[0];

? ? ? ? ? ? ? ? bst[z].ch[1]=bst[x].ch[1];

? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? temp=bst[x].val>bst[y].val;

? ? ? ? ? ? ? ? if(y) bst[y].ch[temp]=z;

? ? ? ? ? ? ? ? if(bst[z].ch[0]) bst[bst[z].ch[0]].fa=z;

? ? ? ? ? ? ? ? if(bst[z].ch[1]) bst[bst[z].ch[1]].fa=z;

}

? ? ? ? ? ? else?

{

int z;

? ? ? ? ? ? ? ? if(bst[x].ch[0]) z=bst[x].ch[0];

? ? ? ? ? ? ? ? else z=bst[x].ch[1];

? ? ? ? ? ? ? ? bool temp=bst[x].val>bst[y].val;

? ? ? ? ? ? ? ? bst[y].ch[temp]=z;

? ? ? ? ? ? ? ? bst[z].fa=y;

? ? ? ? ? ? }

}

else

{

Love_Elegia(root);

putchar('\n');

Love_Theory(root);

putchar('\n');

}

}

}

signed main()

{

solve();

return 0;

}

```

啊看到這里你會發(fā)現(xiàn)，我寫的 BST 巨長，而且呢，巨爛無比，啊還要防止退化成鏈。但是呢，親愛的 TQ 沒給我們講蹺蹺板樹。。。

等我學(xué)會了平衡樹就來補(bǔ)。。。