數(shù)據(jù)結(jié)構(gòu)與算法——常用高級(jí)數(shù)據(jù)結(jié)構(gòu)及其Java實(shí)現(xiàn)

itvincent 發(fā)布于2019-08-15 14:33 / 1636人閱讀

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

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

跳躍表

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

性質(zhì)：

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

每一層都是一個(gè)有序的鏈表，排列順序?yàn)橛筛邔拥降讓?，都至少包含兩個(gè)鏈表節(jié)點(diǎn)，分別是前面的head節(jié)點(diǎn)和后面的nil節(jié)點(diǎn)；

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

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

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

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

全部代碼在此

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

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

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

紅黑樹

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

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

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

根是黑色。

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

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

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

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

Java定義：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

全部代碼在此

B樹相關(guān)

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

B-樹

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

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

根節(jié)點(diǎn)至少有兩個(gè)子節(jié)點(diǎn)

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

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

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

B+樹

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

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

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

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

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

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

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

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

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

針對(duì)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é)點(diǎn)溢出就要分裂該節(jié)點(diǎn)，并用處于中間的key提升并插入到父節(jié)點(diǎn)去，直到當(dāng)前插入節(jié)點(diǎn)不溢出為止。

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

B*樹

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

Trie樹

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

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

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

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

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

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

例子：

add
adbc
bye

對(duì)應(yīng)樹：

Java定義：

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

插入：

從頭到尾遍歷字符串的每一個(gè)字符

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

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

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

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

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

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

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

刪除：

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

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

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

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

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

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

    return ret;
}

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

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

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

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

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

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

圖

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

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

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

圖的java實(shí)現(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);
    }
    //返回頂點(diǎn)v的相鄰頂點(diǎn)
    public Iterable adj(int v) {
        return adj[v];
    }
}

深度優(yōu)先

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)先與單點(diǎn)最短路徑

深度優(yōu)先可以獲得一個(gè)初始節(jié)點(diǎn)到另一個(gè)頂點(diǎn)的路徑，但是該路徑不一定是最短的（取決于圖的表示方法和遞歸設(shè)計(jì)），廣度優(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;
    }
}

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

最小生成樹

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

kruskal算法

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

prim算法

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

參考與感謝

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

云服務(wù)器 GPU云服務(wù)器 java常用加密算法算法與數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法教程

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/68676.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

itvincent

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

JAVA學(xué)習(xí)筆記036-第一個(gè)簡(jiǎn)單的Mybatis程序（代碼經(jīng)驗(yàn)證）

閱讀 967·2021-11-17 09:33
從電子游戲到DevOps

閱讀 426·2019-08-30 11:16
css3 動(dòng)畫（三）animation 簡(jiǎn)介

閱讀 2480·2019-08-29 16:05
幾個(gè)CSS技巧的分享

閱讀 3364·2019-08-29 15:28
float與absolute脫離文檔流的區(qū)別

閱讀 1404·2019-08-29 11:29
react-router v4.x 源碼拾遺1

閱讀 1959·2019-08-26 13:51
講清楚之 javascript 參數(shù)傳值

閱讀 3398·2019-08-26 11:55
NPM酷庫(kù)：bluebird Promise工具庫(kù)

閱讀 1218·2019-08-26 11:31

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！

數(shù)據(jù)結(jié)構(gòu)與算法——常用高級(jí)數(shù)據(jù)結(jié)構(gòu)及其Java實(shí)現(xiàn)

相關(guān)文章

Java 高級(jí)面試知識(shí)點(diǎn)匯總！

高級(jí) Java 必須突破的 10 個(gè)知識(shí)點(diǎn)！

**學(xué)Java編程需要注意的地方**

***數(shù)據(jù)結(jié)構(gòu)與算法——常用排序算法及其Java實(shí)現(xiàn)***

發(fā)表評(píng)論

0條評(píng)論

itvincent

男|高級(jí)講師

TA的文章

JAVA學(xué)習(xí)筆記036-第一個(gè)簡(jiǎn)單的Mybatis程序（代碼經(jīng)驗(yàn)證）

從電子游戲到DevOps

css3 動(dòng)畫（三）animation 簡(jiǎn)介

幾個(gè)CSS技巧的分享

float與absolute脫離文檔流的區(qū)別

react-router v4.x 源碼拾遺1

講清楚之 javascript 參數(shù)傳值

NPM酷庫(kù)：bluebird Promise工具庫(kù)

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！

數(shù)據(jù)結(jié)構(gòu)與算法——常用高級(jí)數(shù)據(jù)結(jié)構(gòu)及其Java實(shí)現(xiàn)

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！