摘要：前文數(shù)據(jù)結(jié)構(gòu)與算法常用數(shù)據(jù)結(jié)構(gòu)及其實現(xiàn)總結(jié)了基本的數(shù)據(jù)結(jié)構(gòu)，類似的，本文準(zhǔn)備總結(jié)一下一些常見的高級的數(shù)據(jù)結(jié)構(gòu)及其常見算法和對應(yīng)的實現(xiàn)以及應(yīng)用場景，務(wù)求理論與實踐一步到位。

前文 數(shù)據(jù)結(jié)構(gòu)與算法——常用數(shù)據(jù)結(jié)構(gòu)及其Java實現(xiàn) 總結(jié)了基本的數(shù)據(jù)結(jié)構(gòu)，類似的，本文準(zhǔn)備總結(jié)一下一些常見的高級的數(shù)據(jù)結(jié)構(gòu)及其常見算法和對應(yīng)的Java實現(xiàn)以及應(yīng)用場景，務(wù)求理論與實踐一步到位。

跳躍列表是對有序的鏈表增加上附加的前進(jìn)鏈接，增加是以隨機化的方式進(jìn)行的，所以在列表中的查找可以快速的跳過部分列表。是一種隨機化數(shù)據(jù)結(jié)構(gòu)，基于并聯(lián)的鏈表，其效率可比擬于紅黑樹和AVL樹(對于大多數(shù)操作需要O(logn)平均時間)，但是實現(xiàn)起來更容易且對并發(fā)算法友好。redis 的 sorted SET 就是用了跳躍表。

性質(zhì)：

由很多層結(jié)構(gòu)組成；

每一層都是一個有序的鏈表，排列順序為由高層到底層，都至少包含兩個鏈表節(jié)點，分別是前面的head節(jié)點和后面的nil節(jié)點；

最底層的鏈表包含了所有的元素；

如果一個元素出現(xiàn)在某一層的鏈表中，那么在該層之下的鏈表也全都會出現(xiàn)（上一層的元素是當(dāng)前層的元素的子集）；

鏈表中的每個節(jié)點都包含兩個指針，一個指向同一層的下一個鏈表節(jié)點，另一個指向下一層的同一個鏈表節(jié)點；

可以看到，這里一共有4層，最上面就是最高層（Level 3），最下面的層就是最底層（Level 0），然后每一列中的鏈表節(jié)點中的值都是相同的，用指針來連接著。跳躍表的層數(shù)跟結(jié)構(gòu)中最高節(jié)點的高度相同。理想情況下，跳躍表結(jié)構(gòu)中第一層中存在所有的節(jié)點，第二層只有一半的節(jié)點，而且是均勻間隔，第三層則存在1/4的節(jié)點，并且是均勻間隔的，以此類推，這樣理想的層數(shù)就是logN。

全部代碼在此

查找：
從最高層的鏈表節(jié)點開始，相等則停止查找；如果比當(dāng)前節(jié)點要大和比當(dāng)前層的下一個節(jié)點要小，那么則往下找；否則在當(dāng)前層繼續(xù)往后比較，以此類推，一直找到最底層的最后一個節(jié)點，如果找到則返回，反之則返回空。

插入：
要插入，首先需要確定插入的層數(shù)，這里有幾種方法。1. 拋硬幣，只要是正面就累加，直到遇見反面才停止，最后記錄正面的次數(shù)并將其作為要添加新元素的層；2. 統(tǒng)計概率，先給定一個概率p，產(chǎn)生一個0到1之間的隨機數(shù)，如果這個隨機數(shù)小于p，則將高度加1，直到產(chǎn)生的隨機數(shù)大于概率p才停止，根據(jù)給出的結(jié)論，當(dāng)概率為1/2或者是1/4的時候，整體的性能會比較好（其實當(dāng)p為1/2的時候，就是拋硬幣的方法）。當(dāng)確定好要插入的層數(shù)k以后，則需要將元素都插入到從最底層到第k層。

刪除：
在各個層中找到包含指定值的節(jié)點，然后將節(jié)點從鏈表中刪除即可，如果刪除以后只剩下頭尾兩個節(jié)點，則刪除這一層。

