[[377374]]

本文轉(zhuǎn)載自微信公眾號(hào)「淺羽的IT小屋」，作者淺羽Eric 。轉(zhuǎn)載本文請(qǐng)聯(lián)系淺羽的IT小屋公眾號(hào)。

這段時(shí)間在圈子里也認(rèn)識(shí)了很多大佬們，從他們身上看到的是事業(yè)有成，感情幸福，還都很年輕。不禁感嘆，年輕人都這么有規(guī)劃，成為了別人眼中的人生贏家模樣。我覺(jué)得不要太在意與別人的橫向比較，更多的應(yīng)該是與自己的縱向比較。因?yàn)槠胀ㄈ烁?，我們都是在為工作、生活努力的那群人。這句話(huà)更多的是想送給一部分關(guān)注我號(hào)，目前比較焦慮的小伙伴，你要堅(jiān)信只要努力，沒(méi)有辦不成的事。

今天給大家介紹的是常見(jiàn)的幾種數(shù)據(jù)結(jié)構(gòu)，主要針對(duì)一些剛?cè)腴T(mén)數(shù)據(jù)結(jié)構(gòu)以及需要系統(tǒng)復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)的小伙伴們!身為程序員的我們，每天都在和不同的數(shù)據(jù)打交道。那么你真的對(duì)數(shù)據(jù)結(jié)構(gòu)一清二楚了么?

小羽從各數(shù)據(jù)結(jié)構(gòu)的定義、特點(diǎn)、使用和方法實(shí)現(xiàn)來(lái)給大家進(jìn)行介紹。每種都配有圖文進(jìn)行詳解，幫助大家來(lái)更好地掌握對(duì)應(yīng)知識(shí)。如果你對(duì)這個(gè)問(wèn)題有困惑，快來(lái)看看~

棧 stack

棧(stack)是限制插入和刪除只能在一個(gè)位置上進(jìn)行的表，該位置是表的末端，叫做棧頂(top)。它是后進(jìn)先出(LIFO)的。對(duì)棧的基本操作只有 push(進(jìn)棧)和 pop(出棧)兩種，前者相當(dāng)于插入，后者相當(dāng)于刪除最后的元素。

存儲(chǔ)結(jié)構(gòu)

隊(duì)列 queue

隊(duì)列是一種特殊的線性表，特殊之處在于它只允許在表的前端(front)進(jìn)行刪除操作，而在表的后端(rear)進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱(chēng)為隊(duì)尾，進(jìn)行刪除操作的端稱(chēng)為隊(duì)頭。

存儲(chǔ)結(jié)構(gòu)

鏈表 Link

鏈表是一種數(shù)據(jù)結(jié)構(gòu)，和數(shù)組同級(jí)。比如，Java 中我們使用的 ArrayList，其實(shí)現(xiàn)原理是數(shù)組。而LinkedList 的實(shí)現(xiàn)原理就是鏈表了。鏈表在進(jìn)行循環(huán)遍歷時(shí)效率不高，但插入和刪除時(shí)優(yōu)勢(shì)明顯。

存儲(chǔ)結(jié)構(gòu)

散列表 Hash Table

散列表(Hash table，也叫哈希表)是一種查找算法，與鏈表、樹(shù)等算法不同的是，散列表算法在查找時(shí)不需要進(jìn)行一系列和關(guān)鍵字(關(guān)鍵字是數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值，用以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素)的比較操作。

散列表算法希望能盡量做到不經(jīng)過(guò)任何比較，通過(guò)一次存取就能得到所查找的數(shù)據(jù)元素，因而必須要在數(shù)據(jù)元素的存儲(chǔ)位置和它的關(guān)鍵字(可用 key 表示)之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系，使每個(gè)關(guān)鍵字和散列表中一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)。因此在查找時(shí)，只要根據(jù)這個(gè)對(duì)應(yīng)關(guān)系找到給定關(guān)鍵字在散列表中的位置即可。這種對(duì)應(yīng)關(guān)系被稱(chēng)為散列函數(shù)(可用 h(key)表示)。

