性质

二叉搜索树是一种具有以下性质的树：

1. 如果左子树不为空的话，左子树的所有节点的值都小于根节点的值
2. 如果右子树不为空的话，右子树的所有节点的值都大于根节点的值
3. 他的左右子树也都是二叉搜索树

下面就是一棵二叉搜索树

操作

二叉搜索树在一般的情况下都可以较为高效的完成一些操作，但在特殊情况下会退化成链。

二叉搜索树中的一个点代表的值可以是多个相同值的点的一个整体，也就是说，每一个值可能有重复的，但二叉搜索树里面不会有重复的，如果重复只需要在计数器上加一即可，这样也可以省空间，

下面以平衡树的模板题为例

查找

从根节点开始找，如果当前点的值就是要查找的值，那么就返回当前点的编号。
如果当前点的值大于要找的值，就去左子树去找。
如果当前点的值小于要找的值，就去右子树去找。

代码实现的话很简单，注意别打错下标就好，因为题目里面没有这个操作所以不放代码了。

插入

当你想要插入某一个值 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,半个小时