定义

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

实现

/**
 * 基于二叉树的符号表
 * @author zzk
 *
 */
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){
		return get(root, key);
	}

	//在以x为根节点的子树中查找并返回key所对应的值
	//如果找不到则返回null
	private Value get(Node x, Key key){
		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;
	}

	//最小值
	public Key min(){
		return min(root).key;
	}
	//不断的进入左树查找
	private Node min(Node x){
		if(x.left == null)
			return x;
		return min(x.left);
	}
	
	public Key max(){
		return max(root).key;
	}
	
	private Node max(Node x){
		if(x.right == null)
			return x;
		return max(x.right);
	}
	
	//小于等于key值的最大键（向下取整）
	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;
	}
	
	//返回给定键的排名（也就相当于在排序数组中查找某索引位置的值）
	public Key select(int k){
		return select(root, k).key;
	}
	
	private 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;
	}
	
	//返回以x为根节点的子树中小于x.key的键的数量（也就相当于在排序数组中查找某值在数组中的索引）
	public int 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);
		else
			return size(x.left);
	}
	
	//删除最小值
	public void deleteMin(){
		root = deleteMin(root);
	}
	
	private Node deleteMin(Node x){
		if( x.left == null ){
			return x.right;
		}
		x.left = deleteMin(x.left);
		x.N = size(x.left) + size(x.right) + 1;
		return x;
	}
	//删除某键
	public void delete(Key key){
		root = delete(root, key);
	}
	//删除key值，删除后用key的后继节点填补它的位置
	private Node delete(Node x, Key key){
		if(x==null)
			return null;
		int cmp = key.compareTo(x.key);
		if( cmp < 0 )
			x.left = delete(x.left, key);
		else if( cmp > 0 )
			x.right = delete(x.right, key);
		else{
			Node t = x;
			x = min(t.right);
			x.right  = deleteMin(t.right);
			x.left = t.left;
		}
		x.N = size(x.left) + size(x.right) + 1;
		return x;
	}
	//中序遍历（左-根-右）
	private void print(Node x){
		if( x == null )
			return;
		print(x.left);
		StdOut.println(x.key);
		print(x.right);
	}
	
	//二叉查找数的范围查找操作（查找出最小值到最大值之间的key集合）
	public Iterable<Key> keys(){
		return keys(min(), max());
	}
	
	public Iterable<Key> keys(Key lo, Key hi){
		Queue<Key> queue = new Queue<Key>();
		keys(root, queue, lo, hi);
		return queue;
	}
	
	private void keys(Node x, Queue<Key> queue, Key lo, Key hi){
		if( x==null )
			return;
		int cmplo = lo.compareTo(x.key);
		int cmphi = hi.compareTo(x.key);
		if(cmplo < 0)
			keys(x.left, queue, lo, hi);
		if(cmplo <= 0 && cmphi >=0 )
			queue.enqueue(x.key);
		if( cmphi > 0 )
			keys(x.right, queue, lo, hi);
	}
}

性能

在一棵二叉查找树中，所有的操作在最坏情况下所需的时间都和树的高度成正比，树的所有操作都沿着树的一条或两条路径行进，根据定义树的长度不可能大于树的高度。

简单的符号表实现成本

算法（数据结构）	最坏的情况下的运行时间的增长数量级（N次插入之后）	-	平均情况下的运行时间的增长数量级（N次随机插入之后）	-	是否支持有序相关的操作
-	查找	插入	查找命中	插入	-
顺序查询（无序链表）	N	N	N/2	N	否
二分查找（有序数组）	lgN	N	lgN	N/2	是
二叉树查找（二叉查找树）	N	N	1.39lgN	1.39lgN	是