用的構(gòu)造散列函數(shù)的方法有：

直接定址法：取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址。即：h(key) = key 或 h(key) = a * key + b，其中 a 和 b 為常數(shù)。

數(shù)字分析法：數(shù)字分析法又稱(chēng)數(shù)字選擇法，其方法是收集所有可能出現(xiàn)的鍵值，排列在一起，對(duì)鍵值的每一位進(jìn)行分析，選擇分布較均勻若干位組成散列地址。

平方取值法：取關(guān)鍵字平方后的中間幾位為散列地址。

折疊法：將關(guān)鍵字分割成位數(shù)相同的幾部分，然后取這幾部分的疊加和作為散列地址。

除留余數(shù)法：取關(guān)鍵字被某個(gè)不大于散列表表長(zhǎng) m 的數(shù) p 除后所得的余數(shù)為散列地址，即：h(key) = key MOD p p ≤ m

隨機(jī)數(shù)法：選擇一個(gè)隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的散列地址，即：h(key) = random(key)

用散列函數(shù)h將關(guān)鍵字映射到散列表中

排序二叉樹(shù)

首先如果普通二叉樹(shù)每個(gè)節(jié)點(diǎn)滿(mǎn)足：左子樹(shù)所有節(jié)點(diǎn)值小于它的根節(jié)點(diǎn)值，且右子樹(shù)所有節(jié)點(diǎn)值大于它的根節(jié)點(diǎn)值，則這樣的二叉樹(shù)就是排序二叉樹(shù)。

插入操作

首先要從根節(jié)點(diǎn)開(kāi)始往下找到自己要插入的位置(即新節(jié)點(diǎn)的父節(jié)點(diǎn));具體流程是：新節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)比較，如果相同則表示已經(jīng)存在且不能再重復(fù)插入;如果小于當(dāng)前節(jié)點(diǎn)，則到左子樹(shù)中尋找，如果左子樹(shù)為空則當(dāng)前節(jié)點(diǎn)為要找的父節(jié)點(diǎn)，新節(jié)點(diǎn)插入到當(dāng)前節(jié)點(diǎn)的左子樹(shù)即可;如果大于當(dāng)前節(jié)點(diǎn)，則到右子樹(shù)中尋找，如果右子樹(shù)為空則當(dāng)前節(jié)點(diǎn)為要找的父節(jié)點(diǎn)，新節(jié)點(diǎn)插入到當(dāng)前節(jié)點(diǎn)的右子樹(shù)即可。

從左到右，從下到上(7次插入操作)

刪除操作

刪除操作主要分為三種情況，即要?jiǎng)h除的節(jié)點(diǎn)無(wú)子節(jié)點(diǎn)，要?jiǎng)h除的節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)，要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)。

1. 對(duì)于要?jiǎng)h除的節(jié)點(diǎn)無(wú)子節(jié)點(diǎn)可以直接刪除，即讓其父節(jié)點(diǎn)將該子節(jié)點(diǎn)置空即可。

2. 對(duì)于要?jiǎng)h除的節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)，則替換要?jiǎng)h除的節(jié)點(diǎn)為其子節(jié)點(diǎn)。

3. 對(duì)于要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，則首先找該節(jié)點(diǎn)的替換節(jié)點(diǎn)(即右子樹(shù)中最小的節(jié)點(diǎn))，接著替換要?jiǎng)h除的節(jié)點(diǎn)為替換節(jié)點(diǎn)，然后刪除替換節(jié)點(diǎn)。

三種情況

查詢(xún)操作

查找操作的主要流程為：先和根節(jié)點(diǎn)比較，如果相同就返回，如果小于根節(jié)點(diǎn)則到左子樹(shù)中遞歸查找，如果大于根節(jié)點(diǎn)則到右子樹(shù)中遞歸查找。因此在排序二叉樹(shù)中可以很容易獲取最大(最右最深子節(jié)點(diǎn))和最小(最左最深子節(jié)點(diǎn))值。

紅黑樹(shù)

