[[377374]]

本文轉載自微信公眾號「淺羽的IT小屋」，作者淺羽Eric 。轉載本文請聯系淺羽的IT小屋公眾號。

這段時間在圈子里也認識了很多大佬們，從他們身上看到的是事業有成，感情幸福，還都很年輕。不禁感嘆，年輕人都這么有規劃，成為了別人眼中的人生贏家模樣。我覺得不要太在意與別人的橫向比較，更多的應該是與自己的縱向比較。因為普通人更多，我們都是在為工作、生活努力的那群人。這句話更多的是想送給一部分關注我號，目前比較焦慮的小伙伴，你要堅信只要努力，沒有辦不成的事。

今天給大家介紹的是常見的幾種數據結構，主要針對一些剛入門數據結構以及需要系統復習數據結構的小伙伴們!身為程序員的我們，每天都在和不同的數據打交道。那么你真的對數據結構一清二楚了么?

小羽從各數據結構的定義、特點、使用和方法實現來給大家進行介紹。每種都配有圖文進行詳解，幫助大家來更好地掌握對應知識。如果你對這個問題有困惑，快來看看~

棧 stack

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

存儲結構

隊列 queue

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

存儲結構

鏈表 Link

鏈表是一種數據結構，和數組同級。比如，Java 中我們使用的 ArrayList，其實現原理是數組。而LinkedList 的實現原理就是鏈表了。鏈表在進行循環遍歷時效率不高，但插入和刪除時優勢明顯。

存儲結構

散列表 Hash Table

散列表(Hash table，也叫哈希表)是一種查找算法，與鏈表、樹等算法不同的是，散列表算法在查找時不需要進行一系列和關鍵字(關鍵字是數據元素中某個數據項的值，用以標識一個數據元素)的比較操作。

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

用的構造散列函數的方法有：

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

數字分析法：數字分析法又稱數字選擇法，其方法是收集所有可能出現的鍵值，排列在一起，對鍵值的每一位進行分析，選擇分布較均勻若干位組成散列地址。

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

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

除留余數法：取關鍵字被某個不大于散列表表長 m 的數 p 除后所得的余數為散列地址，即：h(key) = key MOD p p ≤ m

隨機數法：選擇一個隨機函數，取關鍵字的隨機函數值為它的散列地址，即：h(key) = random(key)

用散列函數h將關鍵字映射到散列表中

排序二叉樹

首先如果普通二叉樹每個節點滿足：左子樹所有節點值小于它的根節點值，且右子樹所有節點值大于它的根節點值，則這樣的二叉樹就是排序二叉樹。

插入操作

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

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

刪除操作

刪除操作主要分為三種情況，即要刪除的節點無子節點，要刪除的節點只有一個子節點，要刪除的節點有兩個子節點。

1. 對于要刪除的節點無子節點可以直接刪除，即讓其父節點將該子節點置空即可。

2. 對于要刪除的節點只有一個子節點，則替換要刪除的節點為其子節點。

3. 對于要刪除的節點有兩個子節點，則首先找該節點的替換節點(即右子樹中最小的節點)，接著替換要刪除的節點為替換節點，然后刪除替換節點。

三種情況

查詢操作

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

紅黑樹

R-B Tree，全稱是 Red-Black Tree，又稱為“紅黑樹”，它一種特殊的二叉查找樹。紅黑樹的每個節點上都有存儲位表示節點的顏色，可以是紅(Red)或黑(Black)。

紅黑樹的特性

1. 每個節點或者是黑色，或者是紅色。

2. 根節點是黑色。

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

4. 從一個節點到該節點的子孫節點的所有路徑上包含相同數目的黑節點。

左旋

對 x 進行左旋，意味著，將“x 的右孩子”設為“x 的父親節點”;即，將 x 變成了一個左節點(x成了為 z 的左孩子)!。因此，左旋中的“左”，意味著“被旋轉的節點將變成一個左節點”。

左旋

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

節點左旋演示

右旋

對 x 進行右旋，意味著，將“x 的左孩子”設為“x 的父親節點”;即，將 x 變成了一個右節點(x成了為 y 的右孩子)!因此，右旋中的“右”，意味著“被旋轉的節點將變成一個右節點”。

右旋

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

添加

第一步: 將紅黑樹當作一顆二叉查找樹，將節點插入。

第二步：將插入的節點著色為"紅色"。根據被插入節點的父節點的情況，可以將"當節點 z 被著色為紅色節點，并插入二叉樹"劃分為三種情況來處理。

當被插入的節點是根節點時間，直接把此節點涂為黑色。

當被插入的節點的父節點是黑色，什么也不需要做。節點被插入后，仍然是紅黑樹。

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

3種情況(case)

第三步: 通過一系列的旋轉或著色等操作，使之重新成為一顆紅黑樹。

刪除

第一步：將紅黑樹當作一顆二叉查找樹，將節點刪除。

這和"刪除常規二叉查找樹中刪除節點的方法是一樣的"。分 3 種情況：

1. 被刪除節點沒有兒子，即為葉節點。那么，直接將該節點刪除就 OK 了。

2. 被刪除節點只有一個兒子。那么，直接刪除該節點，并用該節點的唯一子節點頂替它的位置。

3. 被刪除節點有兩個兒子。那么，先找出它的后繼節點;然后把“它的后繼節點的內容”復制給“該節點的內容”;之后，刪除“它的后繼節點”。

第二步：通過"旋轉和重新著色"等一系列來修正該樹，使之重新成為一棵紅黑樹。

因為"第一步"中刪除節點之后，可能會違背紅黑樹的特性。所以需要通過"旋轉和重新著色"來修正該樹，使之重新成為一棵紅黑樹。選擇重著色 3 種情況。

當 x 是“紅+黑”節點，直接把 x 設為黑色，結束。此時紅黑樹性質全部恢復。

當 x 是“黑+黑”節點，且 x 是根，什么都不做，結束。此時紅黑樹性質全部恢復。

當 x 是“黑+黑”節點，且 x 不是根，這種情況又可以劃分為 4 種子情況。這 4 種子情況如下表所示：

4種情況(case)

B-TREE

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

1. 樹中每個結點至多有 m 個孩子;

2. 除根結點和葉子結點外，其它每個結點至少有有 ceil(m / 2)個孩子;

3. 若根結點不是葉子結點，則至少有 2 個孩子(特殊情況：沒有孩子的根結點，即根結點為葉子結點，整棵樹只有一個根節點);

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

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

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

Pi 為指向子樹根的接點，且指針 P(i-1)指向子樹種所有結點的關鍵字均小于 Ki，但都大于 K(i-1)。

關鍵字的個數 n 必須滿足：ceil(m / 2)-1 <= n <= m-1

b-tree

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

1. 有 n 棵子樹的結點中含有 n 個關鍵字;(B-tree 是 n 棵子樹有 n-1 個關鍵字)

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

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

差異

位圖

位圖的原理就是用一個 bit 來標識一個數字是否存在，采用一個 bit 來存儲一個數據，所以這樣可以大大的節省空間。bitmap 是很常用的數據結構，比如用于 Bloom Filter 中;用于無重復整數的排序等等。bitmap 通?；跀到M來實現，數組中每個元素可以看成是一系列二進制數，所有元素組成更大的二進制集合。

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

數據為【5，1，7，15，0，4，6，10】，則存入這個結構中的情況為