平衡二叉樹的定義都不怎么準(zhǔn)，即使是維基百科。我在這里大概說一下，左右子樹高度差用 HB(k) 來表示，當(dāng) k=0 為完全平衡二叉樹，當(dāng) k<=1 為AVL樹，當(dāng) k>=1 但是接近平衡的是紅黑樹，其它平衡的還有如Treap、替罪羊樹等，總之就是高度能保持在O(logn)級別的二叉樹。紅黑樹是一種自平衡二叉查找樹，也被稱為"對稱二叉B樹"，保證樹的高度在[logN,logN+1]（理論上，極端的情況下可以出現(xiàn)RBTree的高度達(dá)到2*logN，但實際上很難遇到）。它是復(fù)雜的，但它的操作有著良好的最壞運行時間：它可以在O(logn)時間內(nèi)做查找，插入和刪除。

紅黑樹是每個節(jié)點都帶有顏色屬性的二叉查找樹，顏色為紅色或黑色。在二叉查找樹強制一般要求以外，有如下額外要求：

節(jié)點是紅色或黑色。

根是黑色。

所有葉子都是黑色（葉子是NIL節(jié)點，亦即空節(jié)點）。

每個紅色節(jié)點的子節(jié)點必須是黑色的。（從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點）

從任一節(jié)點到其每個葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點。

這些約束確保了紅黑樹的關(guān)鍵特性：從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。結(jié)果是這個樹大致上是平衡的（AVL樹平衡程度更高）。因為操作比如插入、刪除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同于普通的二叉查找樹。
要知道為什么這些性質(zhì)確保了這個結(jié)果，注意到性質(zhì)4導(dǎo)致了路徑不能有兩個毗連的紅色節(jié)點就足夠了。最短的可能路徑都是黑色節(jié)點，最長的可能路徑有交替的紅色和黑色節(jié)點。因為根據(jù)性質(zhì)5所有最長的路徑都有相同數(shù)目的黑色節(jié)點，這就表明了沒有路徑能多于任何其他路徑的兩倍長。而且插入和刪除操作都只需要<=3次的節(jié)點旋轉(zhuǎn)操作，而AVL樹可能需要O(logn)次。正是因為這種時間上的保證，紅黑樹廣泛應(yīng)用于 Nginx 和 Node.js 等的 timer 中，Java 8 中 HashMap 與 ConcurrentHashMap 也因為用紅黑樹取代了鏈表，性能有所提升。

Java定義：

class  Node{
   public   T value;
   public   Node parent;
   public   boolean isRed;
   public   Node left;
   public   Node right;
}

查找：
因為每一個紅黑樹也是一個特殊的二叉查找樹，因此紅黑樹上的查找操作與普通二叉查找樹相同，可見上文，這里不再贅述。
然而，在紅黑樹上進(jìn)行插入操作和刪除操作會導(dǎo)致不再匹配紅黑樹的性質(zhì)?；謴?fù)紅黑樹的性質(zhì)需要少量（logn）的顏色變更（實際是非?？焖俚模┖筒怀^三次樹旋轉(zhuǎn)（對于插入操作是兩次）。雖然插入和刪除很復(fù)雜，但操作時間仍可以保持為O(logn)。

左、右旋：
左左情況對應(yīng)右旋，右右情況對應(yīng)左旋，同AVL樹，可見上文

插入：
插入操作首先類似于二叉查找樹的插入，只是任何一個插入的新結(jié)點的初始顏色都為紅色，因為插入黑點會增加某條路徑上黑結(jié)點的數(shù)目，從而導(dǎo)致整棵樹黑高度的不平衡，所以為了盡可能維持所有性質(zhì)新插入節(jié)點總是先設(shè)為紅色，但還是可能會違返紅黑樹性質(zhì)，亦即在新插入節(jié)點的父節(jié)點為紅色節(jié)點的時候，這時就需要通過一系列操作來使紅黑樹保持平衡。破壞性質(zhì)的情況有：

 1. 叔叔節(jié)點也為紅色。
 2. 叔叔節(jié)點為空，且祖父節(jié)點、父節(jié)點和新節(jié)點處于一條斜線上。
 3. 叔叔節(jié)點為空，且祖父節(jié)點、父節(jié)點和新節(jié)點不處于一條斜線上。

1、D是新插入節(jié)點，將父節(jié)點和叔叔節(jié)點與祖父節(jié)點的顏色互換，然后D的祖父節(jié)點A變成了新插入節(jié)點，如果A的父節(jié)點是紅色則繼續(xù)調(diào)整

