摘要：前文數據結構與算法常用數據結構及其實現總結了基本的數據結構，類似的，本文準備總結一下一些常見的高級的數據結構及其常見算法和對應的實現以及應用場景，務求理論與實踐一步到位。

前文 數據結構與算法——常用數據結構及其Java實現 總結了基本的數據結構，類似的，本文準備總結一下一些常見的高級的數據結構及其常見算法和對應的Java實現以及應用場景，務求理論與實踐一步到位。

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

性質：

由很多層結構組成；

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

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

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

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

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

全部代碼在此

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

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

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

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

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

節點是紅色或黑色。

根是黑色。

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

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

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

這些約束確保了紅黑樹的關鍵特性：從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。結果是這個樹大致上是平衡的（AVL樹平衡程度更高）。因為操作比如插入、刪除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同于普通的二叉查找樹。
要知道為什么這些性質確保了這個結果，注意到性質4導致了路徑不能有兩個毗連的紅色節點就足夠了。最短的可能路徑都是黑色節點，最長的可能路徑有交替的紅色和黑色節點。因為根據性質5所有最長的路徑都有相同數目的黑色節點，這就表明了沒有路徑能多于任何其他路徑的兩倍長。而且插入和刪除操作都只需要<=3次的節點旋轉操作，而AVL樹可能需要O(logn)次。正是因為這種時間上的保證，紅黑樹廣泛應用于 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;
}

查找：
因為每一個紅黑樹也是一個特殊的二叉查找樹，因此紅黑樹上的查找操作與普通二叉查找樹相同，可見上文，這里不再贅述。
然而，在紅黑樹上進行插入操作和刪除操作會導致不再匹配紅黑樹的性質。恢復紅黑樹的性質需要少量（logn）的顏色變更（實際是非常快速的）和不超過三次樹旋轉（對于插入操作是兩次）。雖然插入和刪除很復雜，但操作時間仍可以保持為O(logn)。

左、右旋：
左左情況對應右旋，右右情況對應左旋，同AVL樹，可見上文

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

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

1、D是新插入節點，將父節點和叔叔節點與祖父節點的顏色互換，然后D的祖父節點A變成了新插入節點，如果A的父節點是紅色則繼續調整

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

3、C是新插入節點，將C節點進行左旋，這樣就從 3 轉換成 2了，然后針對 2 進行操作處理就行了。2 操作做了一個右旋操作和顏色互換來達到目的。如果樹的結構是下圖的鏡像結構，則只需要將對應的左旋變成右旋，右旋變成左旋即可。

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

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

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

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

1、將兄弟節點提升到父節點，轉換之后就會變成后面的狀態 2，3，或者4了，從待刪除節點開始調整

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

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

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

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

全部代碼在此

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

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

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

根節點至少有兩個子節點

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

位于M-1和M key的子節點的值位于M-1 和M key對應的Value之間

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

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

有k個子結點的結點必然有k個關鍵碼

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

樹的所有葉結點構成一個有序鏈表，可以按照關鍵碼排序的次序遍歷全部記錄

更適合文件索引系統

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

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

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

B+Tree：非葉子節點只存key，大大滴減少了非葉子節點的大小，那么每個節點就可以存放更多的記錄，樹更矮了，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;
}

插入：

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

// 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);
}

刪除：

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

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

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

Trie樹的基本性質：

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

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

從根節點到某一個節點，路徑上經過的字符連接起來，為該節點對應的字符串。

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

例子：

add
adbc
bye

對應樹：

Java定義：

class TrieNode {
    char c;// 該節點的數據
    int occurances;//前節點所對應的字符串在字典樹里面出現的次數
    Map children;//當前節點的子節點，保存的是它的下一個節點的字符
}

插入：

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

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

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

為了統計每一個字符串出現的次數，應該在最后一個節點插入后occurances++，表示這個字符串出現的次數增加一次

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

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

    //獲取待插入字符的對應節點
    char c = s.charAt(pos);
    TrieNode n = children.get(c);
    if (n == null) {//當前待插入字符不存在于子節點中
        n = new TrieNode(c);//新創建一個節點
        children.put(c, n);//新建節點變為子節點
    }

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

刪除：

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

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

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

//待刪除的字符串s，以及當前待刪除的字符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;

    //遞歸出口是已經到了字符串的最后一個字符，若occurances=0，代表已經刪除了
    //否則繼續遞歸到最后一個字符
    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保存在葉子節點，意味著它雖然被標記著不存在了，但是還占著空間
    //所以必須刪除，但是如果“Harlan”刪除了，但是Trie里面還保存這“Harlan1994”,那么就不需要刪除字符了
    if (n.children == null && n.occurances == 0) {
        children.remove(n.c);
        if (children.size() == 0)
            children = null;
    }

    return ret;
}

求一個字符串出現的次數：

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

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

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

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

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

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

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

圖的用處很廣，比如社交網絡、計算機網絡、CG中的可達性分析、任務調度、拓補排序等等。

圖的java實現完整代碼在這，下面是部分：

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;   }
}

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

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;
    }
}

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

樹是一個無環連通圖，最小生成樹是原圖的極小連通子圖，且包含原圖中的所有 n 個結點，并且有保持圖連通的最少的邊（如果是加權的就是權值之和最小）。最小生成樹廣泛用于電路設計、航線規劃、電線規劃等領域。

以圖上的邊為出發點依據貪心策略逐次選擇圖中最小邊為最小生成樹的邊，且所選的當前最小邊與已有的邊不構成回路。
代碼在這。

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

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