查找树(search tree)是一种数据结构，它支持多种动态集合操作，包括 SEARCH , MINIMUN , MAXIMUN , PREDECESSOR , SUCCESSOR , INSERT 以及 DELETE。它既可以用作字典，也可以用作优先队列。

在二叉查找树(binary search tree)上执行的基本操作的时间与树的高度成正比。对于一颗含有n个结点的完全二叉树，这些操作的最坏运行时间为O(lgn)。但是，如果树是含有n个结点的线性链，则这些操作的最坏情况为O(n)。在下文可以看到，一颗随机构造的二叉查找树的期望高度为O(lgn)，从而这种树上基本动态集合的平均操作时间为O(lgn)

在实际中，并不能总保证二叉查找树是随机构成的，但对于有些二叉查找树的变形来说，各基本操作的最坏情况却能保证是很好的。比如红黑树和B树。

二叉查找树

如下图所示，一颗二叉查找树是按二叉树结构来组织的。这样的树可以用链表结构表示，其中每一个结点都是一个对象。结点中除了 key 域与卫星数据外，还包含域 left , right 和 p，它们分别指向结点的左儿子、右儿子、和父结点。如果某个儿子结点或父结点不存在，则相应域中的值即为NIL。根节点是树中唯一的父结点域为NIl的结点

二叉查找树，对任何结点x，其左子树的关键字最大不超过key[x]，其右子树中的关键字最小不小于key[x]。不同的二叉查找树可以表示同一组值。在有关查找树的操作中，大部分操作的最坏情况运行时间与数的高度是成正比的。

二叉查找树中的关键字的存储方式总是满足以下的二叉查找树性质：

1
2
3
4
5

x为二叉查找树中的一个结点
if (y是x的左子树中的一个结点) 
	key[y] <= key[x];
else if (y是x的右子树中的一个结点)
	key[y] >= key[x];

在上图中，根结点的关键字为8，其左子树中的关键字为3、1、6、4和7都不大于8；其右子树中的关键字为10，右子树中的10、14、13都不小于8。这个性质对树中的每个结点都成立。

二叉查找树性质允许我们通过一个简单的递归算法来按序输出二叉查找树中的所有关键字。这种算法称为中序遍历算法。这样命名的原因是输出的子树的关键字位于其左子树的关键字和右子树的关键字中间。

调用下面的过程inOrderTree(T.root)，就可以输出二叉搜索树的所有关键字

1
2
3
4
5
6

inOrderTree(x) {
	if x != nil
		inOrderTree(x.left);
		print(x.key);
		inOrderTree(x.right);
}

根据二叉搜索树性质，可以用递归证明上诉算法的正确性

遍历一颗含有n个结点的二叉搜素树需要耗费O(n)的时间，因为初次调用之后，对于树中的每个结点这个过程恰好要调用两次，一次是它的左孩子，另一次是它的右孩子。

查询二叉搜索树

我们经常需要查找一个存储在二叉搜索树中的关键字，除了 SEARCH 操作外，还有 MINIMUN , MAXIMUN , PREDECESSOR , SUCCESSOR 的查询操作

• 查找

我们使用下面的过程在一棵二叉搜索树中查找有一个具有给定关键字的结点，输入一个指向树根的指针和一个关键字k，如果这个结点存在，TREE-SEARCH返回一个指向关键字为k的结点的指针，否则返回nil

1
2
3
4
5
6
7

TREE-SEARCH(x,k) 
	if x == nil or k == x.key
		return x
	if k<x.key
		return TREE-SEARCH(x.left,k)
	else
		return TREE-SEARCH(x.right,k)

这个过程从树根开始，并沿着这棵树中的一条简单路径向下进行。对于每个遇到的结点x，比较k与x.key。如果两个关键字相等，查找就终止。如果k小于x.key，查找在x的左子树中继续，因为二叉搜索树的性质蕴含了k不可能被存储在右子树中。对称的。如果k大于x.key，查找在右子树中继续。从树根开始递归期间遇到的结点就形成了一条向下的简单路径，所以TREE-SEARCH的运行时间为O(h)，其中h是这棵树的高度。

我们可以采用while循环来展开递归，用一种迭代方式重写这个过程。对于大多数计算机，迭代版本的效率要高得多。

1
2
3
4
5
6
7