2、C是新插入節(jié)點，將B節(jié)點進(jìn)行右旋操作，并且和父節(jié)點A互換顏色，如果B和C節(jié)點都是右節(jié)點的話，只要將操作變成左旋就可以了。

3、C是新插入節(jié)點，將C節(jié)點進(jìn)行左旋，這樣就從 3 轉(zhuǎn)換成 2了，然后針對 2 進(jìn)行操作處理就行了。2 操作做了一個右旋操作和顏色互換來達(dá)到目的。如果樹的結(jié)構(gòu)是下圖的鏡像結(jié)構(gòu)，則只需要將對應(yīng)的左旋變成右旋，右旋變成左旋即可。

如果上面的3中情況如果對應(yīng)的操作是在右子樹上，做對應(yīng)的鏡像操作就是了。

刪除：
刪除操作首先類似于二叉查找樹的刪除，如果刪除的是紅色節(jié)點或者葉子則不需要特別的紅黑樹定義修復(fù)（但是需要二叉查找樹的修復(fù)），黑色節(jié)點則需要修復(fù)。刪除修復(fù)操作分為四種情況(刪除黑節(jié)點后)：

1. 兄弟節(jié)點是紅色的。
2. 兄弟節(jié)點是黑色的，且兄弟節(jié)點的子節(jié)點都是黑色的。
3. 兄弟節(jié)點是黑色的，且兄弟節(jié)點的左子節(jié)點是紅色的，右節(jié)點是黑色的(兄弟節(jié)點在右邊)，如果兄弟節(jié)點在左邊的話，就是兄弟節(jié)點的右子節(jié)點是紅色的，左節(jié)點是黑色的。
4. 兄弟節(jié)點是黑色的，且右子節(jié)點是是紅色的(兄弟節(jié)點在右邊)，如果兄弟節(jié)點在左邊，則就是對應(yīng)的就是左節(jié)點是紅色的。

刪除操作最復(fù)雜的操作，總體思想是從兄弟節(jié)點借調(diào)黑色節(jié)點使樹保持局部的平衡，如果局部的平衡達(dá)到了，就看整體的樹是否是平衡的，如果不平衡就接著向上追溯調(diào)整。

1、將兄弟節(jié)點提升到父節(jié)點，轉(zhuǎn)換之后就會變成后面的狀態(tài) 2，3，或者4了，從待刪除節(jié)點開始調(diào)整

2、兄弟節(jié)點可以消除一個黑色節(jié)點，因為兄弟節(jié)點和兄弟節(jié)點的子節(jié)點都是黑色的，所以可以將兄弟節(jié)點變紅，這樣就可以保證樹的局部的顏色符合定義了。這個時候需要將父節(jié)點A變成新的節(jié)點，繼續(xù)向上調(diào)整，直到整顆樹的顏色符合RBTree的定義為止

3、左邊的紅色節(jié)點借調(diào)過來，這樣就可以轉(zhuǎn)換成狀態(tài) 4 了，3是一個中間狀態(tài)，是因為根據(jù)紅黑樹的定義來說，下圖并不是平衡的，他是通過case 2操作完后向上回溯出現(xiàn)的狀態(tài)。之所以會出現(xiàn)3和后面的4的情況，是因為可以通過借用侄子節(jié)點的紅色，變成黑色來符合紅黑樹定義5

4、是真正的節(jié)點借調(diào)操作，通過將兄弟節(jié)點以及兄弟節(jié)點的右節(jié)點借調(diào)過來，并將兄弟節(jié)點的右子節(jié)點變成紅色來達(dá)到借調(diào)兩個黑節(jié)點的目的，這樣的話，整棵樹還是符合RBTree的定義的。

注意，上述4種的鏡像情況就進(jìn)行鏡像處理即可，左對右，右對左。

全部代碼在此

B樹有一種說法是二叉查找樹，每個結(jié)點只存儲一個關(guān)鍵字，等于則命中，小于走左結(jié)點，大于走右結(jié)點，這樣的話上一篇文章就已經(jīng)說過了。但是實際上這樣翻譯是一種錯誤，B樹就是 B-tree 亦即B-樹。

