我们来研究一种符号表的实现————它结合了使用链表带来的插入元素的灵活性和使用顺序数组带来的查找元素的高效性，称为二叉搜索树。
————————————————————————
一个二叉搜索树是一个二叉树，每个节点都有一个可以比较的键，并满足以下约束条件：每个节点的键都比它左子树中所有节点的键大，都比它右子树中所有节点的键小
————————————————————————
可以把每个链接看成指向一个子二叉搜索树而不是指向一个节点，用根节点来代表一个二叉搜索树
基本实现（Basic Implementation）
表示（Representation）
每个节点包含五个部分：一个键，一个值，一个左链接，一个右链接，和一个子树节点计数。一个BST（二叉搜索树）表示若干个键（及其相应的值）的集合，不同的BST可能表示同一个这样的集合，用根节点来指示一个BST。
class Node
{
private Key key;
private Value val;
private Node left, right;
private int N; // # nodes in subtree rooted here
public Node(Key key, Value val, int N)
{ this.key = key; this.val = val; this.N = N; }
}
查找（Search）
我们可以递归地来进行查找，当树为空时：查找失败（返回null）；当查找的键比当前节点的键大时，递归查找右子树；当查找的键比当前节点的键小时，递归查找左子树；当查找的键等于当前节点的键时，返回当前节点的值。
最终，搜索路径终止于一个有键的节点（查找成功）或一个空节点（查找失败）。
public Value get(Key key)
{ return get(root, key); }
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;
}
插入（Insert）
插入和查找的实现十分相似，相当于在查找失败后，用一个新的节点去代替空节点就行。
public void put(Key key, Value val)
{ root = put(root, key, val); }
private Node put(Node x, Key key, Value 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; // size方法只是简单地返回给定节点N值
return x;
}
递归过程
递归的过程可以分为两部分来看：
- 在递归调用之前，好比从根节点一直沿着树向下
- 在递归调用之后，好比从底层节点一直沿着树向上
所以我们只需要在递归调用后从下往上更新子树节点计数就行（如插入操作的代码所示）
两层包装
注意在插入和查找的操作中都利用重载对方法进行了包装，真正进行递归的方法对用户是不可见的（private）。其中，public方法返回需要的值（或不返回），而private方法一律返回Node对象。
性能分析（Analysis）
BST的运行时间与树的形状有很大关系，也就是说，与元素插入的顺序有关。在最好的情况下，BST是完美平衡的一棵，每个null链接与根节点直接都是 ~lgN 个节点；在最差的情况下，查找路径上会有 N 个节点（即每个节点只有一个子节点）。在通常情况下，树的形状与最好情况更加类似。
对BST的分析与快速排序（quicksort）类似：树的根节点类似于快速排序中的分割点（partitioning item）；子树的递归创建类似于快速排序里递归地进行子数组排序。
————————————————————————
对由N个随机的元素创建的一个二叉搜索树，查找命中平均需要 ~2lnN（约1.39lgN）次比较操作。
————————————————————————
对由N个随机的元素创建的一个二叉搜索树，查找失败和插入平均需要 ~2lnN（约1.39lgN）次比较操作。
————————————————————————
基于顺序的方法 & 删除 （Order-based methods and deletion）
二叉排序树被广泛应用的一个重要原因是：它保证了元素之间的相对顺序，可以支持许多基于顺序的操作。
最大值和最小值（Minimum and maximum)
可以递归地计算最小值（最大值同理，将左换为右即可）：
- 如果当前节点的左链接为空，则子树中的最小值为当前结点
- 如果当前结点的左链接不为空，则最小值是左链接所指子树中的最小值
这样，从根节点开始，就能递归地找到最小值（最大值）
public Key min()
{
return min(root).key;
}
private Node min(Node x)
{
if (x.left == null) return x;
return min(x.left)
}
下界和上界（Floor and ceiling）
如果一个给定的键比当前节点的键小，则这个键的下界一定在左子树中；如果比当前节点的键大，则这个键的下届可能在右子树中。
上界的查找与之类似，将“小”换为“大”，“左”换为“右”即可。
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;
}
选择（Selection）
如果我们要在一个大小为 N 的二叉排序树中找第 k 个元素（rank k），则一定有 k 个其他的元素比这个元素小。如果左子树的大小 t 大于 k，则我们在左子树中找第 k 个元素；如果 t 等于 k ，那么根节点处的元素就是我们要找的元素；如果 t 小于 k ，那么我们就在右子树中找第 k-t-1 个元素。如此递归，我们就能找到要找的元素。
private Node select(Node x, int 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;
}
序号（Rank）
和选择操作类似，如果给定的元素和根节点相等，则返回左子树的大小；如果给定的元素比根节点小，则返回它在左子树中的序号；如果比根节点大，则返回它在右节点中的序号加左子树大小加1
public int rank(Key key)
{ return rank(key, root); }
private int rank(Key key, Node x)
{
if (x==null) return 0;
int cmp = key.compareTo(x.key);
if (cmp < 0) return rank(key, x.left);
else if (cmp > 0) return rank(key, x.right) + size(x.left) + 1;
else return size(x.left);
}
删除（Deletion）
删除最小值和最大值
以删除最小值为例：沿着左链接一直从根节点往下，直到遇到一个 null左子树，然后用当前结点的右节点来代替它自己。这样，就删除了最小值。同理可实现删除最大值。
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)
{
delete(root ,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
{
if (x.right == null) return x.left;
if (x.left == null) return x.right;
Node t = x;
x = min(x.right);
x.right = deleteMin(t.right);
x .left = t.left;
}
x.N = size(x.left) + 1 + size(x.right);
return x;
}
区间查找（Range queries）
类似于中序遍历，将每个在范围内的元素添加到一个队列中，最后输出这个队列
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, Node lo, Node 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) leys(x.right, queue, lo ,hi);
}
————————————————————————
对一个二叉搜索树，在最差情况下，所有操作的时间复杂度都与树的高度成正比。
————————————————————————
二叉搜索树有一个前提：就是插入键的顺序可以很好地由随机模型来描述。如果不满足这一条件（比如插入一个有序序列），树的高度就会变得很大（N）
| 数据结构 | 最差情况 查找 |
最差情况 插入 |
平均情况 查找 |
平均情况 插入 |
是否高效支持基于顺序的操作？ |
|---|---|---|---|---|---|
| 顺序查找 （无序链表） |
N | N | N/2 | N | no |
| 二分查找 （有序数组） |
lg N | N | lg N | N/2 | yes |
| 二叉搜索树 | N | N | 1.39 lgN | 1.39 lgN | yes |