R-B Tree，全稱(chēng)是 Red-Black Tree，又稱(chēng)為“紅黑樹(shù)”，它一種特殊的二叉查找樹(shù)。紅黑樹(shù)的每個(gè)節(jié)點(diǎn)上都有存儲(chǔ)位表示節(jié)點(diǎn)的顏色，可以是紅(Red)或黑(Black)。

紅黑樹(shù)的特性

1. 每個(gè)節(jié)點(diǎn)或者是黑色，或者是紅色。

2. 根節(jié)點(diǎn)是黑色。

3. 每個(gè)葉子節(jié)點(diǎn)(NIL)是黑色。[注意：這里葉子節(jié)點(diǎn)，是指為空(NIL 或NULL)的葉子節(jié)點(diǎn)!] (4)如果一個(gè)節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的。

4. 從一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。

左旋

對(duì) x 進(jìn)行左旋，意味著，將“x 的右孩子”設(shè)為“x 的父親節(jié)點(diǎn)”;即，將 x 變成了一個(gè)左節(jié)點(diǎn)(x成了為 z 的左孩子)!。因此，左旋中的“左”，意味著“被旋轉(zhuǎn)的節(jié)點(diǎn)將變成一個(gè)左節(jié)點(diǎn)”。

左旋

LEFT-ROTATE(T, x)  
y ← right[x] // 前提：這里假設(shè) x 的右孩子為 y。下面開(kāi)始正式操作 
right[x] ← left[y] // 將 “y 的左孩子” 設(shè)為 “x 的右孩子”，即 將β設(shè)為 x 的右孩子 
p[left[y]] ← x // 將 “x” 設(shè)為 “y 的左孩子的父親”，即 將β的父親設(shè)為 x 
p[y] ← p[x] // 將 “x 的父親” 設(shè)為 “y 的父親” 
if p[x] = nil[T]  
then root[T] ← y // 情況 1：如果 “x 的父親” 是空節(jié)點(diǎn)，則將 y 設(shè)為根節(jié)點(diǎn) 
else if x = left[p[x]]  
 then left[p[x]] ← y // 情況 2：如果 x 是它父節(jié)點(diǎn)的左孩子，則將 y 設(shè)為“x 的父節(jié)點(diǎn) 
的左孩子” 
 else right[p[x]] ← y // 情況 3：(x 是它父節(jié)點(diǎn)的右孩子) 將 y 設(shè)為“x 的父節(jié)點(diǎn)的右孩 
子” 
left[y] ← x // 將 “x” 設(shè)為 “y 的左孩子” 
p[x] ← y // 將 “x 的父節(jié)點(diǎn)” 設(shè)為 “y 

節(jié)點(diǎn)左旋演示

右旋

對(duì) x 進(jìn)行右旋，意味著，將“x 的左孩子”設(shè)為“x 的父親節(jié)點(diǎn)”;即，將 x 變成了一個(gè)右節(jié)點(diǎn)(x成了為 y 的右孩子)!因此，右旋中的“右”，意味著“被旋轉(zhuǎn)的節(jié)點(diǎn)將變成一個(gè)右節(jié)點(diǎn)”。

右旋

RIGHT-ROTATE(T, y)  
x ← left[y] // 前提：這里假設(shè) y 的左孩子為 x。下面開(kāi)始正式操作 
left[y] ← right[x] // 將 “x 的右孩子” 設(shè)為 “y 的左孩子”，即 將β設(shè)為 y 的左孩子 
p[right[x]] ← y // 將 “y” 設(shè)為 “x 的右孩子的父親”，即 將β的父親設(shè)為 y 
p[x] ← p[y] // 將 “y 的父親” 設(shè)為 “x 的父親” 
if p[y] = nil[T]  
then root[T] ← x // 情況 1：如果 “y 的父親” 是空節(jié)點(diǎn)，則將 x 設(shè)為根節(jié)點(diǎn) 
else if y = right[p[y]]  
 then right[p[y]] ← x // 情況 2：如果 y 是它父節(jié)點(diǎn)的右孩子，則將 x 設(shè)為“y 的父節(jié) 
