二叉搜索树 Binary Search Tree 总结
## 定义
二叉搜索树是一种二叉树的树形数据结构。定义如下：
- 空树或左右子树都是二叉搜索树的二叉树是二叉搜索树。
- 二叉搜索树的左子树上的结点的权值都小于其根节点的权值。
- 二叉搜索树的右子树上的结点的权值都大于其根节点的权值。
而一个有 $n$ 个结点的二叉搜索树的时间复杂度最优情况下为 $O(\log n)$。但当二叉搜索树为链状时时间复杂度最坏，为 $O(n)$。
## 存储
我的写法（其实是 wx 和锹的）是用结构体，分别存储一个结点的父亲、左右儿子和权值。
```c++
const int SON=2;
struct BST
{
int fa,ch[SON];//ch[0]为左儿子，ch[1]为右儿子。
int val;
}bst[MAXN];
```
## 详细操作
### 1.遍历
这里主要写的是前序遍历和中序遍历。
前序非常简单啊，根据定义就可以了。先输出当前结点的权值，再通过递归先遍历左子树，再遍历右子树。中序就是先左子树，再输出当前结点，再右子树。
```c++
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]);
}
```
### 2.查找
根据二叉搜索树的定义，我们只需要先比较根节点与要查找的元素的值。如果小于根节点，就跳到左子树。大于就跳到右子树，一直这样下去直到找到这个元素。
然而查找的写法肯定是先想到的递归，这里写的是用 `while` 的方法。
```c++
int find(int v)
{
int x=root;
if(!x) return x;
bool temp=v>bst[x].val;//temp存储要查找的元素是否大于当前结点的权值。
while(v!=bst[x].val&&bst[x].ch[temp])
{
x=bst[x].ch[temp];//更新x找到下一个结点。
temp=v>bst[x].val;//更新temp。
}
return x;
}
```
### 3.插入
想要在二叉搜索树中插入一个元素，首先应该找到在哪插。这只需要用到前面查找时用的方法，一直找直到为空。而 `while` 循环会直到为空才会退出，所以在循环时需要另定义一个变量 $y$ 来更新当前结点 $x$ 的父亲。
找到位置后，我们先需要初始化。将它的权值赋为插入的值，将它的父亲、左右儿子初始化为 $0$，同时增加结点数。这个可以写成一个函数。
```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;//这里返回的是新的结点数量，用于插入时更新
}
```
之后我们要分类讨论。当是空树的情况时，故当 $y$ 等于 $0$ 时，这需要更新根节点为 $x$。另外就只需判断 $x$ 与要插入的值的大小就行了，即判断是插在左子树还是右子树。最后更新新结点的父亲。
完整代码：
```c++
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;
}
```
### 4.删除
啊首先就是要分类讨论，分别是删除的结点没有儿子、有一个儿子，有两个儿子。
如果该结点没有儿子，则将它的父亲的子节点改为 $0$。
如果只有一个儿子，连接该结点的父亲和它的子节点。
如果该结点有两个儿子，找到该结点的后继，删除其后继，将该结点的“遗产”都转给它的后继。
啊那要怎么找后继呢。
一个结点的后继的定义是在整棵树中大于该结点的最小结点，在结合二叉搜索树的定义，我们可以发现，要找一个结点的后继，首先找到它的右儿子（右子树上的所有结点一定大于它的根节点），再一直往左儿子方向遍历，直到没有左儿子（深度越大的左儿子越小）。
```c++
int successor(int x)
{
x=bst[x].ch[1];//先往右。
while(bst[x].ch[0]) x=bst[x].ch[0];//然后一直往左跑，直到没有左儿子。
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;//用后继替代要删除的结点。
}
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;//连接它的父亲与它的儿子（也就是直接跳过该结点，不看它）。
}
```
## 总结
啊这样的话二叉搜索树的板子最终版就完成了！！！
```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;
}
```
啊看到这里你会发现，我写的 BST 巨长，而且呢，巨烂无比，啊还要防止退化成链。但是呢，亲爱的 TQ 没给我们讲跷跷板树。。。
等我学会了平衡树就来补。。。