B-樹（B-tree）是一種自平衡的樹，能夠保持?jǐn)?shù)據(jù)有序。這種數(shù)據(jù)結(jié)構(gòu)能夠讓查找數(shù)據(jù)、順序訪問、插入數(shù)據(jù)及刪除的動作，都在對數(shù)時間內(nèi)完成。B-樹，概括來說是一個一般化的二叉查找樹，可以擁有多于2個子節(jié)點（多路查找樹）。與自平衡二叉查找樹不同，B-樹為系統(tǒng)大塊數(shù)據(jù)的讀寫操作做了優(yōu)化。B-樹減少定位記錄時所經(jīng)歷的中間過程，從而加快存取速度。B-樹這種數(shù)據(jù)結(jié)構(gòu)可以用來描述外部存儲。這種數(shù)據(jù)結(jié)構(gòu)常被應(yīng)用在數(shù)據(jù)庫和文件系統(tǒng)的實現(xiàn)上，比如MySQL索引就用了B+樹。

B-樹可以看作是對二叉查找樹的一種擴展，即他允許每個節(jié)點有M-1個子節(jié)點。

根節(jié)點至少有兩個子節(jié)點

每個節(jié)點有M-1個key，并且以升序排列

位于M-1和M key的子節(jié)點的值位于M-1 和M key對應(yīng)的Value之間

其它節(jié)點至少有M/2個子節(jié)點，至多M個，非葉子結(jié)點存儲指向關(guān)鍵字范圍的子結(jié)點，所有關(guān)鍵字在整顆樹中出現(xiàn)，且只出現(xiàn)一次，非葉子結(jié)點可以命中；

B+樹是對B-樹的一種變形樹，在B-樹基礎(chǔ)上，為葉子結(jié)點增加鏈表指針，它與B-樹的差異在于：

有k個子結(jié)點的結(jié)點必然有k個關(guān)鍵碼

非葉結(jié)點僅具有索引作用，跟記錄有關(guān)的信息均存放在葉結(jié)點中，非葉子結(jié)點相當(dāng)于是葉子結(jié)點（包含所有關(guān)鍵字）的索引（稀疏索引），葉子結(jié)點才是存儲（關(guān)鍵字）數(shù)據(jù)的數(shù)據(jù)層。所以B+樹只有達(dá)到葉子結(jié)點才命中（B-樹可以在非葉子結(jié)點命中）

樹的所有葉結(jié)點構(gòu)成一個有序鏈表，可以按照關(guān)鍵碼排序的次序遍歷全部記錄

更適合文件索引系統(tǒng)

mysql中普遍使用B+樹做索引，但在實現(xiàn)上又根據(jù)聚簇索引和非聚簇索引而不同。所謂聚簇索引，就是指主索引文件和數(shù)據(jù)文件為同一份文件，聚簇索引主要用在Innodb存儲引擎中。在該索引實現(xiàn)方式中B+Tree的葉子節(jié)點上的data就是數(shù)據(jù)本身，key為主鍵，如果是一般索引的話，data便會指向?qū)?yīng)的主索引。在B+Tree的每個葉子節(jié)點增加一個指向相鄰葉子節(jié)點的指針，就形成了帶有順序訪問指針的B+Tree。做這個優(yōu)化的目的是為了提高區(qū)間訪問的性能。非聚簇索引就是指B+Tree的葉子節(jié)點上的data，并不是數(shù)據(jù)本身，而是數(shù)據(jù)存放的地址。主索引和輔助索引沒啥區(qū)別，只是主索引中的key一定得是唯一的。主要用在MyISAM存儲引擎中。非聚簇索引比聚簇索引多了一次讀取數(shù)據(jù)的IO操作，所以查找性能上會差一些。

一般來說，索引本身也很大，不可能全部存儲在內(nèi)存中，因此索引往往以索引文件的形式存儲的磁盤上。這樣的話，索引查找過程中就要產(chǎn)生磁盤I/O消耗，相對于內(nèi)存存取，I/O存取的消耗要高幾個數(shù)量級，所以評價一個數(shù)據(jù)結(jié)構(gòu)作為索引的優(yōu)劣最重要的指標(biāo)就是在查找過程中磁盤I/O操作次數(shù)的漸進(jìn)復(fù)雜度。換句話說，索引的結(jié)構(gòu)組織要盡量減少查找過程中磁盤I/O的存取次數(shù)。

