前言

一般用符號(hào)表來(lái)儲(chǔ)存鍵值對(duì)，就好像字典那樣，通過(guò)索引來(lái)查找值，若鍵重復(fù)則覆蓋值。我們能希望找到一種高效的查找算法使在平均情況和最差情況下，時(shí)間復(fù)雜度都能達(dá)到O(logn)。下面會(huì)逐步介紹四種算法，最終達(dá)到我們的目的。

順序查找

用鏈表實(shí)現(xiàn)，無(wú)法索引數(shù)據(jù)，必須遍歷找數(shù)據(jù)，速度比較慢，查找插入時(shí)間復(fù)雜度都為O(n)，而且無(wú)法保證有序。但是實(shí)現(xiàn)簡(jiǎn)單，適用于小型數(shù)據(jù)。

public class SequentialSearchST? {? ? private Node head;? ? private int size=0;? ? public void put(Key key,Value v){? ? ? ? Node p=head;? ? ? ? while(p!=null){? ? ? ? ? ? if(p.key.equals(key)){? ? ? ? ? ? ? ? p.v=v;? ? ? ? ? ? ? ? return;? ? ? ? ? ? }? ? ? ? ? ? p=p.next;? ? ? ? }? ? ? ? head=new Node(key,v,head);? ? ? ? size++;? ? }? ? public Value get(Key key){? ? ? ? Node p=head;? ? ? ? while (p!=null){? ? ? ? ? ? if(p.key.equals(key)){? ? ? ? ? ? ? ? return? p.v;? ? ? ? ? ? }? ? ? ? ? ? p=p.next;? ? ? ? }? ? ? ? return null;? ? }}

二分查找

用數(shù)組保存數(shù)據(jù)，保證有序。二分查找速度很快，但是僅限于查找。因?yàn)椴迦氲臅r(shí)候要保證有序，所以要往后移動(dòng)數(shù)據(jù)以便插入。查找復(fù)雜度O(logn),插入復(fù)雜度O(n)。

public class BinarySearch {? ? public void put(Key key,Value value){? ? ? ? int index=rank(key);? ? ? ? //鍵相等則覆蓋值? ? ? ? if(keys[index]!=null&&key.compareTo(keys[index])==0){? ? ? ? ? ? values[index]=value;? ? ? ? ? ? return;? ? ? ? }? ? ? ? //把數(shù)據(jù)往后移，以便插入? ? ? ? for(int i=size+1;i>index;i--){? ? ? ? ? ? keys[i]=keys[i-1];? ? ? ? ? ? values[i]=values[i-1];? ? ? ? }? ? ? ? keys[index]=key;? ? ? ? values[index]=value;? ? ? ? size++;? ? }? ? public Value get(Key key){? ? ? ? int index=rank(key);//二分查找? ? ? ? if(keys[index]!=null && key.compareTo(keys[index])==0){? ? ? ? ? ? return values[index];? ? ? ? }? ? ? ? return null;? ? }? ? ? public int rank(Key key){return rank(key,0,size);}? ? public int rank(Key key,int l,int h){? ? ? ? if(l>h) return l;? ? ? ? int mid = (l+h)/2;? ? ? ? int cmp=0;? ? ? ? if(keys[mid]!=null)? ? ? ? ? ? cmp=key.compareTo(keys[mid]);? ? ? ? if(cmp<0)? ? ? ? ? ? return rank(key,l,mid-1);? ? ? ? else if(cmp>0)? ? ? ? ? ? return rank(key,mid+1,h);? ? ? ? return mid;? ? }}

二叉搜索樹(shù)

通過(guò)前面兩個(gè)算法，我們可以知道鏈表能快速刪除插入，而二分能快速查找。所以我們想找到一種結(jié)構(gòu)既是鏈?zhǔn)浇Y(jié)構(gòu)，同時(shí)又能進(jìn)行二分查找，同時(shí)保證查找和插入的高效性。

答案就是二叉搜索樹(shù)。

定義

是二叉樹(shù)

每個(gè)節(jié)點(diǎn)含有一個(gè)鍵和關(guān)聯(lián)的值

且每個(gè)節(jié)點(diǎn)的鍵大于左兒子且小于右兒子

實(shí)現(xiàn)

其實(shí)給出定義，實(shí)現(xiàn)就已經(jīng)很清楚了。說(shuō)白了就是從無(wú)到有構(gòu)造一個(gè)二叉樹(shù)，每次插入都和樹(shù)中的節(jié)點(diǎn)進(jìn)行比較，小的放左邊，大的放右邊。就如同快速排序，用一個(gè)主元把左右兩邊分開(kāi)。

還是直接看代碼清楚點(diǎn)

public class BST{? ? Node root;? ? public void put(Key key,Value value){? ? ? ? root = put(root,key,value);? ? }? ? public Node put(Node x, Key key, Value value) {? ? ? ? if(x==null){? ? ? ? ? ? return new Node(key,value,0);? ? ? ? }? ? ? ? int cmp = key.compareTo(x.key);? ? ? ? if(cmp<0) x.left=put(x.left,key,value);? ? ? ? else if(cmp>0) x.right=put(x.right,key,value);? ? ? ? else {? ? ? ? ? ? x.value=value;? ? ? ? ? ? x.N = size(x.right)+size(x.left)+1;? ? ? ? }? ? ? ? return x;? ? }? ? 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);? ? ? ? return x.value;? ? }}