點(diǎn)的左孩子” 
 else left[p[y]] ← x // 情況 3：(y 是它父節(jié)點(diǎn)的左孩子) 將 x 設(shè)為“y 的父節(jié)點(diǎn)的左孩 
子” 
right[x] ← y // 將 “y” 設(shè)為 “x 的右孩子” 
p[y] ← x // 將 “y 的父節(jié)點(diǎn)” 設(shè)為 “x” 

添加

第一步: 將紅黑樹(shù)當(dāng)作一顆二叉查找樹(shù)，將節(jié)點(diǎn)插入。

第二步：將插入的節(jié)點(diǎn)著色為"紅色"。根據(jù)被插入節(jié)點(diǎn)的父節(jié)點(diǎn)的情況，可以將"當(dāng)節(jié)點(diǎn) z 被著色為紅色節(jié)點(diǎn)，并插入二叉樹(shù)"劃分為三種情況來(lái)處理。

當(dāng)被插入的節(jié)點(diǎn)是根節(jié)點(diǎn)時(shí)間，直接把此節(jié)點(diǎn)涂為黑色。

當(dāng)被插入的節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色，什么也不需要做。節(jié)點(diǎn)被插入后，仍然是紅黑樹(shù)。

當(dāng)被插入的節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色。這種情況下，被插入節(jié)點(diǎn)是一定存在非空祖父節(jié)點(diǎn)的;進(jìn)一步的講，被插入節(jié)點(diǎn)也一定存在叔叔節(jié)點(diǎn)(即使叔叔節(jié)點(diǎn)為空，我們也視之為存在，空節(jié)點(diǎn)本身就是黑色節(jié)點(diǎn))。理解這點(diǎn)之后，我們依據(jù)"叔叔節(jié)點(diǎn)的情況"，將這種情況進(jìn)一步劃分為 3 種情況(Case)。

3種情況(case)

第三步: 通過(guò)一系列的旋轉(zhuǎn)或著色等操作，使之重新成為一顆紅黑樹(shù)。

刪除

第一步：將紅黑樹(shù)當(dāng)作一顆二叉查找樹(shù)，將節(jié)點(diǎn)刪除。

這和"刪除常規(guī)二叉查找樹(shù)中刪除節(jié)點(diǎn)的方法是一樣的"。分 3 種情況：

1. 被刪除節(jié)點(diǎn)沒(méi)有兒子，即為葉節(jié)點(diǎn)。那么，直接將該節(jié)點(diǎn)刪除就 OK 了。

2. 被刪除節(jié)點(diǎn)只有一個(gè)兒子。那么，直接刪除該節(jié)點(diǎn)，并用該節(jié)點(diǎn)的唯一子節(jié)點(diǎn)頂替它的位置。

3. 被刪除節(jié)點(diǎn)有兩個(gè)兒子。那么，先找出它的后繼節(jié)點(diǎn);然后把“它的后繼節(jié)點(diǎn)的內(nèi)容”復(fù)制給“該節(jié)點(diǎn)的內(nèi)容”;之后，刪除“它的后繼節(jié)點(diǎn)”。

第二步：通過(guò)"旋轉(zhuǎn)和重新著色"等一系列來(lái)修正該樹(shù)，使之重新成為一棵紅黑樹(shù)。

因?yàn)?quot;第一步"中刪除節(jié)點(diǎn)之后，可能會(huì)違背紅黑樹(shù)的特性。所以需要通過(guò)"旋轉(zhuǎn)和重新著色"來(lái)修正該樹(shù)，使之重新成為一棵紅黑樹(shù)。選擇重著色 3 種情況。

當(dāng) x 是“紅+黑”節(jié)點(diǎn)，直接把 x 設(shè)為黑色，結(jié)束。此時(shí)紅黑樹(shù)性質(zhì)全部恢復(fù)。

當(dāng) x 是“黑+黑”節(jié)點(diǎn)，且 x 是根，什么都不做，結(jié)束。此時(shí)紅黑樹(shù)性質(zhì)全部恢復(fù)。