B-Tree：如果一次檢索需要訪問4個節(jié)點，數(shù)據(jù)庫系統(tǒng)設(shè)計者利用磁盤預(yù)讀原理，把節(jié)點的大小設(shè)計為一個頁，那讀取一個節(jié)點只需要一次I/O操作，完成這次檢索操作，最多需要3次I/O(根節(jié)點常駐內(nèi)存)。數(shù)據(jù)記錄越小，每個節(jié)點存放的數(shù)據(jù)就越多，樹的高度也就越小，I/O操作就少了，檢索效率也就上去了。

B+Tree：非葉子節(jié)點只存key，大大滴減少了非葉子節(jié)點的大小，那么每個節(jié)點就可以存放更多的記錄，樹更矮了，I/O操作更少了。所以B+Tree擁有更好的性能。

針對B-樹，完整代碼在此

Java定義：

public class BTree, Value>  {
    private static final int M = 4;//
    private Node root;       // root of the B-tree
    private int height;      // height of the B-tree
    private int n;           // number of key-value pairs in the B-tree

    private static final class Node {
        private int m;                             // number of children
        private Entry[] children = new Entry[M];   // the array of children
        // create a node with k children
        private Node(int k) {
            m = k;
        }
    }
    private static class Entry {
        private Comparable key;
        private final Object val;
        private Node next;     // helper field to iterate over array entries
        public Entry(Comparable key, Object val, Node next) {
            this.key  = key;
            this.val  = val;
            this.next = next;
        }
    }
}

查找：

類似于二叉樹的查找。

public Value get(Key key) {
    return search(root, key, height);
}

private Value search(Node x, Key key, int ht) {
    Entry[] children = x.children;

    if (ht == 0) {
        for (int j = 0; j < x.m; j++) {
            if (eq(key, children[j].key)) return (Value) children[j].val;
        }
    }
    else {
        for (int j = 0; j < x.m; j++) {
            if (j+1 == x.m || less(key, children[j+1].key))
                return search(children[j].next, key, ht-1);
        }
    }
    return null;
}

插入：

首先要找到合適的插入位置直接插入，如果造成節(jié)點溢出就要分裂該節(jié)點，并用處于中間的key提升并插入到父節(jié)點去，直到當(dāng)前插入節(jié)點不溢出為止。

// split node in half
private Node split(Node h) {
    Node t = new Node(M/2);
    h.m = M/2;
    for (int j = 0; j < M/2; j++)
        t.children[j] = h.children[M/2+j]; 
    return t;    
}

public void put(Key key, Value val) {
    if (key == null) throw new IllegalArgumentException("argument key to put() is null");
    Node u = insert(root, key, val, height); 
    n++;
    if (u == null) return;

    // need to split root
    Node t = new Node(2);
    t.children[0] = new Entry(root.children[0].key, null, root);
    t.children[1] = new Entry(u.children[0].key, null, u);
    root = t;
    height++;
}

private Node insert(Node h, Key key, Value val, int ht) {
    int j;
    Entry t = new Entry(key, val, null);

    // external node
    if (ht == 0) {
        for (j = 0; j < h.m; j++) {
            if (less(key, h.children[j].key)) break;
        }
    }

    // internal node
    else {
        for (j = 0; j < h.m; j++) {
            if ((j+1 == h.m) || less(key, h.children[j+1].key)) {
                Node u = insert(h.children[j++].next, key, val, ht-1);
                if (u == null) return null;
                t.key = u.children[0].key;
                t.next = u;
                break;
            }
        }
    }

    for (int i = h.m; i > j; i--)
        h.children[i] = h.children[i-1];
    h.children[j] = t;
    h.m++;
    if (h.m < M) return null;
    else         return split(h);
}

刪除：

首先要找到節(jié)點所在位置，然后刪除，如果當(dāng)前節(jié)點key數(shù)量少于M/2 則要從兄弟或者父節(jié)點借key，但是這樣維護起來麻煩，一般采取懶刪除做法，亦即不是真正的刪除，只是標(biāo)記一下刪除了而已。

是B+樹的變體，在B+樹的非根和非葉子結(jié)點再增加指向兄弟的指針。

