我們?cè)谥霸诘谄哒聦W(xué)習(xí)優(yōu)先隊(duì)列中學(xué)習(xí)堆有序中學(xué)習(xí)到了完全二叉樹(shù)堂油，而這里我們將范圍擴(kuò)大變成二叉樹(shù)，而且將每個(gè)結(jié)點(diǎn)變成存儲(chǔ)鍵值對(duì)的數(shù)據(jù)碧绞，這就成為二叉查找樹(shù)府框。
強(qiáng)調(diào)一下，其實(shí)一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)往下的所有部分也可以看成一個(gè)二叉樹(shù)讥邻，按子結(jié)點(diǎn)是左還是右分為左子樹(shù)和右子樹(shù)迫靖。
實(shí)際上每個(gè)結(jié)點(diǎn)的鍵是有比較值的，每個(gè)結(jié)點(diǎn)的鍵都大于左子樹(shù)中任意結(jié)點(diǎn)的鍵而小于右子樹(shù)任意結(jié)點(diǎn)的鍵兴使。
所以我們搜尋一個(gè)結(jié)點(diǎn)系宜，其實(shí)就是遍歷二叉樹(shù)的一個(gè)過(guò)程，由于是二叉发魄，所以就很有規(guī)律蜈首。
我們從根結(jié)點(diǎn)出發(fā)，每到一個(gè)結(jié)點(diǎn)欠母，就和當(dāng)前結(jié)點(diǎn)比較，如果比當(dāng)前結(jié)點(diǎn)大就遍歷結(jié)點(diǎn)的右子樹(shù)吆寨，如果比它下則遍歷左子樹(shù)赏淌，重復(fù)以往，直到找到所要的點(diǎn)或者找到子結(jié)點(diǎn)了（說(shuō)明樹(shù)中并無(wú)該值）
這樣我們其實(shí)每次比較啄清，選擇子樹(shù)其實(shí)可以說(shuō)是有一種二分的思想了六水。
public class BinarySearchTree<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 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小于等于的結(jié)點(diǎn)） ceiling（找到最小的比key大于等于的結(jié)點(diǎn)），后面兩個(gè)實(shí)現(xiàn)的思路有點(diǎn)意思辣卒。
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;
}
//如果該結(jié)點(diǎn)比key要大的話(huà)掷贾，就要找左子樹(shù)，如果沒(méi)有左子樹(shù)則返回null荣茫，因?yàn)闆](méi)有比key小的數(shù)
if(x.key.compareTo(key) > 0){
return floor(x.left, key);
}
//如果該結(jié)點(diǎn)比key小想帅，則這個(gè)結(jié)點(diǎn)有可能就是所求答案，但可能會(huì)有比這個(gè)數(shù)更大但符合小于key的數(shù)啡莉。
//如果在右子樹(shù)找不到合適的數(shù)港准，則該結(jié)點(diǎn)就是答案
Node t=floor(x.right, key);
if(t!=null) return t; //經(jīng)過(guò)層層迭代，倘若不為空咧欣，這個(gè)就是迭代后最佳的答案浅缸，反正比自己好，也不敢多bb
else return x; //發(fā)現(xiàn)自己的右子樹(shù)沒(méi)有一個(gè)合適的人選魄咕，沒(méi)辦法就只能自己上衩椒。
}
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;
//結(jié)點(diǎn)比key小，不合適,要嘗試找更加大的
if(x.key.compareTo(key)<0) return ceiling(x.right, key);
//結(jié)點(diǎn)比key大了，看看有沒(méi)有稍微小一點(diǎn)的
Node t=ceiling(x.left, key);
if(t!=null) return t;
else return x;
}
select和rank
很有意思
左子樹(shù)的結(jié)點(diǎn)都是小于當(dāng)前結(jié)點(diǎn)的毛萌，而對(duì)于根結(jié)點(diǎn)和從根節(jié)點(diǎn)開(kāi)始一直走左邊所經(jīng)過(guò)的結(jié)點(diǎn)來(lái)說(shuō)苟弛，它的左子樹(shù)大小+1就是它當(dāng)前的序號(hào)。而對(duì)于右結(jié)點(diǎn)來(lái)說(shuō)朝聋，第k結(jié)點(diǎn)就是右子樹(shù)的第k-size(左子樹(shù))-1結(jié)點(diǎn)嗡午。
而rank是select的逆操作，其實(shí)就是不斷遍歷搜集所有比自己小的數(shù)冀痕，比如當(dāng)你發(fā)現(xiàn)比當(dāng)前結(jié)點(diǎn)大了荔睹，要往右子樹(shù)遍歷，此時(shí)候你必須記錄左子樹(shù)的所有結(jié)點(diǎn)的數(shù)目言蛇，然后再跑到右子樹(shù)進(jìn)行新的迭代僻他，倘若你需要往左子樹(shù)遍歷，則右子樹(shù)的結(jié)點(diǎn)和自己完全無(wú)關(guān)腊尚。
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小吨拗，說(shuō)明所要結(jié)點(diǎn)在左子樹(shù)
if(k<t) return select(x.left,k);
//k比t大，則需要從右子樹(shù)找了婿斥。注意此時(shí)要找的結(jié)點(diǎn)是“右子樹(shù)”中的第t-k-1個(gè)
else if(k>t) 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);
}
刪除操作
刪除有兩個(gè)操作劝篷。一個(gè)是deleteMin（刪除最小結(jié)點(diǎn)），一個(gè)是delete（一個(gè)是刪除指定鍵的結(jié)點(diǎn)）
我們知道對(duì)于一個(gè)結(jié)點(diǎn)來(lái)說(shuō)民宿，倘若它有左結(jié)點(diǎn)娇妓，那最小值肯定在左子樹(shù)當(dāng)中，否則自己就是最小的活鹰。
public void deleteMin() {
root=deleteMin(root);
}
private Node deleteMin(Node x) {
//x.left=null說(shuō)明此時(shí)x就是最小點(diǎn)哈恰，要?jiǎng)h除該點(diǎn)，要將右子樹(shù)接到其父結(jié)點(diǎn)中
if(x.left==null) return x.right; //如果沒(méi)有右結(jié)點(diǎn)返回null也合適
x.left=deleteMin(x.left); //更新父結(jié)點(diǎn)
x.N=size(x.left)+size(x.right)+1; //更新每一個(gè)結(jié)點(diǎn)的x.N
return x;
}
對(duì)于delete來(lái)說(shuō)志群，找到所要?jiǎng)h除的結(jié)點(diǎn)并不難着绷，重點(diǎn)是刪除結(jié)點(diǎn)后它的子結(jié)點(diǎn)（子樹(shù)）該怎么接到父結(jié)點(diǎn)上。有三種情況锌云，沒(méi)有子樹(shù)荠医，只有左子樹(shù)或右子樹(shù)，同時(shí)有左右子樹(shù)宾抓。第一種很簡(jiǎn)單子漩，第二種直接將剩下的子樹(shù)接到父結(jié)點(diǎn)即可。第三種比較麻煩石洗，我們知道父結(jié)點(diǎn)只有一個(gè)子結(jié)點(diǎn)的接口幢泼。不可能直接將兩個(gè)子樹(shù)接上去。
所以我們需要從一個(gè)子結(jié)點(diǎn)中找到一個(gè)合適的結(jié)點(diǎn)來(lái)代替將要被刪除的結(jié)點(diǎn)的位置讲衫。唯一合適的子結(jié)點(diǎn)就一定存在在右子樹(shù)的最小的結(jié)點(diǎn)A上缕棵。（仔細(xì)體會(huì)一下）孵班。
然后左子樹(shù)接在A的左結(jié)點(diǎn)上，而原來(lái)右子樹(shù)需要處理招驴，因?yàn)?strong>A可能本來(lái)就有右子樹(shù)篙程，需要將A的右子樹(shù)接在它的父結(jié)點(diǎn)上（執(zhí)行deleteMin操作），然后再將整個(gè)右子樹(shù)接到A的右邊别厘。
再更新受影響各個(gè)結(jié)點(diǎn)的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 {
//被刪除的結(jié)點(diǎn)B只有一個(gè)子結(jié)點(diǎn)
if(x.right==null) return x.left;
if(x.left==null) return x.right;
Node t=x;
//找到代替刪除結(jié)點(diǎn)的結(jié)點(diǎn)A
x=min(t.right);
//deleteMin處理代替結(jié)點(diǎn)可能存在的右子樹(shù)的情況,然后將B經(jīng)處理右子樹(shù)接在A上
x.right=deleteMin(t.right);
x.left=t.left;
}
//更新N值
x.N=size(x.left)+size(x.right)+1;
return x;
}
鍵查找
//遍歷所有的鍵虱饿，應(yīng)該是從小到大順序的
public Iterable<Key>keys(){
return keys(min(),max());
}
public Iterable<Key>keys(Key lo,Key hi){
LinkedList<Key> queue=new LinkedList<Key>();
keys(root,queue,lo,hi);
return queue;
}
private void keys(Node x,LinkedList<Key> queue,Key lo,Key hi) {
if(x==null) return;
int cmplo=lo.compareTo(x.key);
int cmphi=hi.compareTo(x.key);
//從左往右找，按從小到大順序
//說(shuō)明當(dāng)前的結(jié)點(diǎn)比較大触趴，可以看看有沒(méi)有更小的但符合范圍的結(jié)點(diǎn)
if(cmplo<0) keys(x.left,queue,lo,hi);
//合適的鍵氮发，加入隊(duì)列當(dāng)中
if(cmplo<=0&&cmphi>=0) queue.addFirst(x.key);
if(cmphi>0) keys(x.right,queue,lo,hi);
}
二叉查找樹(shù)平均情況：查找1.39logN 插入1.39logN
