算法系列笔记（九）二叉查找树算法系列笔记（九）二叉查找

我们在之前在第七章学习优先队列中学习堆有序中学习到了完全二叉树，而这里我们将范围扩大变成二叉树，而且将每个结点变成存储键值对的数据，这就成为二叉查找树。
强调一下，其实一个结点的子结点往下的所有部分也可以看成一个二叉树，按子结点是左还是右分为左子树和右子树。
实际上每个结点的键是有比较值的，每个结点的键都大于左子树中任意结点的键而小于右子树任意结点的键。
所以我们搜寻一个结点，其实就是遍历二叉树的一个过程，由于是二叉，所以就很有规律。

我们从根结点出发，每到一个结点，就和当前结点比较，如果比当前结点大就遍历结点的右子树，如果比它下则遍历左子树，重复以往，直到找到所要的点或者找到子结点了（说明树中并无该值）

这样我们其实每次比较，选择子树其实可以说是有一种二分的思想了。

public class BinarySearchTree,Value> { private Node root; private class Node{ private Key key; private Value val; private Node left,right; private int N; public Node(Key k,Value v,int a) { key=k; val=v; N=a; } }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); } 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) { 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; return x; } }

找大小 【算法系列笔记（九）二叉查找树】下面是min max floor（找到最大的比key小于等于的结点） ceiling（找到最小的比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 max() { return max(root).key; } private Node max(Node x) { if(x.right==null) return x; return max(x.right); }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; if(x.key.compareTo(key) == 0){ return x; }//如果该结点比key要大的话，就要找左子树，如果没有左子树则返回null，因为没有比key小的数 if(x.key.compareTo(key) > 0){ return floor(x.left, key); } //如果该结点比key小，则这个结点有可能就是所求答案，但可能会有比这个数更大但符合小于key的数。 //如果在右子树找不到合适的数，则该结点就是答案 Node t=floor(x.right, key); if(t!=null) return t; //经过层层迭代，倘若不为空，这个就是迭代后最佳的答案，反正比自己好，也不敢多bb else return x; //发现自己的右子树没有一个合适的人选，没办法就只能自己上。 }public Key ceiling(Key key) { Node x=ceiling(root,key); if(x==null) return null; return x.key; } private Node ceiling(Node x,Key key) { if(x==null) return null; if(x.key.compareTo(key)==0) return x; //结点比key小，不合适,要尝试找更加大的 if(x.key.compareTo(key)<0) return ceiling(x.right, key); //结点比key大了，看看有没有稍微小一点的 Node t=ceiling(x.left, key); if(t!=null) return t; else return x; }

select和rank 很有意思

左子树的结点都是小于当前结点的，而对于根结点和从根节点开始一直走左边所经过的结点来说，它的左子树大小+1就是它当前的序号。而对于右结点来说，第k结点就是右子树的第k-size(左子树)-1结点。

而rank是select的逆操作，其实就是不断遍历搜集所有比自己小的数，比如当你发现比当前结点大了，要往右子树遍历，此时候你必须记录左子树的所有结点的数目，然后再跑到右子树进行新的迭代，倘若你需要往左子树遍历，则右子树的结点和自己完全无关。

public Key select(int k) { return select(root,k).key; } private Node select(Node x,int k) { if(x==null) return null; int t=size(x.left); //k比t小，说明所要结点在左子树 if(kt) return select(x.right, t-k-1); else return x; }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 1+size(x.left)+rank(key, x.right); else return size(x.left); }

删除操作删除有两个操作。一个是deleteMin（删除最小结点），一个是delete（一个是删除指定键的结点）
我们知道对于一个结点来说，倘若它有左结点，那最小值肯定在左子树当中，否则自己就是最小的。

public void deleteMin() { root=deleteMin(root); } private Node deleteMin(Node x) { //x.left=null说明此时x就是最小点，要删除该点，要将右子树接到其父结点中 if(x.left==null) return x.right; //如果没有右结点返回null也合适 x.left=deleteMin(x.left); //更新父结点 x.N=size(x.left)+size(x.right)+1; //更新每一个结点的x.N return x; }

对于delete来说，找到所要删除的结点并不难，重点是删除结点后它的子结点（子树）该怎么接到父结点上。有三种情况，没有子树，只有左子树或右子树，同时有左右子树。第一种很简单，第二种直接将剩下的子树接到父结点即可。第三种比较麻烦，我们知道父结点只有一个子结点的接口。不可能直接将两个子树接上去。

所以我们需要从一个子结点中找到一个合适的结点来代替将要被删除的结点的位置。唯一合适的子结点就一定存在在右子树的最小的结点A上。（仔细体会一下）。
然后左子树接在A的左结点上，而原来右子树需要处理，因为A可能本来就有右子树，需要将A的右子树接在它的父结点上（执行deleteMin操作），然后再将整个右子树接到A的右边。
再更新受影响各个结点的N

public void delete(Key key) { root=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 { //被删除的结点B只有一个子结点 if(x.right==null) return x.left; if(x.left==null) return x.right; Node t=x; //找到代替删除结点的结点A x=min(t.right); //deleteMin处理代替结点可能存在的右子树的情况,然后将B经处理右子树接在A上 x.right=deleteMin(t.right); x.left=t.left; } //更新N值 x.N=size(x.left)+size(x.right)+1; return x; }

键查找

//遍历所有的键，应该是从小到大顺序的 public Iterablekeys(){ return keys(min(),max()); } public Iterablekeys(Key lo,Key hi){ LinkedList queue=new LinkedList(); keys(root,queue,lo,hi); return queue; } private void keys(Node x,LinkedList 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.addFirst(x.key); if(cmphi>0) keys(x.right,queue,lo,hi); }

二叉查找树平均情况：查找1.39logN 插入1.39logN