當(dāng) x 是“黑+黑”節(jié)點(diǎn)，且 x 不是根，這種情況又可以劃分為 4 種子情況。這 4 種子情況如下表所示：

4種情況(case)

B-TREE

B-tree 又叫平衡多路查找樹(shù)。一棵 m 階的 B-tree (m 叉樹(shù))的特性如下(其中 ceil(x)是一個(gè)取上限的函數(shù))：

1. 樹(shù)中每個(gè)結(jié)點(diǎn)至多有 m 個(gè)孩子;

2. 除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外，其它每個(gè)結(jié)點(diǎn)至少有有 ceil(m / 2)個(gè)孩子;

3. 若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有 2 個(gè)孩子(特殊情況：沒(méi)有孩子的根結(jié)點(diǎn)，即根結(jié)點(diǎn)為葉子結(jié)點(diǎn)，整棵樹(shù)只有一個(gè)根節(jié)點(diǎn));

4. 所有葉子結(jié)點(diǎn)都出現(xiàn)在同一層，葉子結(jié)點(diǎn)不包含任何關(guān)鍵字信息(可以看做是外部結(jié)點(diǎn)或查詢(xún)失敗的結(jié)點(diǎn)，實(shí)際上這些結(jié)點(diǎn)不存在，指向這些結(jié)點(diǎn)的指針都為 null);

5. 每個(gè)非終端結(jié)點(diǎn)中包含有 n 個(gè)關(guān)鍵字信息：(n，P0，K1，P1，K2，P2，……，Kn，Pn)。其中：

Ki (i=1…n)為關(guān)鍵字，且關(guān)鍵字按順序排序 K(i-1)< Ki。

Pi 為指向子樹(shù)根的接點(diǎn)，且指針 P(i-1)指向子樹(shù)種所有結(jié)點(diǎn)的關(guān)鍵字均小于 Ki，但都大于 K(i-1)。

關(guān)鍵字的個(gè)數(shù) n 必須滿(mǎn)足：ceil(m / 2)-1 <= n <= m-1

b-tree

一棵 m 階的 B+tree 和 m 階的 B-tree 的差異在于：

1. 有 n 棵子樹(shù)的結(jié)點(diǎn)中含有 n 個(gè)關(guān)鍵字;(B-tree 是 n 棵子樹(shù)有 n-1 個(gè)關(guān)鍵字)

2. 所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息，及指向含有這些關(guān)鍵字記錄的指針，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大的順序鏈接。(B-tree 的葉子節(jié)點(diǎn)并沒(méi)有包括全部需要查找的信息)

3. 所有的非終端結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中僅含有其子樹(shù)根結(jié)點(diǎn)中最大(或最小)關(guān)鍵字。(B-tree 的非終節(jié)點(diǎn)也包含需要查找的有效信息)

差異

位圖

位圖的原理就是用一個(gè) bit 來(lái)標(biāo)識(shí)一個(gè)數(shù)字是否存在，采用一個(gè) bit 來(lái)存儲(chǔ)一個(gè)數(shù)據(jù)，所以這樣可以大大的節(jié)省空間。bitmap 是很常用的數(shù)據(jù)結(jié)構(gòu)，比如用于 Bloom Filter 中;用于無(wú)重復(fù)整數(shù)的排序等等。bitmap 通?；跀?shù)組來(lái)實(shí)現(xiàn)，數(shù)組中每個(gè)元素可以看成是一系列二進(jìn)制數(shù)，所有元素組成更大的二進(jìn)制集合。

例如：unsigned int bit[N]，在這個(gè)數(shù)組里面，可以存儲(chǔ) N * sizeof(int) * 8個(gè)數(shù)據(jù)，但是最大的數(shù)只能是N * sizeof(int) * 8 - 1。假如，我們要存儲(chǔ)的數(shù)據(jù)范圍為0-15，則我們只需要使得N=1，這樣就可以把數(shù)據(jù)存進(jìn)去。如下圖：

數(shù)據(jù)為【5，1，7，15，0，4，6，10】，則存入這個(gè)結(jié)構(gòu)中的情況為