一. 定义

• 二叉查找树，是指具有如下性质(称作”BST”性质)的二叉树：
• 给定一棵二叉树，每个结点带有一个数值，称作这个结点的“关键码”(或”关键字”、”键值”等，英文是”key”)
• BST性质：对于树中的任意结点，满足以下两条性质
• 它的关键码不小于左子树中任何结点的关键码
• 它的关键码不大于右子树中任何结点的关键码

二. 支持的操作

1. insert()：新增一个关键码为val的结点
2. get()：查找关键码为val的结点
3. getnext()：查找val的后继
4. getpre()：查找val的前驱
5. remove()：删除val的结点
6. getrank()：查找val的排名*
7. getkth()：查找第k大的val*

三. 二叉查找树的存储与初始化

1. 存储：

const int MAXLEN=100000;
struct NODE 
{
  int l,r;//左右孩子编号，0代表孩子不存在
  int val;//关键码
}tree[MAXLEN+2];
int tot;//当前结点总数
int root;//根结点下标

2. 初始化

• 为了避免越界，减少边界情况的特殊判断，一般在BST中额外插入一个关键码为正无穷和一个关键码为负无穷的节点。仅由这两个节点构成的BST就是一棵初始的空BST。

int newnode(int val)//新建一个节点，返回其编号
{
	tree[++tot].val=val;
	tree[tot].l=tree[tot].r=0;
	return tot;
}
void build()//建树
{
	newnode(-INF);
	newnode(INF);
	root=1;
	tree[1].r=2;
}