ITERATIVE-TREE-SEARCH(x,k)
	while x != nil and k != x.key
		if k < x.key
			x = x.left
		else
			x = x.right
	return x

• 最大关键字元素和最小关键字元素

通过从树根开始沿着left孩子指针直到遇到一个nil，我们总能在一棵二叉搜索树中找到一个元素。下面的过程返回了一个指向在以给定结点x为根的子树中的最小元素的指针。这里假设都为nil

1
2
3
4

TREE-MINIMUN(x)
	while x.left != nil
		x = x.left
	return x

二叉搜索树性质保证了TREE-MINIMUN是正确的。如果结点x没有左子树，那么由于x右子树中的每个关键字结点都至少大于或等于x.key，则以x为根的子树中的每个关键字都不大于x.key，则以x为根的子树中的最小关键字一定是以x.left为根的子树中

TREE-MAXIMUN的伪代码是对称的，如下：

1
2
3
4

TREE-MAXIMUN(x)
	while x.right != nil
		x = x.right
	return x

这两个过程在一棵高度为h的树上均能在O(h)时间内执行完，因为与TREE-SEARCH一样，他们遇到的结点均形成了一条从树根向下的简单路径。

• 前驱和后继

给定一棵二叉搜索树中的一个结点，有时候需要按中序遍历的次序查找他的后继。如果所有的关键字互不相同，则一个结点x的后继是大于x.key的最小关键字的结点。一颗二叉搜索树的结构允许我们通过没有任何关键字的比较来确定一个结点的后继。如果后继存在，下面的过程将返回一棵二叉搜索树的结点x的后继；如果x是这棵书中的最大关键字，则返回nil

1
2
3
4
5
6
7
8

TREE-SUCCESSOR(x)
	if x.right != nil
		return TREE-MINIMUN(x.right)
	y = x.p
	while y != nil and x == y.right
		x = y
		y = y.p
	return y

把TREE-SUCCESSOR的伪代码分为两种情况。如果结点x的右子树非空，那么x的后继恰是x右子树中额最左结点。通过第三行的TREE-MINIMUN(x.right)调用可以找到。

另一方面，如果结点x的右子树为空并且有一个后继，那么y就是x的底层祖先，并且y的左孩子也是x的一个祖先结点。

在一棵高度为h的树上，TREE-SUCCESSOR的运行时间为O(h)，因为该过程或者遵从一条简单路径沿树向上或者遵从简单路径沿树详细。过程TREE-SUCCESSOR(x)和TREE-PREDECESSOR(x)是对称的，其运行时间也为O(h)

即使关键字万全不相同，我们仍然定义任何结点x的后继结点x的后继和前驱分别调用TREE-SUCCESSOR(x)和TREE-PREDECESSOR(x)所返回的结点。

总之我们证明了下面这条定理：

在一棵高度为h的二叉搜索树上，动态集合上的操作SEARCH , MINIMUN , MAXIMUN , PREDECESSOR , SUCCESSOR可以在O(h)时间内完成

插入和删除

插入和删除操作会引起有二叉搜索树表示的动态集合的变化，一定要修改数据结构来反映这个变化，但修改要保持二叉搜索树性质的成立。正如下面将所看到的，插入一个新结点带来的树的修改要相对简单些，而删除的处理有些复杂

• 插入

要将一个新值v插入到一颗二叉搜索树T中，需要调用过程TREE-INSERT。该过程以结点z作为输入，其中z.key = v, z.left = nil, z.right = nil。这个过程要修改T和z的某些属性，来把z插入到树中的相应位置上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

TREE-INSERT(T,z)
	y = nil
	x = T.root
	while x != nil
		y = x
		if z.key < x.key
			x = x.left
		else
			x = x. right
	z.p = y
	if y == nil
		T.root = z 
	elseif z.ket < y.key
		y.left = z
	else
		y.right = z

TREE-INSERT从树根开始，指针x记录了一条向下的简单路径，并查找要替换的输入项z的nil。该过程保持遍历指针y作为x的双亲。初始化后，第4~8行的while循环使得这两个指针沿树向下移动，向左或向右移动取决于z.key和x.key的比较，直到x变为nil。这个nil占据的位置就是输入项z要放置的地方。我们需要遍历指针y，这是因为找到nil是需要知道z属于哪个结点。第9~14行设置相应的指针，使得z插入其中。

与其他搜索树上的原始操作一样，过程TREE-INSERT在一棵高度为h的树上运行时间为O(h)

