二叉搜索树 Binary Search Tree

# 二叉搜索树 Binary Search Tree

二叉搜索树（二叉排序树或二叉查找树）：

若二叉搜索树为空，则查找不成功；否则：

插入操作在查找不成功时才进行；

若二叉搜索树为空树，则新插入的节点为根节点；否则，新插入的节点必为一个叶子节点，其插入位置由查找过程得到。

删除一个节点后，仍是二叉排序树。可分三种情况讨论：

	struct node {
	int val;
	node lch, rch;
	};

	bool find(node *p, int x) {
	if (p == NULL) return false;
	else if (x == p->val) return true;
	else if (x < p->val) return find(p->lch, x);
	else return find(p->rch, x);
	}

	node insert(node p, int x) {
	if (p == NULL) {
	node *q = new node;
	q->val = x;
	q->lch = q->rch = NULL;
	return q;
	}
	else {
	if (x < p->val) p->lch = insert(p->lch, x);
	else p->rch = insert(p->rch, x);
	return p;
	}
	}

	node remove(node p, int x) {
	if (p == NULL) return NULL;
	else if (x < p->val) p->lch = remove(p->lch, x);
	else if (x > p->val) p->rch = remove(p->rch, x);
	else if (p->lch == NULL) { // 第一种情况
	node *q = p->rch;
	delete p;
	return q;
	}
	else if (p->lch->rch == NULL) {// 第二种情况
	node *q = p->lch;
	q->rch = p->rch;
	delete p;
	return q;
	}
	else { // 第三种情况
	node *q;
	for (q = p->lch; q->rch->rch != NULL; q = q->rch);
	node *r = q->rch;
	q->rch = r->lch;
	r->lch = p->lch;
	r->rch = p->rch;
	delete p;
	return r;
	}
	return p;
	}

给定含 n 个关键字的集合，假设所有关键字不相同，对应有 n! 个关键字序列，每个关键字序列构造一棵二叉排序树，所有这些二叉排序树中查找每个关键字的平均时间为 $O(log2n)$ 。
给定含 n 个关键字的关键字序列构造一棵二叉排序树。其中查找性能最好的是高度最小的二叉排序树，最好查找性能为 $O(log2n)$ 。查找性能最坏的是高度为 n 的二叉排序树（单支树），最坏查找性能为 $O(n)$ 。平均情况由具体的关键字序列来确定。所以常说二叉排序树的时间复杂度在 $O(log2n)$ 和 $O(n)$ 之间，就是指这种分析方法。
查找序列（ $k_1，k_2，…，k_n$ ）的查找树画法是，每一层只有一个结点，首先 $k_1$ 为根结点，再依次画出其他结点，若 $k_{i+1}<k_i$ ，则 $k_{i+1}$ 的结点作为 $k_i$ 结点的左孩子，否则作为右孩子。