BST的性质
树上每个节点上有个值，这个值叫关键码
每个节点的关键码大于其任意左侧子节点的关键码，小于其任意右节点的关键码。
显然一个BST的中序遍历就是关键码单调递增的节点序列
BST的建立
为了避免越界其实好像没卵用,减少边界情况的判定，一般在BST中额外插入一个关键码为INF和-INF的节点
const int N=1000000;
struct BST
{
int l,r;//l,r分别是左右孩子的编号
int val;//关键码
}a[N];
int tot,root,INF=1<<30;
int New(int val)
{
a[++tot].val=val;
return tot;
}
void build()
{
New(-INF),New(INF);
root=1,a[1].r=2;
}
BST的检索
在BST中检索是否存在关键码为val的节点
设p为根节点
1.若p的关键码等于(val)，直接返回
2.若p的关键码大于(val)
(1)若(p)的左子节点为空，则不存在
(2)若(p)的左子节点不为空，则在p的左子树中递归检索
2.若p的关键码小于(val)
(1)若(p)的右子节点为空，则不存在
(2)若(p)的右子节点不为空，则在(p)的右子树中递归检索
int get(int p,int val)
{
if(p==0) return 0;
if(val==a[p].val) return p;
return val<a[p].val ? get(a[p].l,val) : get(a[p].r,val);
}
BST的插入
在BST中插入关键码为val的节点
与BST的检索的检索过程类似，这里就不在赘述
void insert(int &p,int val)
{
if(p==0)
{
p=New(val);
return ;
}
if(val==a[p].val) return;
val<a[p].val ? insert(a[p].l,val) : insert(a[p].r,val);
}
细心的读者应该发现了p是引用的,why?
因为这里父节点的l或r值会被更新
BST求前驱/后继
这里首先赘述一下什么是前驱和后继
后继:BST中关键码大于val的最小的
前驱:BST中关键码小于val的最大的
这里以求后继为例
初始化ans为正无穷关键码的那个节点的编号。然后在BST中检索val,检索过程中不断更新ans
检索完成后有三种可能的结果
1.没有找到(val)，那么现在ans即为所求
2.找到了(val)，但是关键码为val的节点p没有右子树，那ans即为所求
3.找到了(val)，而且关键码为val的节点p有右子树,那么就要从p的右孩子一直向左找
因为教育局把sm.ms图床给封了所以图片上传不了,抱歉
int getnext(int val)
{
int ans=2,p=root;
while(p)
{
if(val==a[p].val)
{
if(a[p].r>0)
{
p=a[p].r;
while(a[p].l>0) p=a[p].l;
ans=p;
}
break;
}
if(a[p].val>val&&a[p].val<a[ans].val) ans=p;
p=val<a[p].val ? a[p].l : a[p].r;
}
return ans;
}
上面的代码是用的非递归，以后有时间可能会补上递归的
前驱同理，这里不再赘述。
BST的节点删除
从BST中删除关键码为val的节点
首先检索出关键码为val的节点p来
有以下几种情况
1.如果p的子节点个数小于(2),则直接删除掉(p),并令(p)的子节点替代(p)的位置，与(p)的父节点相连
2.(p)既有左子树又有右子树，那么就找出(val)的后继来，显然后继没有左子树，所以直接删除后继，然后让后继的右子树代替游记，然后让后继代替(p)
没法传图，抱歉*2
void remove(int &p,int val)
{
if(p==0) return ;
if(val==a[p].val)
{
if(a[p].l==0) p=a[p].r;
else if(a[p].r==0) p=a[p].l;
else
{
int next=a[p].r;
while(a[next].l>0) next=a[p].l;
remove(a[p].r,a[next].val);
a[next].l=a[p].l,a[next].r=a[p].r;
p=next;
}
return ;
}
if(val<a[p].val) remove(a[p].l,val);
else remove(a[p].r,val);
}
细心的读者可能发现了，上述代码只能处理没有重复的关键值的情况，其实处理重复的关键值也很简单，这需要记录一个(cnt)即可
struct BST
{
int l,r;//l,r分别是左右孩子的编号
int val;//关键码
int cnt;//计数器
}a[N];
其他操作不再赘述
复杂度
显然BST一次操作复杂度为(O(log N))。
但是BST容易被有序数列卡成(O(N))的，这时树就变成一条链了
这是就可以用平衡树解决.....以后或许会更一篇平衡树的博客（前提是我要学会）
参考《算法竞赛进阶指南》,代码未经测试不保证正确性，如有错误还望指正（狗头保命）