3.2 Binary Search Trees

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

每个结点都包括一个键、一个值、一条左链接、一条右链接和一个结点计数器。

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

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);
	}
	public int size(Node x){
		if(x == NULL) return 0;
		else return x.N;
	}
	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.compateTo(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 void put(Node root,Key key,Value val){
		//如果key存在于以key为根结点的子树中则更新它的值
		//否则将以key和val为键值对的新结点插入到该子树中
		if(x == null) return new Node(key,val,1);
		int cmp = key.compateTo(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;
	}
}

floor(Key key)：小于等于key的最大键

如果给定的键key小于二叉查找树的根结点键，那么小于等于key的最大键一定在左子树中，如果key大于二叉树的根结点键，可能在右子树中，也可能是根结点键

二叉查找树中max()、min()、floor()方法的实现

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(root,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;
}

二叉查找树中rank()和select()方法的实现
select（排名为k的键）：如果左子树中的结点数t大于k，我们就继续递归地在左子树中查找排名为k的键；如果t等于k，我们就返回根结点中的键。如果t小于k，我们就（递归地）在右子树中查找排名为（k-t-1）的键。

public Key select(int k)
{
	return select(root,k).key;
}
public Node select(Node x,int k)
{
	//返回排名为k的结点
	if(x == null) return null;
	int t = size(x.left);
	if    (t > k) return select(x.left,k);
	else if(t < k)return select(x.right,k-t-1);
	else return x;
}

public Key rank(Key key){
	return rank(key, root);
}
private int rank(Key key,Node x)
{
        //返回以x为根节点的子树中小于x.key的键的数量
	if (x == null) return 0;
	int cmp = key.compareTo(x.key);
	if     (cmp < 0) return rank(key,x.left);//返回该键在左子树中的排名
	else if(cmp > 0) return 1 + size(x.left) + rank(key,x.right);
        //返回t + 1（根结点）加上它在右子树中的排名
	else             return size(x.left)
}

具体实现二叉查找树

命题：在由N个随机键构造的二叉查找树中插入操作和查找未命中中平均所需的比较次数为~2lnN(约1.39lgN)
命题：在一颗二叉查找树中，所有操作在最坏情况下所需的时间和树的高度成正比

Exercise

1. Write a test client TestBST.java for use in testing the implementations of min(),max(),floor(),select(),rank(),deleteMin(),deleteMax(),and keys() that are given in the text
2. Give nonrecursive implementations of get(),put(),and keys() for BST.
   solution:NonrecuisiveBST.java
   Creative Problems

---

1. Perfect balance. Write a program PerfectBalance.java that inserts a set of keys into an initially empty BST such that the tree produced is equivalent to binary search, in the sense that the sequence of compares done in the search for any key in the BST is the same as the sequence of compares used by binary search for the same set of keys.
   Hint: Put the median at the root and recursively build the left and right subtree.
2. Certification. Write a method isBST() in BST.java that takes a Node as argument and returns true if the argument node is the root of a binary search tree, false otherwise.
3. Subtree count check. Write a recursive method isSizeConsistent() in BST.java that takes a Node as argument and returns true if the subtree count field N is consistent in the data structure rooted at that node, false otherwise.
4. Select/rank check. Write a method isRankConsistent() in BST.java that checks, for all i from 0 to size() - 1, whether i is equal to rank(select(i)) and, for all keys in the BST, whether key is equal to select(rank(key)).
   Web Exercise

---