Trie（讀作try）樹又稱字典樹、單詞查找樹，是一種樹形結(jié)構(gòu)，是一種哈希樹的變種。典型應(yīng)用是用于統(tǒng)計，排序和保存大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計。它的優(yōu)點是：利用字符串的公共前綴來減少查詢時間，最大限度地減少無謂的字符串比較，查詢效率比哈希樹高。Trie的核心思想是空間換時間：利用字符串的公共前綴來降低查詢時間的開銷以達(dá)到提高效率的目的。

Trie樹的基本性質(zhì)：

每個節(jié)點最多包含R個子節(jié)點（R為字母表的大小，又稱為R向單詞查找樹）

根節(jié)點不包含字符，除根節(jié)點意外每個節(jié)點只包含一個字符。

從根節(jié)點到某一個節(jié)點，路徑上經(jīng)過的字符連接起來，為該節(jié)點對應(yīng)的字符串。

每個節(jié)點的所有子節(jié)點包含的字符串不相同。

例子：

add
adbc
bye

對應(yīng)樹：

Java定義：

class TrieNode {
    char c;// 該節(jié)點的數(shù)據(jù)
    int occurances;//前節(jié)點所對應(yīng)的字符串在字典樹里面出現(xiàn)的次數(shù)
    Map children;//當(dāng)前節(jié)點的子節(jié)點，保存的是它的下一個節(jié)點的字符
}

插入：

從頭到尾遍歷字符串的每一個字符

從根節(jié)點開始插入，若該字符存在，那就不用插入新節(jié)點，要是不存在，則插入新節(jié)點

然后順著插入的節(jié)點一直按照上述方法插入剩余的節(jié)點

為了統(tǒng)計每一個字符串出現(xiàn)的次數(shù)，應(yīng)該在最后一個節(jié)點插入后occurances++，表示這個字符串出現(xiàn)的次數(shù)增加一次

//新插入的字符串s，以及當(dāng)前待插入的字符c在s中的位置
int insert(String s, int pos) {
        
    //如果插入空串，則直接返回
    //此方法調(diào)用時從pos=0開始的遞歸調(diào)用，pos指的是插入的第pos個字符
    if (s == null || pos >= s.length())
        return 0;

    // 如果當(dāng)前節(jié)點沒有孩子節(jié)點，則new一個
    if (children == null)
        children = new HashMap();

    //獲取待插入字符的對應(yīng)節(jié)點
    char c = s.charAt(pos);
    TrieNode n = children.get(c);
    if (n == null) {//當(dāng)前待插入字符不存在于子節(jié)點中
        n = new TrieNode(c);//新創(chuàng)建一個節(jié)點
        children.put(c, n);//新建節(jié)點變?yōu)樽庸?jié)點
    }

    //插入的結(jié)束時直到最后一個字符插入，返回的結(jié)果是該字符串出現(xiàn)的次數(shù)
    //否則繼續(xù)插入下一個字符
    if (pos == s.length() - 1) {
        n.occurances++;
        return n.occurances;
    } else {
        return n.insert(s, pos + 1);
    }
}

刪除：

從root結(jié)點的孩子開始（因為每一個字符串的第一個字符肯定在root節(jié)點的孩子里），判斷該當(dāng)前節(jié)點是否為空，若為空且沒有到達(dá)所要刪除字符串的最后一個字符，則不存在該字符串。若已經(jīng)到達(dá)葉子結(jié)點但是并沒有遍歷完整個字符串，說明整個字符串也不存在，例如要刪除的是"harlan1994"，而有"harlan".

只有當(dāng)要刪除的字符串找到時并且最后一個字符正好是葉子節(jié)點時才需要刪除，而且任何刪除動作，只能發(fā)生在葉子節(jié)點。例如要刪除"byebye"，但是字典里還有"byebyeha"，說明byebye不需要刪除，只需要更改occurances=0即可標(biāo)志字典里已經(jīng)不存在"byebye"這個字符串了

當(dāng)遍歷到最后一個字符時，也就是說字典里存在該字符，必須將當(dāng)前節(jié)點的occurances設(shè)為0，這樣標(biāo)志著當(dāng)前節(jié)點代表的這個字符串已經(jīng)不存在了，而要不要刪除，需要考慮2中所提到的情況，也就是說，只有刪除只發(fā)生在葉子節(jié)點上。