• 删除

从一棵二叉搜索树T中删除一个结点z的整个策略分为三种基本情况，但只有一种情况比较棘手

• 如果z没有孩子结点，那么只是简单的将它删除，并修改他的父结点，用nil作为孩子来替换z
• 如果z只有一个孩子，那么将这个孩子提升到树中z的位置上，并修改z的父结点，用z的孩子来替换z
• 如果z有两个孩子，那么找到z的后继y（一定在z的右子树中），并让y占据树中z的位置。z的原来右孩子分成为y的新的右子树，并且z的左子树成为y的新的左子树。这种情况稍显麻烦，因为还有y是否为z的右孩子相关

从一棵二叉搜索树T中删除一个钦定的结点z，这个过程取指向T和x的指针作为输入参数。

为了在二叉搜索树内移动子树，定义一个子过程TRANSPLANT，它是用一颗子树替换另一颗子树并成为其双亲的孩子结点。当TRANSPLANT用一棵以v为根的子树来替换一颗以u为根的子树时，结点u的双亲就变为结点v的双亲，并且最后v成为u的双亲的相应孩子

1
2
3
4
5
6
7
8
9

TRANSPLANT(T, u, v)
	if u.p == nil
		T.root = v
	elseif u = u.p.left
		u.p.left = v
	else
		u.p.right = v
	if v != nil
		v.p = u.p

第2~3行处理u是T的树根的情况。否则，u是其双亲的左孩子或者右孩子。如果u是一个左孩子，第4~5行负责的是u.p.left的更新；如果u是一个右孩子，第6行更新u.p.right。我们允许v = nil，如果v为非nil时，第7~8行更新u.p。注意到，TRANSPLANT并没有处理v.left与n.right的更新，这些更新都有TRANSPLANT的调用者来负责。

利用现成的TRANSPLANT过程，下面是从二叉搜索树T中删除结点z的删除过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14

TREE-DELETE(T,z)
	if z.left == nil
		TRANSPLANT(T,z,z.right)
	elseif z.right == nil
		TRANSPLANT(T,z,z.left)
	else 
		y = TREE-MINIMUM(z.right)
		if y.p != z
			TRANSPLANT(T,y,y.right)
			y.right = z.right
			y.right.p = y
		TRANSPLANT(T,z,y)
		y.left = z.left
		y.left.p = y

TREE-DELETE的处理过程：第2~3行处理z没有左孩子的情况；第4~5行处理z有一个左孩子但是没有右孩子的情况；第6~13行处理剩下的情况，也就是z有两个孩子的情形。第6行查找结点y，它是z的后继，因为z的右子树非空，这样后继一定是这棵子树具有最小关键字的结点，因此就调用TREE-MINIMUM(z.right)。如前所诉，y没有左孩子。将y移除其原来的位置进行拼接，并替换树中的z。如果y是z的右孩子，那么第11~13行用y替换z并成为z的双亲的一个孩子，用z的左孩子替换y的左孩子。如果y不是z的左孩子，第8~10行用y的右孩子替换y并成为y的双亲的一个孩子，然后将z的右孩子替换y的右孩子。最后第11~13行用y替换z并成为z的双亲的一个孩子，再用z的左孩子替换y的左孩子。

除了第6行调用TREE-MINIMUM外，TREE-DELETE的每一行包括调用TRANSPLANT，都只花费常数时间。因此，在一棵高度为h的树上，TREE-DELETE的运行时间为O(h)

总之，我们证明了下面的这个定理

在一棵高度为h的二叉搜索树上，实现动态集合操作INSERT和DELETE的运行时间均为O(h)

随机构建二叉搜索树

我们已经证明了二叉搜索树上的每个基本操作都能在O(h)时间内完成，其中h为这两棵树的高度。然而，随着元素的插入和删除，二叉搜索树的高度是变化的。

而且，当一颗二叉搜索树同时由插入和删除操作生成时，我们队这棵树的平均高度了解的甚少。当树是由插入造作单独生成时，分析就会变得容易的很多。因此，我们定义n个关键字的一个随机构建二叉搜索树(randomly build binary search tree)为按照随机次序插入这些关键字到一颗初始的空树中而生成的树，这里输入关键字n！个排列中的每个都是等可能的出现。

一颗含有n个不同关键字的随机构建二叉搜索树的期望高度为O(lgn)