效率問(wèn)題

二叉搜索樹(shù)的查找和搜索在平均情況下時(shí)間復(fù)雜度都能達(dá)到O(logn)，而且能保證數(shù)據(jù)有序。二叉搜索樹(shù)的中序遍歷就是數(shù)據(jù)的順序。我們貌似已經(jīng)找到了一個(gè)最理想的算法。

但是這個(gè)效率只是在平均情況下。如果數(shù)據(jù)是逆序，或者順序，那么這棵樹(shù)就會(huì)發(fā)生一邊倒的情況使復(fù)雜度直接達(dá)到O(n)，就如同快排中選擇到糟糕的主元(最大或者最小)。比快排糟糕的是，快排我們能通過(guò)隨機(jī)打亂數(shù)據(jù)來(lái)避免這種情況發(fā)生。但二叉搜索樹(shù)則不行，數(shù)據(jù)都是客戶提供，直接插入到樹(shù)中的，這種情況其實(shí)經(jīng)常發(fā)生。

幸運(yùn)的是我們有平衡二叉樹(shù)可以解決這個(gè)問(wèn)題。

平衡二叉樹(shù)

2-3樹(shù)

為了保持樹(shù)平衡性，允許節(jié)點(diǎn)能保存兩個(gè)鍵值對(duì)，且能連三個(gè)兒子。這樣把節(jié)點(diǎn)分成了兩種類型。

2-節(jié)點(diǎn)?: 一個(gè)鍵值對(duì)，兩個(gè)兒子。 (也就是標(biāo)準(zhǔn)的二叉搜索樹(shù))

3-節(jié)點(diǎn)?: 兩個(gè)鍵值對(duì)，三個(gè)兒子。 (兩個(gè)鍵是有序的，左小右大。左兒子小于左邊的鍵，右兒子大于右邊的鍵，中間的兒子在兩個(gè)鍵之間)

實(shí)現(xiàn)原理

2-3樹(shù)插入比較復(fù)雜。在插入的同時(shí)保持平衡性。

向2-節(jié)點(diǎn)中插入鍵。這種情況比較簡(jiǎn)單。直接插入即可。

向3-節(jié)點(diǎn)中插入鍵。比較特殊。先暫時(shí)把鍵插入到3-節(jié)點(diǎn)，此時(shí)這個(gè)節(jié)點(diǎn)中就有了三個(gè)鍵，然后再把這個(gè)節(jié)點(diǎn)分開(kāi)。把中間的兒子簡(jiǎn)單當(dāng)根，左右兩邊的鍵當(dāng)兒子。若父節(jié)點(diǎn)還是3-節(jié)點(diǎn)，則繼續(xù)遞歸進(jìn)行。

性能分析

2-3樹(shù)性能可以說(shuō)是比較好的。不管數(shù)據(jù)怎么樣，查找刪除操作時(shí)間復(fù)雜度都能達(dá)到O(logn)。

但是2-3樹(shù)實(shí)現(xiàn)比較復(fù)雜，需要掌控的情況很多，剝離節(jié)點(diǎn)，傳遞節(jié)點(diǎn)等操作，都需要很復(fù)雜的代碼，且也會(huì)耗費(fèi)不少的時(shí)間。所以我們一般不怎么用原始的2-3樹(shù)，而是用2-3樹(shù)的變形紅黑樹(shù).

紅黑樹(shù)

紅黑樹(shù)最方便的地方除了插入和刪除操作的代碼略復(fù)雜以外，另外的操作都可以直接復(fù)制二叉搜索樹(shù)。

紅黑樹(shù)是2-3樹(shù)的變形，把3-節(jié)點(diǎn)分離開(kāi)來(lái)使之成為普通的2-節(jié)點(diǎn)。但是怎么表現(xiàn)分離開(kāi)的節(jié)點(diǎn)之間的聯(lián)系呢。我們用紅線把他們連起來(lái)。

巧妙地結(jié)合二叉搜索樹(shù)的高效查找操作和2-3樹(shù)的平衡插入操作。

每個(gè)節(jié)點(diǎn)都只有一根連向父節(jié)點(diǎn)的線。這個(gè)線的顏色稱為節(jié)點(diǎn)的顏色。