//待刪除的字符串s，以及當(dāng)前待刪除的字符c在s中的位置
boolean remove(String s, int pos) {
    if (children == null || s == null)
        return false;

    //取出第pos個字符，若不存在，則返回false
    char c = s.charAt(pos);
    TrieNode n = children.get(c);
    if (n == null)
        return false;

    //遞歸出口是已經(jīng)到了字符串的最后一個字符，若occurances=0，代表已經(jīng)刪除了
    //否則繼續(xù)遞歸到最后一個字符
    boolean ret;
    if (pos == s.length() - 1) {
        int before = n.occurances;
        n.occurances = 0;
        ret = before > 0;
    } else {
        ret = n.remove(s, pos + 1);
    }

    //刪除之后，必須刪除不必要的字符
    //比如保存的“Harlan”被刪除了，那么如果n保存在葉子節(jié)點，意味著它雖然被標(biāo)記著不存在了，但是還占著空間
    //所以必須刪除，但是如果“Harlan”刪除了，但是Trie里面還保存這“Harlan1994”,那么就不需要刪除字符了
    if (n.children == null && n.occurances == 0) {
        children.remove(n.c);
        if (children.size() == 0)
            children = null;
    }

    return ret;
}

求一個字符串出現(xiàn)的次數(shù)：

TrieNode lookup(String s, int pos) {
    if (s == null)
        return null;

    //如果找的次數(shù)已經(jīng)超過了字符的長度，說明，已經(jīng)遞歸到超過字符串的深度了，表明字符串不存在
    if (pos >= s.length() || children == null)
        return null;

    //如果剛好到了字符串最后一個，則只需要返回最后一個字符對應(yīng)的結(jié)點，若節(jié)點為空，則表明不存在該字符串
    else if (pos == s.length() - 1)
        return children.get(s.charAt(pos));

    //否則繼續(xù)遞歸查詢下去，直到?jīng)]有孩子節(jié)點了
    else {
        TrieNode n = children.get(s.charAt(pos));
        return n == null ? null : n.lookup(s, pos + 1);
    }
}

以上kookup方法返回值是一個TrieNode，要找某個字符串出現(xiàn)的次數(shù)，只需要看其中的n.occurances即可。
要看是否包含某個字符串，只需要看是否為空節(jié)點即可。

圖（Graph）是一種復(fù)雜的非線性結(jié)構(gòu)，在圖中，每個元素都可以有>=0個前驅(qū)，也可以有>=0個后繼，也就是說，元素之間的關(guān)系是任意的。其標(biāo)準(zhǔn)定義為：圖是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G(V,E)，其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合。

按照邊無方向和有方向分為無向圖（一般作為圖的代表）和有向圖，邊有權(quán)值就叫做加權(quán)圖，還有加權(quán)有向圖。圖的表示方法有：鄰接矩陣（VxV的布爾矩陣，很耗空間）、邊的數(shù)組（每個邊作為一個數(shù)組元素，實現(xiàn)起來需要檢查所有邊，耗時間）、鄰接表數(shù)組（一個頂點為索引的列表數(shù)組，一般是圖的最佳表示方法）。

圖的用處很廣，比如社交網(wǎng)絡(luò)、計算機網(wǎng)絡(luò)、CG中的可達(dá)性分析、任務(wù)調(diào)度、拓補排序等等。

圖的java實現(xiàn)完整代碼在這，下面是部分：

public class Graph {
    private static final String NEWLINE = System.getProperty("line.separator");

    private final int V;
    private int E;
    private Bag[] adj;
    
    public Graph(int V) {
        this.V = V;
        this.E = 0;
        adj = (Bag[]) new Bag[V];
        for (int v = 0; v < V; v++) {
            adj[v] = new Bag();
        }
    }
    
    public Graph(In in) {
        try {
            this.V = in.readInt();
            adj = (Bag[]) new Bag[V];
            for (int v = 0; v < V; v++) {
                adj[v] = new Bag();
            }
            int E = in.readInt();
            for (int i = 0; i < E; i++) {
                int v = in.readInt();
                int w = in.readInt();
                addEdge(v, w); 
            }
        }
        catch (NoSuchElementException e) {
            throw new IllegalArgumentException("invalid input format in Graph constructor", e);
        }
    }
    public void addEdge(int v, int w) {
        E++;
        adj[v].add(w);
        adj[w].add(v);
    }
    //返回頂點v的相鄰頂點
    public Iterable adj(int v) {
        return adj[v];
    }
}

