二叉搜索树(BST)
它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
性质：中序遍历为升序
such as:
它支持：插入，查询，删除
在接下来的说明中，我们认为元素没有重复(有的话就记录出现次数cnt就好了)
插入：
当我们插入一个数时，和根节点比较大小，如果比根节点小就到左子树寻找，否则到右子树寻找，然后重复上述过程，直到找到插入的位置
例如：插入15
1.和13比较，15>13，向右子树寻找
2.和16比较，15<16，向左子树寻找
3.和14比较，15>14，向右子树寻找，右子树为空，则节点15插入到14的右边
查询
设数组(siz[x])表示以(x)为根节点的子树的大小(包括(x))，(ls)表示当前节点的左儿子，(rs)表示当前节点的右儿子
查询(x)的排名：比较(x)与根节点的大小，如果等于根节点，排名为(siz[ls]+1)；如果比根节点小，到左子树中查找，排名为左子树的排名；如果比根节点大，到右子树中查找，排名为右子树的排名+siz[ls]+1
查询排名为(x)的数：判断左子树大小和(x)的关系。如果(siz[ls]+1=x)，说明根节点就是要找的x；否则，如果siz[ls]>x，说明这个数在左子树中，到左子树寻找排名为x的数；如果siz[ls]<x，说明这个数在右子树中，到右子树寻找排名为x-siz[ls]-1的数
查询x的前驱：先查找到x的位置，然后找到左子树最靠右的儿子
查询x的后继：先查找到x的位置，然后找到右子树最靠左的儿子
删除
定位当前节点。如果左子树为空，就把右子树提上来，如果右子树为空，就把左子树提上来。否则，删去右子树最小的节点(这个节点的左子树一定为空)，把这个节点移动到当前节点的位置上来。
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, cnt, rot;
struct node
{
int ls, rs, val, siz, cnt;
}nod[N];
void Push_up(int x)
{
int ls = nod[x].ls, rs = nod[x].rs;
nod[x].siz = nod[ls].siz + nod[rs].siz + nod[x].cnt;
}
void Insert(int &rt, int x)
{
if(rt == 0)
{
rt = ++cnt;
nod[rt].siz = nod[rt].cnt = 1;
nod[rt].val = x;
return;
}
if(nod[rt].val == x)
{
nod[rt].cnt ++;
nod[rt].siz ++;
return;
}
if(nod[rt].val < x)
{
Insert(nod[rt].rs, x);
Push_up(rt);
return;
}
if(nod[rt].val > x)
{
Insert(nod[rt].ls, x);
Push_up(rt);
return;
}
}
int Findmin(int &rt)
{
if(nod[rt].ls)
{
int ret = Findmin(nod[rt].ls);
Push_up(rt);
return ret;
}
int ret = rt;
rt = nod[rt].rs;
return ret;
}
void Delete(int &rt, int x)
{
if(nod[rt].val == x)
{
if(nod[rt].cnt > 1)
{
nod[rt].cnt --;
nod[rt].siz --;
return;
}
else
{
if(nod[rt].ls == 0)
{
rt = nod[rt].rs;
return;
}
if(nod[rt].rs == 0)
{
rt = nod[rt].ls;
return;
}
else
{
int nd = Findmin(nod[rt].rs);
nod[rt].val = nod[nd].val;
nod[rt].cnt = nod[nd].cnt;
Push_up(rt);
return;
}
}
}
if(nod[rt].val < x)
{
Delete(nod[rt].rs, x);
Push_up(rt);
return;
}
if(nod[rt].val > x)
{
Delete(nod[rt].ls, x);
Push_up(rt);
return;
}
}
int Getk(int rt, int x)
{
if(nod[rt].val == x) return nod[nod[rt].ls].siz + 1;
else if(nod[rt].val < x) return nod[nod[rt].ls].siz + nod[rt].cnt + Getk(nod[rt].rs, x);
else if(nod[rt].val > x) return Getk(nod[rt].ls, x);
}
int Getkth(int rt, int x)
{
if(nod[nod[rt].ls].siz + 1 <= x && nod[nod[rt].ls].siz + nod[rt].cnt >= x) return nod[rt].val;
if(nod[nod[rt].ls].siz + 1 > x) return Getkth(nod[rt].ls, x);
if(nod[nod[rt].ls].siz + nod[rt].cnt < x) return Getkth(nod[rt].rs, x - (nod[nod[rt].ls].siz + nod[rt].cnt));
}
int Getpre(int rt, int x)
{
int p = rt, ans;
while(p)
{
if(x <= nod[p].val) p = nod[p].ls;
else ans = p, p = nod[p].rs;
}
return nod[ans].val;
}
int Getsuc(int rt, int x)//succeed
{
int p = rt, ans;
while(p)
{
if(x >= nod[p].val) p = nod[p].rs;
else ans = p, p = nod[p].ls;
}
return nod[ans].val;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
{
int opt, x;
scanf("%d%d", &opt, &x);
if(opt == 1) Insert(rot, x);
if(opt == 2) Delete(rot, x);
if(opt == 3) printf("%d
", Getk(rot, x));
if(opt == 4) printf("%d
", Getkth(rot, x));
if(opt == 5) printf("%d
", Getpre(rot, x));
if(opt == 6) printf("%d
", Getsuc(rot, x));
}
}
下一篇：朝鲜树