實(shí)現(xiàn)

我們通過(guò)旋轉(zhuǎn)來(lái)維持樹(shù)的平衡。一般有兩種情況需要旋轉(zhuǎn)。

連續(xù)兩個(gè)左節(jié)點(diǎn)的顏色為紅色,向右轉(zhuǎn)

右節(jié)點(diǎn)的顏色為紅色，向左轉(zhuǎn)

第三種情況是左右兩邊都為紅色。最好處理，不需要旋轉(zhuǎn)。只需要把左右兩個(gè)兒子的顏色改成黑色，再把自己的顏色改成黑色。可以想象成把3個(gè)鍵值對(duì)3-節(jié)點(diǎn)剝離開(kāi)。

public class BlackRedBST {? ? private final boolean RED = true;? ? private final boolean BLACK = false;? ? private Node root;? ? public void put(Key key,Value value){? ? ? ? root = put(root,key,value);? ? ? ? root.color = BLACK;? ? }? ? private Node put(Node x, Key key, Value value) {? ? ? ? if(x==null) return new Node(key,value,0,RED);? ? ? ? int cmp = key.compareTo(x.key);? ? ? ? if(cmp<0) x.left = put(x.left,key,value);? ? ? ? else if(cmp>0) x.right = put(x.right,key,value);? ? ? ? else if(cmp==0) x.value =value;? ? ? ? if( isRED(x.right) && !isRED(x.left)) x=rotateLeft(x);? ? ? ? if( isRED(x.left) && isRED(x.left.left)) x=rotateRight(x);? ? ? ? if( isRED(x.left) && isRED(x.right)) flipColor(x);? ? ? ? x.N = size(x.right) + size(x.left) +1;? ? ? ? return? x;? ? }? ? private void flipColor(Node x) {? ? ? ? x.right.color = BLACK;? ? ? ? x.left.color = BLACK;? ? ? ? x.color = RED;? ? }? ? private Node rotateLeft(Node x) {? ? ? ? Node r =x.right;? ? ? ? x.right = r.left;? ? ? ? r.left = x;? ? ? ? r.color = x.color;? ? ? ? x.color = RED;? ? ? ? x.N = size(x.left)+size(x.right) +1;? ? ? ? return r;? ? }? ? private Node rotateRight(Node x) {? ? ? ? Node r =x.left;? ? ? ? x.left = r.right;? ? ? ? r.right = x;? ? ? ? r.left.color = RED;? ? ? ? r.right.color = RED;? ? ? ? r.color =BLACK;? ? ? ? x.N = size(x.left)+size(x.right) +1;? ? ? ? return r;? ? }}

性能分析

無(wú)論數(shù)據(jù)如何，插入刪除時(shí)間復(fù)雜度都為O(logn)，可以說(shuō)達(dá)到了理想狀態(tài)，且代碼簡(jiǎn)單。

性能測(cè)試

分別對(duì)四個(gè)文件進(jìn)行插入搜索操作。

tale.txt(779kb)

順序查找(7.143秒) 二分查找(0.46秒)?二叉搜索樹(shù)(0.191秒)?紅黑樹(shù)(0.237秒)

leipzig100k.txt(12670kb)

順序查找(無(wú)) 二分查找(13.911秒)?二叉搜索樹(shù)(1.389秒)?紅黑樹(shù)(1.442秒)

leipzig300k.txt(37966kb)

順序查找(無(wú)) 二分查找(60.222秒)?二叉搜索樹(shù)(2.742秒)?紅黑樹(shù)(3.104秒)

leipzig1m.txt(126607kb)

順序查找(無(wú)) 二分查找(無(wú))?二叉搜索樹(shù)(3.016秒)?紅黑樹(shù)(2.797秒)

由上面的數(shù)據(jù)分析，順序查找實(shí)際是非常慢的。而二分查找對(duì)小型數(shù)據(jù)還是比較快，但是數(shù)據(jù)一大就不行了。

而這里的二叉搜索樹(shù)和紅黑樹(shù)，無(wú)論什么數(shù)據(jù)效率都是極高。而且由leipzig300k.txt到leipzig1m.txt數(shù)據(jù)幾乎翻了4倍，而這兩種算法的效率幾乎沒(méi)收什么影響。

這里因?yàn)槲业臄?shù)據(jù)比較平均的關(guān)系，比較不出紅黑樹(shù)和二叉搜索樹(shù)的差異。我自己構(gòu)造了一組數(shù)據(jù)進(jìn)行測(cè)試。完全逆序的100000個(gè)數(shù)進(jìn)行插入刪除。

紅黑樹(shù)(0.173秒)

二叉搜索樹(shù)(StackOverflow)

Reference

維基百科