【深入解析算法】二叉查找树,查找

7 二叉查找树

我们将学习一种能够将链表插入的灵活性和有序数组查找的高效性结合起来的符号表实现。具体来说，就是使用每个结点含有两个链接(链表中每个结点只含有一个链接)的二叉查找树来高效地实现符号表，这也是计算机科学中最重要的算法之一。

首先，我们需要定义一些术语。我们所使用的数据结构由结点组成，结点包含的链接可以指向空( null )或者其他结点。在二又树中，每个结点只能有一个父结点指向自己(只有一个例外，也就是根结点，它没有父结点)，而且每个结点都只有左右两个链接，分别指向自己的左子结点和右子结点。尽管链接指向的是结点，但我们可以将每个链接看做指向了另-棵二叉树，而这棵树的根结点就是被指向的结点。因此我们可以将二叉树定义为一个空链接， 或者是一一个有左右两个链接的结点，每个链接都指向.棵(独立的)子二又树。在二叉查找树中，每个结点还包含了一个键和一 个值， 键之间也有顺序之分以支持高效的查找。

定义：一棵二又查找树(BST)是一棵二叉树，其中每个结点都含有一个Comparable的键(以及相关联的值)且每个结点的键都大于其左子树中的任意结点的键而小于右子树的任意结点的键。

我们在画出二叉查找树时会将键写在结点上。我们使用“A是E的左子结点”的说法用键指代结点。我们用连接结点的线表示链接，并将键对应的值写在结点旁边(若值不确定则省略)。除了空结点只表示为向下的一条线段以外，每个结点的链接都指向它下方的结点。

7.1 基本实现

下面的算法定义了二叉查找树(BST)的数据结构，我们会在本节中用它实现有序符号表的API。 首先我们要研究一下这个经典的数据类型，以及与它的特点紧密相关的get() (查找)和put()(插入)方法的实现。

7.1.1 数据表示

和链表一样，我们嵌套定义了一个私有类来表示二叉查找树上的一个结点。 每个结点都含有一个键、 一个值、一条左链接 、一条右链接和一个结点计数器(有需要时我们会在图中将结点计数器的值写在结点上方)。左链接指向-棵由小于该结点的所有键组成的二叉查找树，右链接指向一棵由大于该结点的所有键组成的二叉查找树。变量N给出了以该结点为根的子树的结点总数。你将会看到，它简化了许多有序符号表的操作的实现。下面的算法中实现的私有方法size()会将空链接的值当作0，这样我们就能保证以下公式对于二叉树中的任意结点x总是成立。

size(x) = size(x.left) + size(x.right) + 1
1

一棵二叉查找树代表了一组键(及其相应的值)的集合，而同一个集合可以用多棵不同的二叉查找树表示。如果我们将-棵二叉查找树的所有键投影到一条直线上， 保证个结点的左子树中的键出现在它的左边，右子树中的键出现在它的右边，那么我们一定可以得到一条有序的键列。我们会利用二叉查找树的这种天生的灵活性，用多棵二叉查找树表示同一组有序的键来实现构建和使用二叉查找树的高效算法。

7.1.2 查找

一般来说，在符号表中查找一个键可能得到两种结果。如果含有该键的结点存在于表中,我们的查找就命中了,然后返回相应的值。否则查找未命中(并返回null)。根据数据表示的递归结构我们马上就能得到，在二叉查找树中查找一个键的递归算法: 如果树是空的，则查找未命中:如果被查找的键和根结点的键相等，查找命中，否则我们就(递归地)在适当的子树中继续查找。如果被查找的键，两棵能够表较小就选择左子树，较大则选择右子树。下面的算法中递归的get()方法完全实现了这段算法。它的第一个参数是一 一个结点(子树的根结点)，第二个参数是被查找的键。代码会保证只有该结点所表示的子树才会含有和被查找的键相等的结点。和二分查找中每次迭代之后查找的区间就会减半-一样， 在二叉查找树中，随着我们不断向下查找，当前结点所表示的子树的大小也在减小(理想情况下是减半，但至少会有一个结点)。当找到一个含有被查找的键的结点(命中)或者当前子树变为空(未命中)时这个过程才会结束。从根结点开始，在每个结点中查找的进程都会递归地在它的一个子结点上展开，因此一-次查找也就定义了树的一条路径。对于命中的查找，路径在含有被查找的键的结点处结束。对于未命中的查找，路径的终点是一一个空链接。

