二叉查找树 #

• 使用每个结点含有两个链接（链表中每个结点只含有一个链接）的二叉查找树来高效地实现符号表

• 该数据结构由结点组成，结点包含的链接可以为空(null)或者指向其他结点

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

• 

基本实现 #

• 数据表示

  • 每个结点都含有一个键、一个值、一条左链接、一条右链接和一个结点计数器 左链接指向一棵由小于该结点的所有键组成的二叉查找树，右链接指向一棵由大于该节点的所有键组成的二叉查找树，变量N给出了以该结点为根的子树的结点总数
  • 对于任意节点总是成立 size(x)=size(x.left)+size(x.right)+1

• 多棵二叉查找树表示同一组有序的键来实现构建和使用二叉查找树的高校算法

• 查找

  • 在符号表中查找一个键可能得到两种结果：如果含有该键的结点存在表中，我们的查找就命中了，然后返回值；否则查找未命中（返回null)
  • 递归：如果树是空的，则查找未命中；如果被查找的键和根节点的键相等，查找命中，否则在适当的子树中查找：如果被查找的键较小就选择左子树，否则选择右子树
  • 下面的get()方法，第一个参数是一个结点（子树根节点），第二个参数是被查找的键，代码会保证只有该结点所表示的子树才会含有和被查找的键相等的结点
  • 从根结点开始，在每个结点中查找的进程都会递归地在它的一个子结点上展开，因此一次查找也就定义了树的一条路径。对于命中的查找，路径在含有被查找的键的结点处结束。对于未命中的查找，路径的终点是一个空链接

• 基于二叉查找树的符号表

  public class BST<Key extends Comparable<Key>, Value>
  {
  	private Node root;
  	// 二叉查找树的根结点
  	private class Node
  	{
  		private Key key;
  		// 键
  		private Value val;
  		// 值
  		private Node left, right;
  		// 指向子树的链接
  		private int N;
  		// 以该结点为根的子树中的结点总数
  		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)
  	// 请见算法3.3（续1）
  	public void put(Key key, Value val)
  	// 请见算法3.3（续1）
  	// max()、min()、floor()、ceiling()方法请见算法3.3（续2）
  	// select()、rank()方法请见算法3.3（续3）
  	// delete()、deleteMin()、deleteMax()方法请见算法3.3（续4）
  	// keys()方法请见算法3.3（续5）
  }
  

  • 每个Node 对象都是一棵含有N 个结点的子树的根结点，它的左链接指向一棵由小于该结点的所有键组成的二叉查找树，右链接指向一棵由大于该结点的所有键组成的二叉查找 树。root 变量指向二叉查找树的根结点Node 对象（这棵树包含了符号表中的所有键值对）

• 二叉查找树的查找和排序方法的实现

  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;
  }
  

• 插入 put()方法的实现逻辑和递归查找很相似：如果树是空的，就返回一个含有该键值对的新节点；如果被查找的键小于根节点的键，我们就会继续在左子树中插入该键，否则在右子树中插入该键

• 递归

  • 可以将递归调用前的代码想象成沿着树向下走：它会将给定的键和每个结点的键相比较并根据结果向左或者向右移动到下一个结点。然后可以将递归调用后的代码想象成沿着树向上爬
  • 在一棵简单的二叉查找树中，唯一的新链接就是在最底层指向新结点的链接，重置更上层的链接可以通过比较语句来避免。同样，我们只需要将路径上每个结点中的计数器的值加1，但我们使用了更加通用的代码，使之等于结点的所有子结点的计数器之和加1

• 使用二叉查找树的标准索引用例的轨迹

分析 #

在由N 个随机键构造的二叉查找树中，查找命中平均所需的比较次数为∼ 2lnN

在由N 个随机键构造的二叉查找树中插入操作和查找未命中平均所需的比较次数为∼ 2lnN（约1.39lgN）

有序性相关的方法与删除操作 #

最大键和最小键 #

如果根结点的左链接为空，那么一棵二叉查找树中最小的键就是根结点；如果左链接非空，那么 树中的最小键就是左子树中的最小键

向上取整和向下取整 #

如果给定的键key 小于二叉查找树的根结点的键，那么小于等于key 的最大键floor(key) 一定 在根结点的左子树中；如果给定的键key 大于二叉查找树的根结点，那么只有当根结点右子树中存在小于等于key 的结点时，小于等于key 的最大键才会出现在右子树中，否则根结点就是小于等于key的最大键

选择操作 #

public Key min()
{
	return min(root).key;
}
private Node min(Node x)
{
	if (x.left == null) return x;
	return min(x.left);
}
public Key floor(Key key)
{
	Node x = floor(root, key);
	if (x == null) return null;
	return x.key;
}
private Node floor(Node x, Key key)
{
	if (x == null) return null;
	int cmp = key.compareTo(x.key);
	if (cmp == 0) return x;
	if (cmp < 0) return floor(x.left, key);
	Node t = floor(x.right, key);
	if (t != null) return t; else return x;
}

排名 #

删除最大键和删除最小键 #

删除操作 #

范围查找 #

性能分析 #