二叉查找树
上一篇文中，通过二分查找，我们实现了对数级别的查找方案，但因为使用了数组这一数据结构，插入时需要移动大量的元素，导致插入动作任然很慢。为了减少移动的元素，我们这次使用链表，为了保持二分查找的效率，我们将二者结合起来——二叉查找树。
一个二叉查找树就是一个二叉树，每个节点上包含有一个键一个值一个指向左节点的链接一个指向右节点的链接（这个图中的数字代表键，值没有显示）。而且每个结点的键都大于其左子树中的任意结点的键而小于右子树中任意结点的键。跟数组相比，键就好像是数组的下标，为了实现有序而设定的。值对应的就是数组中存的值。在以下代码中，为了代码简单清晰，我们没有使用泛型来定义键和值的类型，而是使用Int。实际上，键只需要实现了Comparable接口就可以，值可以是任何类型。
private class Node{
private int key;
private int value;
Node left,right;
public Node(int key,int value){
this.key=key;
this.value=value;
}
}查找
首先我们来看一下二叉查找树的查找，跟二分查找的相似度赶上了韩国明星脸的相似度。一个二叉树必须有一个根节点，我们首先查找这个元素是否在根节点里，如果在，ok返回就可以了；如果不在，所查找元素的key大于root的key，就去右子树中查找，小于就去左子树中查找，任何子树都有一个根，我们就可以继续这个过程，读到这也许你立刻感受到了递归的酸臭味。好吧，那我们就来递归实现一下
//递归get实现
public int get(int key){
return get(root,key);
}
private int get(Node root,int key){
if (root==null)return -1;//-1代表没找到，实际中value应该是一个泛型，返回Null
if (key>root.key)return get(root.right,key);
else if (key<root.key)return get(root.left,key);
else return root.value;
}插入
查找操作跟数组中的二分查找一样，同样的对数级别时间复杂度，二叉查找树更胜一筹的地方体现在插入元素上。
public void put(int key,int value){
root = put(root,key,value);
}
private Node put(Node root,int key,int value){
if (root==null)return new Node(key,value);
if (key>root.key)root.right = put(root.right,key,value);
else if (key<root.key)root.left = put(root.left,key,value);
else root.value=value;
return root;
}插入的过程，先是判断二叉树中是否存在要插入的键，如果存在，直接进行值的覆盖，如果不存在，就在合适的地方新建结点。
可以看到不论是查找还是插入我们都在对数级别实现了对应的操作，也都使用了递归的操作，递归实现的优点是简单易懂一目了然，但同样，非递归的实现效率要更高一些，而且jvm是对栈深有限制的，如果递归过深，stackoverflow就来拥抱你了。对与我们二叉查找树来说，如果树过于不平衡，就可能出现这种状况，当然下一篇文将解决这个平衡与否的问题。
查找和插入的非递归实现
下面分别给出插入和查找的非递归实现，其实都是一个思路——递归转循环。
//get非递归实现
public int get(int key,boolean notrecursion){
Node x=root;
while (x!=null){
if (x.key==key){
return x.value;
}else if (key>x.key){
x=root.right;
}else {
x=root.left;
}
}
return -1;
} //put的非递归实现
public void put(int key,int value,boolean notrecursion){
if (root==null)root = new Node(key,value);
Node x = root;
Node xfather=null;//x的父结点，当x为null是，成为新节点的父结点
while (x!=null){
if (key == x.key){
x.value = value;
return;
}else if (key<x.key){
xfather=x;
x=x.left;
if (x==null)xfather.left=new Node(key,value);
}else {
xfather=x;
x= x.right;
if (x==null)xfather.right = new Node(key,value);
}
}
}删除
二叉查找树还可以有其他的功能，比如排名，删除，范围查找等，这需要稍微复杂化一下上面的数据结构，使得每个树知道他有多少个子孙结点，并且每次操作之后还需要跟新这个数目的记录等等。最难以理解的就是删除操作。为了循序渐进，我们首先来说一下删除最小结点的步骤。
删除最小结点
因为二叉查找树是有序的，结点的左子树的键总是小于这个结点的键，于是从根节点开始我们不断查找结点的左子树结点，一旦一个结点的左子树为空，那么这个结点就是键最小结点。找到这个结点之后如何删除它呢？如果它没有任何子树，那么让他的父结点的左链接指向空就可以了，没有链接指向这个最小结点，它就会自动被垃圾回收。但如果它有一个右子树（由查找过程可知，它不可能有左子树），我们就需要让它的父结点的左连接指向这个最小结点的右子树。
public void deleteMin(){
root = deleteMin(root);
}
private Node deleteMin(Node root){
if (root.left==null)return root.right;
root.left = deleteMin(root.left);
return root;
}
如图进行了最小结点1的删除，红线替代了虚线，最终1被回收，灰色的线也就消失了。
删除任意结点
删除任意一个结点，需要考虑三种情况：一是这个结点只有一个子树，这种情况只需要让这个结点的父结点指向此结点的这个子树就可以了，在代码中就是直接返回这个结点的子树根结点；第二种情况就是这个结点没有子树，那么直接让它的父结点指向null就可以了，在代码中就是直接返回Null；这两种情况在删除最小结点中都出现了，最繁琐的是第三种情况，这个结点有两个子树。这个情况需要我们一步一步来进行删除：
- 用t指向即将被删除的结点
- 将x指向min(t.right)，也就是被删除结点的右子树中的最小结点
- 将x的右链接指向deleteMin(t.right)，因为deleteMin(t.right)返回的是t的右子树删除最小结点之后的根节点，所以这一步也就是用x来代替t的位置
- 将x的左链接设为t.left，然后通过递归调用的返回更新各个链接，x对t的替代全部完成 public void delete(int key){ root = delete(root,key); } private Node delete(Node x,int key){ if (x==null)return null; if (x.key>key)return delete(x.left,key); else if (x.key<key)return delete(x.right,key); else { if (x.right==null)return x.left; if (x.left==null)return x.right; Node t = x; x=min(t.right); x.right=deleteMin(root.right); x.left=t.left; } return x; } private Node min(Node root){ if (root==null)return null; Node x = root; while (root!=null){ x = root; root = root.left; } return x; }
如图删除了结点3，根节点5左链接最终指向4，4的左链接指向1，4的右连接指向deleteMin(4)，因为4没有子树，所以deleteMin(4)返回的也就是Null。