算法 基于二叉查找树的符号表

public class BST<Key extends Comparable<Key>, Value>{

	private Node root;   //二又查找树的根结点

	public class Node{

		private Key key;  //键

		private Value val;   //值

		private Node left, right;    //指向子树的链接

	}

	public Node(Key key, Value val, int N){

		this.key = key; 

		this.val = val; 

		this.N = N;

	}

	public int size(){ 

		return size(root);

	}

	private int size(Node x){

		if (x = null)   return 0;

		else    return x.N;

	}

	public. Value get(Key key){

		//请见算法(续1)

	}

	public void put(Key key, Value val){

		//请见算法(续1)

		// max()、min()、floor()、 ciling()方法请见算法(续2)/ select()、rank()方法请见算法(续3)

		// delete()、deleteMin()、 deleteMax()方法请见算法(续4)/ keys()方法请见算法(续5)

	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

这段代码用二叉查找树实现了有序符号表的API,树由Node对象组成，每个对象都含有一对键值、两条链接和一个结点计数器N。每个Node对象都是一棵含有 N个结点的子树的根结点，它的左链接指向一棵由小于该结点的所有键组成的二叉查找树，右链接指向一棵由大于该结点的所有键组成的二叉查找树。root变量指向二叉查找树的根结点Node对象(这棵树包含了符号表中的所有键值对)。

算法 (续1)二叉查找树的查找和排序方法的实现

public Value get(Key key){

	return get(root,key);

}

private Value get(Node x, Key key){ 

	//在以x为根结点的子树中查找并返回key所对应的值;

	//如果找不到则返回null

	if (x == null) return null;

	int cmp = key. compareTo(x. key);

	if(cmp < 0) return get(x. left, key);

	else if (cmp > 0) return get(x.right, key);

	else return x.val;

}

public void put(Key key, Value val){ 

	//查找key, 找到则更断它的值，否则为它创建一个新的结点

	root=put(root,key,val);

}

private Node put(Node x，Key key, value val){

	//如果key存在于以x为根结点的子树中则更新它的值;

	//否则将以key和val为键值对的新结点插入到该子树中

	if (x == null)    return new Node(key, val, 1);

	int cmp = key.compareTo(x. key);

	if (cmp <0)   x.left = put(x.left， key, val);

	else if (cmp > 0)   x.right = put(x.right, key, val);

	else  x.val = val;

	x.N= size(x.left) + size(x.right) + 1;

	return x;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

这段代码实现了有序符号表API中的put()和get()方法，它们的递归实现也是本章稍后将会讨论的其他几种实现的模板。每个方法的实现既可以看做是实用的代码，也可以看做是之前讨论的递推猜想的证明。

7.1.1.3 插入

算法3.3(续1)中的查找代码几乎和二分查找的一样插入L简单，这种简洁性是二叉查找树的重要特性之一。而二叉查找树的另一个更重要的特性就是插人的实现难度和查找差不多。当查找一个不存在于树中的结点并结束于一条空链接时，我们需要做的就是将链接指向个含有被查找的键的新结点。算法 (续1)中递归的put()方法的查找L的操作终实现逻辑和递归查找很相似:如果树是空的，就返回一个含有该键值对的新结点;如果被查找的键小于根结点的键，我们会继续在左子树中插入该键，否则在右子树中插入该键。

7.1.1.4 递归

这些递归实现值得我们花点儿时间去理解其中的运行细节。可以将递归调用前的代码想象成沿着树向下走:它会将给定的键和每个结点的键相比较并根据结果向左或者向右移动到下一个结点。然后可以将递归调用后的代码想象成沿着树向上爬。对于get()方法，这对应着-系列的返回指令(return)，但是对于put()方法，这意味着重置搜索路径上每个父结点指向子结点的链接，并增加路径上每个结点中的计数器的值。在一棵简单的二叉查找树中，唯一的新链接就是在最底层指向新结点的链接，重置更上层的链接可以通过比较语句来避免。同样，我们只需要将路径上每个结点中的计数器的值加1,但我们使用了更加通用的代码，使之等于结点的所有子结点的计数器之和加1。基本的二叉查找树的实现常常是非递归的——我们在实现中使用了递归，一来是为了便于读者理解代码的工作方式，二来也是为学习更加复杂的算法做准备。