性质
二叉搜索树是一种具有以下性质的树:
- 如果左子树不为空的话,左子树的所有节点的值都小于根节点的值
- 如果右子树不为空的话,右子树的所有节点的值都大于根节点的值
- 他的左右子树也都是二叉搜索树
下面就是一棵二叉搜索树
操作
二叉搜索树在一般的情况下都可以较为高效的完成一些操作,但在特殊情况下会退化成链。
二叉搜索树中的一个点代表的值可以是多个相同值的点的一个整体,也就是说,每一个值可能有重复的,但二叉搜索树里面不会有重复的,如果重复只需要在计数器上加一即可,这样也可以省空间,
下面以平衡树的模板题为例
查找
从根节点开始找,如果当前点的值就是要查找的值,那么就返回当前点的编号。
如果当前点的值大于要找的值,就去左子树去找。
如果当前点的值小于要找的值,就去右子树去找。
代码实现的话很简单,注意别打错下标就好,因为题目里面没有这个操作所以不放代码了。
插入
当你想要插入某一个值 k 的时候,操作和查找是差不多的,因为你要插入的话要先找到 k 插入的位置,当有点的值和 k 相等时,可以直接当前值的点数加一,反之开一个新点,然后就就是根据 k 和当前点的大小来判断是往哪里插入。
代码实现
void add(int &x,int k)
{
if(x==0)
{
x=++cnt;
e[x].siz=e[x].cnt=1;
e[x].val=k;
return ;
}
if(e[x].val==k)
{
e[x].cnt++;
e[x].siz++;
return ;
}
if(e[x].val<k)
{
add(rs1,k);
p_p(x);
return ;
}
if(e[x].val>k)
{
add(ls1,k);
p_p(x);
return ;
}
return ;
}
删除
我们可以先找到当前节点。如果左子树为空,就把右子树提上来,如果右子树为空,就把左子树提上来。否则,删去右子树最小的节点(这个节点的左子树一定为空),把这个节点移动到当前节点的位置上来。
代码实现
int fid(int &x)
{
if(e[x].ls)
{
int res=fid(ls1);
p_p(x);
return res;
}
int res=x;
x=e[x].rs;
return res;
}
void dele(int &x,int k)
{
if(e[x].val==k)
{
if(e[x].cnt>1)
{
e[x].cnt--;
e[x].siz--;
return ;
}
else
{
if(e[x].ls==0)
{
x=rs1;
return ;
}
if(e[x].rs==0)
{
x=ls1;
return ;
}
else
{
int xx=fid(rs1);
e[x].val=e[xx].val;
e[x].cnt=e[xx].cnt;
p_p(x);
return ;
}
}
}
if(e[x].val<k)
{
dele(rs1,k);
p_p(x);
return ;
}
if(e[x].val>k)
{
dele(ls1,k);
p_p(x);
return ;
}
return ;
}
查询排名
首先如果要是 k 刚好是在当前点的排名上,也就是 k==e[x].val的话,我们可以直接
我们还是和之前一样,如果当前要查询的 k 的排名是大于当前点的排名,也就是 k>e[e[x].ls].siz+1 的话
插曲
x=++cnt打成x==++cnt调了1个多小时。。。
查询排名和值的时候把if里的k>=e[p].val打成了k>=e[x].val,半个小时