public class DepthFirstSearch {
    private boolean[] marked;    // marked[v] = is there an s-v path?
    private int count;           // number of vertices connected to s

    public DepthFirstSearch(Graph G, int s) {
        marked = new boolean[G.V()];
        dfs(G, s);
    }

    // depth first search from v
    private void dfs(Graph G, int v) {
        count++;
        marked[v] = true;
        for (int w : G.adj(v)) {
            if (!marked[w]) {
                dfs(G, w);
            }
        }
    }
    
    public boolean marked(int v) { return marked[v]; }
    
    public int count() {   return count;   }
}

深度優(yōu)先可以獲得一個初始節(jié)點到另一個頂點的路徑，但是該路徑不一定是最短的（取決于圖的表示方法和遞歸設(shè)計），廣度優(yōu)先才能獲得最短路徑。

public class BreadthFirstPaths {
    private static final int INFINITY = Integer.MAX_VALUE;
    private boolean[] marked;  // marked[v] = is there an s-v path
    private int[] edgeTo;      // edgeTo[v] = previous edge on shortest s-v path
    private int[] distTo;      // distTo[v] = number of edges shortest s-v path

    public BreadthFirstPaths(Graph G, int s) {
        marked = new boolean[G.V()];
        distTo = new int[G.V()];
        edgeTo = new int[G.V()];
        validateVertex(s);
        bfs(G, s);

        assert check(G, s);
    }

    public BreadthFirstPaths(Graph G, Iterable sources) {
        marked = new boolean[G.V()];
        distTo = new int[G.V()];
        edgeTo = new int[G.V()];
        for (int v = 0; v < G.V(); v++)
            distTo[v] = INFINITY;
        validateVertices(sources);
        bfs(G, sources);
    }

    // breadth-first search from a single source
    private void bfs(Graph G, int s) {
        Queue q = new Queue();
        for (int v = 0; v < G.V(); v++)
            distTo[v] = INFINITY;
        distTo[s] = 0;
        marked[s] = true;
        q.enqueue(s);

        while (!q.isEmpty()) {
            int v = q.dequeue();
            for (int w : G.adj(v)) {
                if (!marked[w]) {
                    edgeTo[w] = v;
                    distTo[w] = distTo[v] + 1;
                    marked[w] = true;
                    q.enqueue(w);
                }
            }
        }
    }
    
    public Iterable pathTo(int v) {
        validateVertex(v);
        if (!hasPathTo(v)) return null;
        Stack path = new Stack();
        int x;
        for (x = v; distTo[x] != 0; x = edgeTo[x])
            path.push(x);
        path.push(x);
        return path;
    }
}

對于有向加權(quán)圖的單點最短路徑可以用Dijkstra算法。

樹是一個無環(huán)連通圖，最小生成樹是原圖的極小連通子圖，且包含原圖中的所有 n 個結(jié)點，并且有保持圖連通的最少的邊（如果是加權(quán)的就是權(quán)值之和最?。?。最小生成樹廣泛用于電路設(shè)計、航線規(guī)劃、電線規(guī)劃等領(lǐng)域。

以圖上的邊為出發(fā)點依據(jù)貪心策略逐次選擇圖中最小邊為最小生成樹的邊，且所選的當(dāng)前最小邊與已有的邊不構(gòu)成回路。
代碼在這。

從任意一個頂點開始，每次選擇一個與當(dāng)前頂點集最近的一個頂點，并將兩頂點之間的邊加入到樹中。Prim算法在找當(dāng)前最近頂點時使用到了貪心算法。
代碼在這。

紅黑樹深入剖析及Java實現(xiàn)
算法導(dǎo)論
算法第四版
紅黑樹 - 維基百科
紅黑樹(五)之 Java的實現(xiàn)
B樹、B-樹、B+樹、B*樹
B樹 - 維基百科
淺談算法和數(shù)據(jù)結(jié)構(gòu): 十 平衡查找樹之B樹
數(shù)據(jù)庫設(shè)計原理知識--B樹、B-樹、B+樹、B*樹都是什么
B+/-Tree原理及mysql的索引分析
跳躍表原理和實現(xiàn)
跳躍表（Skip list）原理與java實現(xiàn)
Trie樹詳解