有人相愛,有人年少財(cái)務(wù)自由,有人數(shù)據(jù)結(jié)構(gòu)都背不出來
大家好，我是小羽。
這段時(shí)間在圈子里也認(rèn)識(shí)了很多大佬們，從他們身上看到的是事業(yè)有成，感情幸福，還都很年輕。不禁感嘆，年輕人都這么有規(guī)劃，成為了別人眼中的人生贏家模樣。我覺得不要太在意與別人的橫向比較，更多的應(yīng)該是與自己的縱向比較。因?yàn)?span style="color:rgb(62,62,62);font-family:'Helvetica Neue', Helvetica, 'Hiragino Sans GB', 'Microsoft YaHei', Arial, sans-serif;font-size:16px;">普通人更多，我們都是在為工作、生活努力的那群人。這句話更多的是想送給一部分關(guān)注我號(hào)，目前比較焦慮的小伙伴，你要堅(jiān)信只要努力，沒有辦不成的事。
今天給大家介紹的是常見的幾種數(shù)據(jù)結(jié)構(gòu)，主要針對(duì)一些剛?cè)腴T數(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)來給大家進(jìn)行介紹。每種都配有圖文進(jìn)行詳解，幫助大家來更好地掌握對(duì)應(yīng)知識(shí)。如果你對(duì)這個(gè)問題有困惑，快來看看~
棧?stack
棧（stack）是限制插入和刪除只能在一個(gè)位置上進(jìn)行的表，該位置是表的末端，叫做棧頂（top）。它是后進(jìn)先出（LIFO）的。對(duì)棧的基本操作只有 push（進(jìn)棧）和 pop（出棧）兩種，前者相當(dāng)于插入，后者相當(dāng)于刪除最后的元素。
隊(duì)列?queue
隊(duì)列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。
鏈表 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ì)明顯。
散列表 Hash Table
散列表（Hash table，也叫哈希表）是一種查找算法，與鏈表、樹等算法不同的是，散列表算法在查找時(shí)不需要進(jìn)行一系列和關(guān)鍵字（關(guān)鍵字是數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值，用以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素）的比較操作。
散列表算法希望能盡量做到不經(jīng)過任何比較，通過一次存取就能得到所查找的數(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)系被稱為散列函數(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ù)字分析法又稱數(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)
排序二叉樹
首先如果普通二叉樹每個(gè)節(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)與當(dāng)前節(jié)點(diǎn)比較，如果相同則表示已經(jīng)存在且不能再重復(fù)插入；如果小于當(dāng)前節(jié)點(diǎn)，則到左子樹中尋找，如果左子樹為空則當(dāng)前節(jié)點(diǎn)為要找的父節(jié)點(diǎn)，新節(jié)點(diǎn)插入到當(dāng)前節(jié)點(diǎn)的左子樹即可；如果大于當(dāng)前節(jié)點(diǎn)，則到右子樹中尋找，如果右子樹為空則當(dāng)前節(jié)點(diǎn)為要找的父節(jié)點(diǎn)，新節(jié)點(diǎn)插入到當(dāng)前節(jié)點(diǎn)的右子樹即可。
刪除操作
刪除操作主要分為三種情況，即要?jiǎng)h除的節(jié)點(diǎn)無子節(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)無子節(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)（即右子樹中最小的節(jié)點(diǎn)），接著替換要?jiǎng)h除的節(jié)點(diǎn)為替換節(jié)點(diǎn)，然后刪除替換節(jié)點(diǎn)。
查詢操作
查找操作的主要流程為：先和根節(jié)點(diǎn)比較，如果相同就返回，如果小于根節(jié)點(diǎn)則到左子樹中遞歸查找，如果大于根節(jié)點(diǎn)則到右子樹中遞歸查找。因此在排序二叉樹中可以很容易獲取最大（最右最深子節(jié)點(diǎn)）和最?。ㄗ钭笞钌钭庸?jié)點(diǎn)）值。
紅黑樹
R-B Tree，全稱是 Red-Black Tree，又稱為“紅黑樹”，它一種特殊的二叉查找樹。紅黑樹的每個(gè)節(jié)點(diǎn)上都有存儲(chǔ)位表示節(jié)點(diǎn)的顏色，可以是紅(Red)或黑(Black)。
紅黑樹的特性
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。下面開始正式操作right[x] ← left[y] // 將 “y 的左孩子” 設(shè)為 “x 的右孩子”，即 將β設(shè)為 x 的右孩子p[left[y]] ← x // 將 “x” 設(shè)為 “y 的左孩子的父親”，即 將β的父親設(shè)為 xp[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
右旋
對(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。下面開始正式操作left[y] ← right[x] // 將 “x 的右孩子” 設(shè)為 “y 的左孩子”，即 將β設(shè)為 y 的左孩子p[right[x]] ← y // 將 “y” 設(shè)為 “x 的右孩子的父親”，即 將β的父親設(shè)為 yp[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”
添加
第一步: 將紅黑樹當(dāng)作一顆二叉查找樹，將節(jié)點(diǎn)插入。
第二步：將插入的節(jié)點(diǎn)著色為"紅色"。根據(jù)被插入節(jié)點(diǎn)的父節(jié)點(diǎn)的情況，可以將"當(dāng)節(jié)點(diǎn) z 被著色為紅色節(jié)點(diǎn)，并插入二叉樹"劃分為三種情況來處理。
當(dāng)被插入的節(jié)點(diǎn)是根節(jié)點(diǎn)時(shí)間，直接把此節(jié)點(diǎn)涂為黑色。
當(dāng)被插入的節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色，什么也不需要做。節(jié)點(diǎn)被插入后，仍然是紅黑樹。
當(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)。
第三步: 通過一系列的旋轉(zhuǎn)或著色等操作，使之重新成為一顆紅黑樹。
刪除
第一步：將紅黑樹當(dāng)作一顆二叉查找樹，將節(jié)點(diǎn)刪除。
這和"刪除常規(guī)二叉查找樹中刪除節(jié)點(diǎn)的方法是一樣的"。分 3 種情況：
1.?被刪除節(jié)點(diǎn)沒有兒子，即為葉節(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)”。
第二步：通過"旋轉(zhuǎn)和重新著色"等一系列來修正該樹，使之重新成為一棵紅黑樹。
因?yàn)?第一步"中刪除節(jié)點(diǎn)之后，可能會(huì)違背紅黑樹的特性。所以需要通過"旋轉(zhuǎn)和重新著色"來修正該樹，使之重新成為一棵紅黑樹。選擇重著色 3 種情況。
當(dāng) x 是“紅+黑”節(jié)點(diǎn)，直接把 x 設(shè)為黑色，結(jié)束。此時(shí)紅黑樹性質(zhì)全部恢復(fù)。
當(dāng) x 是“黑+黑”節(jié)點(diǎn)，且 x 是根，什么都不做，結(jié)束。此時(shí)紅黑樹性質(zhì)全部恢復(fù)。
當(dāng) x 是“黑+黑”節(jié)點(diǎn)，且 x 不是根，這種情況又可以劃分為 4 種子情況。這 4 種子情況如下表所示：
B-TREE
B-tree 又叫平衡多路查找樹。一棵 m 階的 B-tree (m 叉樹)的特性如下（其中 ceil(x)是一個(gè)取上限的函數(shù)）：
1. 樹中每個(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è)孩子（特殊情況：沒有孩子的根結(jié)點(diǎn)，即根結(jié)點(diǎn)為葉子結(jié)點(diǎn)，整棵樹只有一個(gè)根節(jié)點(diǎn)）；
4. 所有葉子結(jié)點(diǎn)都出現(xiàn)在同一層，葉子結(jié)點(diǎn)不包含任何關(guān)鍵字信息(可以看做是外部結(jié)點(diǎ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 為指向子樹根的接點(diǎn)，且指針 P(i-1)指向子樹種所有結(jié)點(diǎn)的關(guān)鍵字均小于 Ki，但都大于 K(i-1)。
關(guān)鍵字的個(gè)數(shù) n 必須滿足：ceil(m / 2)-1 <= n <= m-1
一棵 m 階的 B+tree 和 m 階的 B-tree 的差異在于：
1. 有 n 棵子樹的結(jié)點(diǎn)中含有 n 個(gè)關(guān)鍵字；(B-tree 是 n 棵子樹有 n-1 個(gè)關(guān)鍵字)
2. 所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息，及指向含有這些關(guān)鍵字記錄的指針，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大的順序鏈接。(B-tree 的葉子節(jié)點(diǎn)并沒有包括全部需要查找的信息)
3. 所有的非終端結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中僅含有其子樹根結(jié)點(diǎn)中最大（或最?。╆P(guān)鍵字。(B-tree 的非終節(jié)點(diǎn)也包含需要查找的有效信息)
位圖
位圖的原理就是用一個(gè) bit 來標(biāo)識(shí)一個(gè)數(shù)字是否存在，采用一個(gè) bit 來存儲(chǔ)一個(gè)數(shù)據(jù)，所以這樣可以大大的節(jié)省空間。bitmap 是很常用的數(shù)據(jù)結(jié)構(gòu)，比如用于 Bloom Filter 中；用于無重復(fù)整數(shù)的排序等等。bitmap 通?；跀?shù)組來實(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)中的情況為
關(guān)于我
下面的是我的個(gè)人二維碼圖片，希望能跟大家一起進(jìn)階，共同進(jìn)步。
小羽也建立了一個(gè)技術(shù)群，如果你想了解到更多關(guān)于IT行業(yè)的技術(shù)以及生活中遇到的問題，歡迎小伙伴進(jìn)群交流，只需添加我好友，備注：進(jìn)群即可，期待你們的加入。
最近因?yàn)殡娔X出故障的原因，更文落下了。新電腦馬上就到了，會(huì)恢復(fù)到之前的更文頻率的，感謝大家一如既往的支持。
推薦閱讀
別小看 Log 日志，它難住了我們組的架構(gòu)師
講真，這份新年豪禮【面試錦囊】真舍不得給你們
圖文詳解：阿里寵兒【小兔】RabbitMQ的養(yǎng)成攻略
周末給女友講了遍加密算法，沒想到…