你學了這麼多年資料結構，到底有多少種樹，你知道嗎？
資料結構中有很多樹的結構，其中包括二叉樹、二叉搜尋樹、2-3樹、紅黑樹等等。本文中對資料結構中常見的幾種樹的概念和用途進行了彙總，不求嚴格精準，但求簡單易懂。
CSDN上釋出了《資料結構與演算法》專欄，這裡不能放連結，就只好給個ID了，
Charmve
（個人公眾號：邁微電子研發社）同時，很高興跟大家推薦自己錄製的《面向筆面試的資料結構與演算法精講》CSDN課程，公眾號內回覆“
課程
” 獲取連結。
一篇長文請耐心看，建議收藏！
資料結構中到底有多少種“樹”
1。 二叉樹
1。1 二叉樹的定義
1。2 二叉樹的示例
1。3 滿二叉樹和完全二叉樹
1。3。1 滿二叉樹
1。3。2 完全二叉樹
1。4 二叉樹的性質
2。 二叉查詢樹
3。 平衡二叉樹
3。1 平衡查詢樹之AVL樹
3。2 平衡二叉樹之紅黑樹
4。 B樹
4。1 什麼是B樹
4。2 B樹的性質
5。 B+樹
5。1 什麼是B+樹
5。2 B+的性質
6。 B*樹
7。 R樹
8。 Trie樹
8。1 什麼是Trie樹
8。2 Trie樹的三個基本性質
8。3 Tire樹的應用
1。 二叉樹
二叉樹是資料結構中一種重要的資料結構，也是樹表家族最為基礎的結構。
1。1 二叉樹的定義
二叉樹的每個結點至多隻有二棵子樹（不存在度大於2的結點），二叉樹的子樹有左右之分，次序不能顛倒。
二叉樹的第i層至多有2i-1個結點；
深度為k的二叉樹至多有2k-1個結點；
對任何一棵二叉樹T，如果其終端結點數為n_0n0，度為2的結點數為n_2n2，則n_0=n_2+1n0=n2+1。
注：二叉樹當中的結點只有度為0、1、2三種情況，度為0就是終端結點。構造二叉樹的過程就是從原始結點開始“生長”結點的過程，初始狀態下，原始結點就是終端結點，n0=1，n1=0，n2=0，每當一個原來的終端結點變成“1度結點”的時候只是把終端的位置向下移動了一點，n1++，不影響n0和n2，而每當一個原來的終端結點變成“2度結點”的時候，原來的終端消失，增加兩個終端，總效果就是n0++，n2++，所以二叉樹當中的n0和n2總是同步增加，即總是滿足n0=n2+1。
1。2 二叉樹的示例
1。3 滿二叉樹和完全二叉樹
1。3。1 滿二叉樹
除最後一層無任何子節點外，每一層上的所有結點都有兩個子結點。也可以這樣理解，除葉子結點外的所有結點均有兩個子結點。節點數達到最大值，所有葉子結點必須在同一層上。
滿二叉樹的性質：
一顆樹深度為h，最大層數為k，深度與最大層數相同，k=h；
葉子數為2h-1；
第k層的結點數是：2k-1；
總結點數是：2k-1，且總節點數一定是奇數。
1。3。2 完全二叉樹
若設二叉樹的深度為h，除第 h 層外，其它各層 （1～（h-1）層） 的結點數都達到最大個數，第h層所有的結點都連續集中在最左邊，這就是完全二叉樹。
注：
完全二叉樹是效率很高的資料結構，堆是一種完全二叉樹或者近似完全二叉樹，所以效率極高，像十分常用的排序演算法、Dijkstra演算法、Prim演算法等都要用堆才能最佳化，二叉排序樹的效率也要藉助平衡性來提高，而平衡性基於完全二叉樹。
1。4 二叉樹的性質
在非空二叉樹中，第i層的結點總數不超過2i-1， i>=1；
深度為h的二叉樹最多有2h-1個結點（h>=1），最少有h個結點；
對於任意一棵二叉樹，如果其葉結點數為N0，而度數為2的結點總數為N2，則N0=N2+1；
具有n個結點的完全二叉樹的深度為 log_2 ⌊n⌋+1log2⌊n⌋+1；
有N個結點的完全二叉樹各結點如果用順序方式儲存，則結點之間有如下關係：
給定N個節點，能構成h（N）種不同的二叉樹，其中h（N）為卡特蘭數的第N項，h（n）=C（2*n， n）/（n+1）h（n）=C（2∗n，n）/（n+1）。
設有i個枝點，I為所有枝點的道路長度總和，J為葉的道路長度總和J=I+2iJ=I+2i。
2。 二叉查詢樹
二叉查詢樹定義
：又稱為是二叉排序樹（Binary Sort Tree）或二叉搜尋樹。二叉排序樹或者是一棵空樹，或者是具有下列性質的二叉樹：
若左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；
若右子樹不空，則右子樹上所有結點的值均大於或等於它的根結點的值；
左、右子樹也分別為二叉排序樹；
沒有鍵值相等的節點。
二叉查詢樹的性質：
對二叉查詢樹進行中序遍歷，即可得到有序的數列。
二叉查詢樹的
時間複雜度
：它和二分查詢一樣，插入和查詢的時間複雜度均為O（logn），但是在最壞的情況下仍然會有O（n）的時間複雜度。原因在於插入和刪除元素的時候，樹沒有保持平衡（比如，我們查詢上圖（b）中的“93”，我們需要進行n次查詢操作）。我們追求的是在最壞的情況下仍然有較好的時間複雜度，這就是平衡查詢樹設計的初衷。
二叉查詢樹的高度決定了二叉查詢樹的查詢效率。
二叉查詢樹的插入
過程如下：
若當前的二叉查詢樹為空，則插入的元素為根節點；
若插入的元素值小於根節點值，則將元素插入到左子樹中；
若插入的元素值不小於根節點值，則將元素插入到右子樹中。
二叉查詢樹的刪除
，分三種情況進行處理：
p為葉子節點，直接刪除該節點，再修改其父節點的指標（注意分是根節點和不是根節點），如圖a；
p為單支節點（即只有左子樹或右子樹）。讓p的子樹與p的父親節點相連，刪除p即可（注意分是根節點和不是根節點），如圖b；
p的左子樹和右子樹均不空。找到p的後繼y，因為y一定沒有左子樹，所以可以刪除y，並讓y的父親節點成為y的右子樹的父親節點，並用y的值代替p的值；或者方法二是找到p的前驅x，x一定沒有右子樹，所以可以刪除x，並讓x的父親節點成為y的左子樹的父親節點。如圖c。
二叉樹相關實現原始碼：
插入操作：
struct node{ int val； pnode lchild； pnode rchild；}；pnode BT = NULL；//遞迴方法插入節點 pnode insert（pnode root， int x）{ if（root == NULL）{ pnode p = （pnode）malloc（LEN）； p->val = x； p->lchild = NULL； p->rchild = NULL； root = p； } else if（x < root->val）{ root->lchild = insert（root->lchild， x）； } else{ root->rchild = insert（root->rchild， x）； } return root；}//非遞迴方法插入節點 void insert_BST（pnode q， int x）{ pnode p = （pnode）malloc（LEN）； p->val = x； p->lchild = NULL； p->rchild = NULL； if（q == NULL）{ BT = p； return ； } while（q->lchild ！= p && q->rchild ！= p）{ if（x < q->val）{ if（q->lchild）{ q = q->lchild； } else{ q->lchild = p； } } else{ if（q->rchild）{ q = q->rchild； } else{ q->rchild = p； } } } return；}
刪除操作：
bool delete_BST（pnode p， int x） //返回一個標誌，表示是否找到被刪元素 { bool find = false； pnode q； p = BT； while（p && ！find）{ //尋找被刪元素 if（x == p->val）{ //找到被刪元素 find = true； } else if（x < p->val）{ //沿左子樹找 q = p； p = p->lchild； } else{ //沿右子樹找 q = p； p = p->rchild； } } if（p == NULL）{ //沒找到 cout << “沒有找到” << x << endl； } if（p->lchild == NULL && p->rchild == NULL）{ //p為葉子節點 if（p == BT）{ //p為根節點 BT = NULL； } else if（q->lchild == p）{ q->lchild = NULL； } else{ q->rchild = NULL； } free（p）； //釋放節點p } else if（p->lchild == NULL || p->rchild == NULL）{ //p為單支子樹 if（p == BT）{ //p為根節點 if（p->lchild == NULL）{ BT = p->rchild； } else{ BT = p->lchild； } } else{ if（q->lchild == p && p->lchild）{ //p是q的左子樹且p有左子樹 q->lchild = p->lchild； //將p的左子樹連結到q的左指標上 } else if（q->lchild == p && p->rchild）{ q->lchild = p->rchild； } else if（q->rchild == p && p->lchild）{ q->rchild = p->lchild； } else{ q->rchild = p->rchild； } } free（p）； } else{ //p的左右子樹均不為空 pnode t = p； pnode s = p->lchild； //從p的左子節點開始 while（s->rchild）{ //找到p的前驅，即p左子樹中值最大的節點 t = s； s = s->rchild； } p->val = s->val； //把節點s的值賦給p if（t == p）{ p->lchild = s->lchild； } else{ t->rchild = s->lchild； } free（s）； } return find；}
查詢操作：
pnode search_BST（pnode p， int x）{ bool solve = false； while（p && ！solve）{ if（x == p->val）{ solve = true； } else if（x < p->val）{ p = p->lchild； } else{ p = p->rchild； } } if（p == NULL）{ cout << “沒有找到” << x << endl； } return p；}
3。 平衡二叉樹
我們知道，對於一般的二叉搜尋樹（Binary Search Tree），其期望高度（即為一棵平衡樹時）為log2n，其各操作的時間複雜度O（log2n）同時也由此而決定。但是，在某些極端的情況下（如在插入的序列是有序的時），二叉搜尋樹將退化成近似鏈或鏈，此時，其操作的時間複雜度將退化成線性的，即O（n）。我們可以透過隨機化建立二叉搜尋樹來儘量的避免這種情況，但是在進行了多次的操作之後，由於在刪除時，我們總是選擇將待刪除節點的後繼代替它本身，這樣就會造成總是右邊的節點數目減少，以至於樹向左偏沉。這同時也會造成樹的平衡性受到破壞，提高它的操作的時間複雜度。於是就有了我們下邊介紹的平衡二叉樹。
平衡二叉樹定義
：平衡二叉樹（Balanced Binary Tree）又被稱為AVL樹（有別於AVL演算法），且具有以下性質：它是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。平衡二叉樹的常用演算法有紅黑樹、AVL樹等。在平衡二叉搜尋樹中，我們可以看到，其高度一般都良好地維持在O（log2n），大大降低了操作的時間複雜度。
最小二叉平衡樹的節點的公式如下：
F（n）=F（n-1）+F（n-2）+1F（n）=F（n−1）+F（n−2）+1
這個類似於一個遞迴的數列，可以參考Fibonacci數列，1是根節點，F（n-1）是左子樹的節點數量，F（n-2）是右子樹的節點數量。
3。1 平衡查詢樹之AVL樹
有關AVL樹的具體實現，可以參考
C小加
的部落格《一步一步寫平衡二叉樹（AVL）》。
AVL樹定義
：AVL樹是最先發明的自平衡二叉查詢樹。AVL樹得名於它的發明者 G。M。 Adelson-Velsky 和 E。M。 Landis，他們在 1962 年的論文 “An algorithm for the organization of information” 中發表了它。在AVL中任何節點的兩個兒子子樹的高度最大差別為1，所以它也被稱為高度平衡樹，n個結點的AVL樹最大深度約1。44log2n。查詢、插入和刪除在平均和最壞情況下都是O（logn）。增加和刪除可能需要透過一次或多次樹旋轉來重新平衡這個樹。
這個方案很好的解決了二叉查詢樹退化成連結串列的問題，把插入，查詢，刪除的時間複雜度最好情況和最壞情況都維持在O(logN)。但是頻繁旋轉會使插入和刪除犧牲掉O(logN)左右的時間，不過相對二叉查詢樹來說，時間上穩定了很多。
AVL樹的自平衡操作——旋轉
：
AVL樹最關鍵的也是最難的一步操作就是
旋轉
。旋轉主要是為了實現AVL樹在實施了插入和刪除操作以後，樹重新回到平衡的方法。下面我們重點研究一下AVL樹的旋轉。
對於一個平衡的節點，由於任意節點最多有兩個兒子，因此高度不平衡時，此節點的兩顆子樹的高度差2。容易看出，這種不平衡出現在下面四種情況：
6節點的左子樹3節點高度比右子樹7節點大2，左子樹3節點的左子樹1節點高度大於右子樹4節點，這種情況成為左左。
6節點的左子樹2節點高度比右子樹7節點大2，左子樹2節點的左子樹1節點高度小於右子樹4節點，這種情況成為左右。
2節點的左子樹1節點高度比右子樹5節點小2，右子樹5節點的左子樹3節點高度大於右子樹6節點，這種情況成為右左。
2節點的左子樹1節點高度比右子樹4節點小2，右子樹4節點的左子樹3節點高度小於右子樹6節點，這種情況成為右右。
從圖2中可以可以看出，1和4兩種情況是對稱的，這兩種情況的旋轉演算法是一致的，只需要經過一次旋轉就可以達到目標，我們稱之為單旋轉。2和3兩種情況也是對稱的，這兩種情況的旋轉演算法也是一致的，需要進行兩次旋轉，我們稱之為雙旋轉。
單旋轉
單旋轉是針對於左左和右右這兩種情況的解決方案，這兩種情況是對稱的，只要解決了左左這種情況，右右就很好辦了。圖3是左左情況的解決方案，節點k2不滿足平衡特性，因為它的左子樹k1比右子樹Z深2層，而且k1子樹中，更深的一層的是k1的左子樹X子樹，所以屬於左左情況。
為使樹恢復平衡，我們把k2變成這棵樹的根節點，因為k2大於k1，把k2置於k1的右子樹上，而原本在k1右子樹的Y大於k1，小於k2，就把Y置於k2的左子樹上，這樣既滿足了二叉查詢樹的性質，又滿足了平衡二叉樹的性質。
這樣的操作只需要一部分指標改變，結果我們得到另外一顆二叉查詢樹，它是一棵AVL樹，因為X向上一移動了一層，Y還停留在原來的層面上，Z向下移動了一層。整棵樹的新高度和之前沒有在左子樹上插入的高度相同，插入操作使得X高度長高了。因此，由於這顆子樹高度沒有變化，所以通往根節點的路徑就不需要繼續旋轉了。
雙旋轉
對於左右和右左這兩種情況，單旋轉不能使它達到一個平衡狀態，要經過兩次旋轉。雙旋轉是針對於這兩種情況的解決方案，同樣的，這樣兩種情況也是對稱的，只要解決了左右這種情況，右左就很好辦了。圖4是左右情況的解決方案，節點k3不滿足平衡特性，因為它的左子樹k1比右子樹Z深2層，而且k1子樹中，更深的一層的是k1的右子樹k2子樹，所以屬於左右情況。
為使樹恢復平衡，我們需要進行兩步，第一步，把k1作為根，進行一次右右旋轉，旋轉之後就變成了左左情況，所以第二步再進行一次左左旋轉，最後得到了一棵以k2為根的平衡二叉樹。
AVL樹實現原始碼：
//AVL樹節點資訊template
3。2 平衡二叉樹之紅黑樹
紅黑樹的定義
：紅黑樹是一種自平衡二叉查詢樹，是在計算機科學中用到的一種資料結構，典型的用途是實現關聯陣列。它是在1972年由魯道夫·貝爾發明的，稱之為“對稱二叉B樹”，它現代的名字是在 Leo J。 Guibas 和 Robert Sedgewick 於1978年寫的一篇論文中獲得的。
它是複雜的，但它的操作有著良好的最壞情況執行時間，並且在實踐中是高效的: 它可以在O(logn)時間內做查詢，插入和刪除，這裡的n是樹中元素的數目。
紅黑樹和AVL樹一樣都對插入時間、刪除時間和查詢時間提供了最好可能的最壞情況擔保。這不只是使它們在時間敏感的應用如實時應用（real time application）中有價值，而且使它們有在提供最壞情況擔保的其他資料結構中作為建造板塊的價值；例如，在計算幾何中使用的很多資料結構都可以基於紅黑樹。此外，紅黑樹還是2-3-4樹的一種等同，它們的思想是一樣的，只不過紅黑樹是2-3-4樹用二叉樹的形式表示的。
紅黑樹的性質
：
紅黑樹是每個節點都帶有顏色屬性的二叉查詢樹，顏色為紅色或黑色。在二叉查詢樹強制的一般要求以外，對於任何有效的紅黑樹我們增加了如下的額外要求：
性質1。 節點是紅色或黑色。
性質2。 根是黑色。
性質3。 所有葉子都是黑色（葉子是NIL節點）。
性質4。 每個紅色節點必須有兩個黑色的子節點。（從每個葉子到根的所有路徑上不能有兩個連續的紅色節點。）
性質5。 從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點。
下面是一個具體的紅黑樹的圖例：
An example of a red-black tree
這些約束確保了紅黑樹的關鍵特性： 從根到葉子的最長的可能路徑不多於最短的可能路徑的兩倍長。結果是這個樹大致上是平衡的。因為操作比如插入、刪除和查詢某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同於普通的二叉查詢樹。
要知道為什麼這些性質確保了這個結果，注意到性質4導致了路徑不能有兩個毗連的紅色節點就足夠了。最短的可能路徑都是黑色節點，最長的可能路徑有交替的紅色和黑色節點。因為根據性質5所有最長的路徑都有相同數目的黑色節點，這就表明了沒有路徑能多於任何其他路徑的兩倍長。
以下內容整理自wiki百科之紅黑樹。
紅黑樹的自平衡操作：
因為每一個紅黑樹也是一個特化的二叉查詢樹，因此紅黑樹上的只讀操作與普通二叉查詢樹上的只讀操作相同。然而，在紅黑樹上進行插入操作和刪除操作會導致不再符合紅黑樹的性質。恢復紅黑樹的性質需要少量（O（logn））的顏色變更（實際是非常快速的）和不超過三次樹旋轉（對於插入操作是兩次）。雖然插入和刪除很複雜，但操作時間仍可以保持為O（logn） 次。
我們首先以二叉查詢樹的方法增加節點並標記它為紅色。如果設為黑色，就會導致根到葉子的路徑上有一條路上，多一個額外的黑節點，這個是很難調整的（違背性質5）
。但是設為紅色節點後，可能會導致出現兩個連續紅色節點的衝突，那麼可以透過顏色調換（color flips）和樹旋轉來調整。下面要進行什麼操作取決於其他臨近節點的顏色。同人類的家族樹中一樣，我們將使用術語叔父節點來指一個節點的父節點的兄弟節點。注意：
性質1和性質3總是保持著。
性質4只在增加紅色節點、重繪黑色節點為紅色，或做旋轉時受到威脅。
性質5只在增加黑色節點、重繪紅色節點為黑色，或做旋轉時受到威脅。
插入操作：
假設，將要插入的節點標為
N
，N的父節點標為
P
，N的祖父節點標為
G
，N的叔父節點標為
U
。在圖中展示的任何顏色要麼是由它所處情形這些所作的假定，要麼是假定所暗含的。
情形1
： 該樹為空樹，直接插入根結點的位置，違反性質1，把節點顏色有紅改為黑即可。
情形2
： 插入節點N的父節點P為黑色，不違反任何性質，無需做任何修改。在這種情形下，樹仍是有效的。性質5也未受到威脅，儘管新節點N有兩個黑色葉子子節點；但由於新節點N是紅色，透過它的每個子節點的路徑就都有同透過它所取代的黑色的葉子的路徑同樣數目的黑色節點，所以依然滿足這個性質。
注： 情形1很簡單，情形2中P為黑色，一切安然無事，但P為紅就不一樣了，下邊是P為紅的各種情況，也是真正難懂的地方。
情形3
： 如果父節點P和叔父節點U二者都是紅色，（此時新插入節點N做為P的左子節點或右子節點都屬於情形3，這裡右圖僅顯示N做為P左子的情形）則我們可以將它們兩個重繪為黑色並重繪祖父節點G為紅色（用來保持性質4）。現在我們的新節點N有了一個黑色的父節點P。因為透過父節點P或叔父節點U的任何路徑都必定透過祖父節點G，在這些路徑上的黑節點數目沒有改變。但是，紅色的祖父節點G的父節點也有可能是紅色的，這就違反了性質4。為了解決這個問題，我們在祖父節點G上遞迴地進行上述情形的整個過程（把G當成是新加入的節點進行各種情形的檢查）。比如，G為根節點，那我們就直接將G變為黑色（情形1）；如果G不是根節點，而它的父節點為黑色，那符合所有的性質，直接插入即可（情形2）；如果G不是根節點，而它的父節點為紅色，則遞迴上述過程（情形3）。
情形4
： 父節點P是紅色而叔父節點U是黑色或缺少，新節點N是其父節點的左子節點，而父節點P又是其父節點G的左子節點。在這種情形下，我們進行針對祖父節點G的一次右旋轉； 在旋轉產生的樹中，以前的父節點P現在是新節點N和以前的祖父節點G的父節點。我們知道以前的祖父節點G是黑色，否則父節點P就不可能是紅色（如果P和G都是紅色就違反了性質4，所以G必須是黑色）。我們切換以前的父節點P和祖父節點G的顏色，結果的樹滿足性質4。性質5也仍然保持滿足，因為透過這三個節點中任何一個的所有路徑以前都透過祖父節點G，現在它們都透過以前的父節點P。在各自的情形下，這都是三個節點中唯一的黑色節點。
情形5
： 父節點P是紅色而叔父節點U是黑色或缺少，並且新節點N是其父節點P的右子節點而父節點P又是其父節點的左子節點。在這種情形下，我們進行一次
左旋轉
調換新節點和其父節點的角色； 接著，我們按情形4處理以前的父節點P以解決仍然失效的性質4。注意這個改變會導致某些路徑透過它們以前不透過的新節點N（比如圖中1號葉子節點）或不透過節點P（比如圖中3號葉子節點），但由於這兩個節點都是紅色的，所以性質5仍有效。
注： 插入實際上是原地演算法，因為上述所有呼叫都使用了尾部遞迴。
刪除操作：
如果需要刪除的節點有兩個兒子，那麼問題可以被轉化成刪除另一個只有一個兒子的節點的問題。
對於二叉查詢樹，在刪除帶有兩個非葉子兒子的節點的時候，我們找到要麼在它的左子樹中的最大元素、要麼在它的右子樹中的最小元素，並把它的值轉移到要刪除的節點中。我們接著刪除我們從中複製出值的那個節點，它必定有少於兩個非葉子的兒子。因為只是複製了一個值，不違反任何性質，這就把問題簡化為如何刪除最多有一個兒子的節點的問題。它不關心這個節點是最初要刪除的節點還是我們從中複製出值的那個節點。
我們只需要討論刪除只有一個兒子的節點(如果它兩個兒子都為空，
即均為葉子，我們任意將其中一個看作它的兒子）。如果我們刪除一個紅色節點（此時該節點的兒子將都為葉子節點），它的父親和兒子一定是黑色的。所以我們可以簡單的用它的黑色兒子替換它，並不會破壞性質3和性質4。透過被刪除節點的所有路徑只是少了一個紅色節點，這樣可以繼續保證性質5。另一種簡單情況是在被刪除節點是黑色而它的兒子是紅色的時候。如果只是去除這個黑色節點，用它的紅色兒子頂替上來的話，會破壞性質5，但是如果我們重繪它的兒子為黑色，則曾經透過它的所有路徑將透過它的黑色兒子，這樣可以繼續保持性質5。
需要進一步討論的是在要刪除的節點和它的兒子二者都是黑色的時候，
這是一種複雜的情況。我們首先把要刪除的節點替換為它的兒子。出於方便，稱呼這個兒子為N（在新的位置上），稱呼它的兄弟（它父親的另一個兒子）為S。在下面的示意圖中，我們還是使用P稱呼N的父親，SL稱呼S的左兒子，SR稱呼S的右兒子。
如果N和它初始的父親是黑色，則刪除它的父親導致透過N的路徑都比不透過它的路徑少了一個黑色節點。因為這違反了性質5，樹需要被重新平衡。有幾種情形需要考慮：
情形1
： N是新的根。在這種情形下，我們就做完了。我們從所有路徑去除了一個黑色節點，而新根是黑色的，所以性質都保持著。
注意： 在情形2、5和6下，我們假定N是它父親的左兒子。如果它是右兒子，則在這些情形下的左和右應當對調。
情形2
： S是紅色。在這種情形下我們在N的父親上做左旋轉，把紅色兄弟轉換成N的祖父，我們接著對調N的父親和祖父的顏色。完成這兩個操作後，儘管所有路徑上黑色節點的數目沒有改變，但現在N有了一個黑色的兄弟和一個紅色的父親（它的新兄弟是黑色因為它是紅色S的一個兒子），所以我們可以接下去按
情形4
、
情形5
或情形6來處理。
情形2 示意圖
情形3
： N的父親、S和S的兒子都是黑色的。在這種情形下，我們簡單的重繪S為紅色。結果是透過S的所有路徑，它們就是以前不透過N的那些路徑，都少了一個黑色節點。因為刪除N的初始的父親使透過N的所有路徑少了一個黑色節點，這使事情都平衡了起來。但是，透過P的所有路徑現在比不透過P的路徑少了一個黑色節點，所以仍然違反性質5。要修正這個問題，我們要從情形1開始，在P上做重新平衡處理。
情形3 示意圖
情形4
： S和S的兒子都是黑色，但是N的父親是紅色。在這種情形下，我們簡單的交換N的兄弟和父親的顏色。這不影響不透過N的路徑的黑色節點的數目，但是它在透過N的路徑上對黑色節點數目增加了一，添補了在這些路徑上刪除的黑色節點。
情形4 示意圖
情形5
： S是黑色，S的左兒子是紅色，S的右兒子是黑色，而N是它父親的左兒子。在這種情形下我們在S上做右旋轉，這樣S的左兒子成為S的父親和N的新兄弟。我們接著交換S和它的新父親的顏色。所有路徑仍有同樣數目的黑色節點，但是現在N有了一個黑色兄弟，他的右兒子是紅色的，所以我們進入了情形6。N和它的父親都不受這個變換的影響。
情形5 示意圖
情形6
： S是黑色，S的右兒子是紅色，而N是它父親的左兒子。在這種情形下我們在N的父親上做左旋轉，這樣S成為N的父親（P）和S的右兒子的父親。我們接著交換N的父親和S的顏色，並使S的右兒子為黑色。子樹在它的根上的仍是同樣的顏色，所以性質3沒有被違反。但是，N現在增加了一個黑色祖先： 要麼N的父親變成黑色，要麼它是黑色而S被增加為一個黑色祖父。所以，透過N的路徑都增加了一個黑色節點。
此時，如果一個路徑不透過N，則有兩種可能性：
它透過N的新兄弟。那麼它以前和現在都必定透過S和N的父親，而它們只是交換了顏色。所以路徑保持了同樣數目的黑色節點。
它透過N的新叔父，S的右兒子。那麼它以前透過S、S的父親和S的右兒子，但是現在只通過S，它被假定為它以前的父親的顏色，和S的右兒子，它被從紅色改變為黑色。合成效果是這個路徑通過了同樣數目的黑色節點。
在任何情況下，在這些路徑上的黑色節點數目都沒有改變。所以我們恢復了性質4。在示意圖中的白色節點可以是紅色或黑色，但是在變換前後都必須指定相同的顏色。
情形6 示意圖
紅黑樹實現原始碼：
#define BLACK 1#define RED 0using namespace std；class bst {private： struct Node { int value； bool color； Node *leftTree， *rightTree， *parent； Node（） { color = RED； leftTree = NULL； rightTree = NULL； parent = NULL； value = 0； } Node* grandparent（） { if （parent == NULL） { return NULL； } return parent->parent； } Node* uncle（） { if （grandparent（） == NULL） { return NULL； } if （parent == grandparent（）->rightTree） return grandparent（）->leftTree； else return grandparent（）->rightTree； } Node* sibling（） { if （parent->leftTree == this） return parent->rightTree； else return parent->leftTree； } }； void rotate_right（Node *p） { Node *gp = p->grandparent（）； Node *fa = p->parent； Node *y = p->rightTree； fa->leftTree = y； if （y ！= NIL） y->parent = fa； p->rightTree = fa； fa->parent = p； if （root == fa） root = p； p->parent = gp； if （gp ！= NULL） { if （gp->leftTree == fa） gp->leftTree = p； else gp->rightTree = p； } } void rotate_left（Node *p） { if （p->parent == NULL） { root = p； return； } Node *gp = p->grandparent（）； Node *fa = p->parent； Node *y = p->leftTree； fa->rightTree = y； if （y ！= NIL） y->parent = fa； p->leftTree = fa； fa->parent = p； if （root == fa） root = p； p->parent = gp； if （gp ！= NULL） { if （gp->leftTree == fa） gp->leftTree = p； else gp->rightTree = p； } } void inorder（Node *p） { if （p == NIL） return； if （p->leftTree） inorder（p->leftTree）； cout << p->value << “ ”； if （p->rightTree） inorder（p->rightTree）； } string outputColor（bool color） { return color ？ “BLACK” ： “RED”； } Node* getSmallestChild（Node *p） { if （p->leftTree == NIL） return p； return getSmallestChild（p->leftTree）； } bool delete_child（Node *p， int data） { if （p->value > data） { if （p->leftTree == NIL） { return false； } return delete_child（p->leftTree， data）； } else if （p->value < data） { if （p->rightTree == NIL） { return false； } return delete_child（p->rightTree， data）； } else if （p->value == data） { if （p->rightTree == NIL） { delete_one_child（p）； return true； } Node *smallest = getSmallestChild（p->rightTree）； swap（p->value， smallest->value）； delete_one_child（smallest）； return true； } } void delete_one_child（Node *p） { Node *child = p->leftTree == NIL ？ p->rightTree ： p->leftTree； if （p->parent == NULL && p->leftTree == NIL && p->rightTree == NIL） { p = NULL； root = p； return； } if （p->parent == NULL） { delete p； child->parent = NULL； root = child； root->color = BLACK； return； } if （p->parent->leftTree == p） { p->parent->leftTree = child； } else { p->parent->rightTree = child； } child->parent = p->parent； if （p->color == BLACK） { if （child->color == RED） { child->color = BLACK； } else delete_case（child）； } delete p； } void delete_case（Node *p） { if （p->parent == NULL） { p->color = BLACK； return； } if （p->sibling（）->color == RED） { p->parent->color = RED； p->sibling（）->color = BLACK； if （p == p->parent->leftTree） rotate_left（p->sibling（））； else rotate_right（p->sibling（））； } if （p->parent->color == BLACK && p->sibling（）->color == BLACK && p->sibling（）->leftTree->color == BLACK && p->sibling（）->rightTree->color == BLACK） { p->sibling（）->color = RED； delete_case（p->parent）； } else if （p->parent->color == RED && p->sibling（）->color == BLACK && p->sibling（）->leftTree->color == BLACK && p->sibling（）->rightTree->color == BLACK） { p->sibling（）->color = RED； p->parent->color = BLACK； } else { if （p->sibling（）->color == BLACK） { if （p == p->parent->leftTree && p->sibling（）->leftTree->color == RED && p->sibling（）->rightTree->color == BLACK） { p->sibling（）->color = RED； p->sibling（）->leftTree->color = BLACK； rotate_right（p->sibling（）->leftTree）； } else if （p == p->parent->rightTree && p->sibling（）->leftTree->color == BLACK && p->sibling（）->rightTree->color == RED） { p->sibling（）->color = RED； p->sibling（）->rightTree->color = BLACK； rotate_left（p->sibling（）->rightTree）； } } p->sibling（）->color = p->parent->color； p->parent->color = BLACK； if （p == p->parent->leftTree） { p->sibling（）->rightTree->color = BLACK； rotate_left（p->sibling（））； } else { p->sibling（）->leftTree->color = BLACK； rotate_right（p->sibling（））； } } } void insert（Node *p， int data） { if （p->value >= data） { if （p->leftTree ！= NIL） insert（p->leftTree， data）； else { Node *tmp = new Node（）； tmp->value = data； tmp->leftTree = tmp->rightTree = NIL； tmp->parent = p； p->leftTree = tmp； insert_case（tmp）； } } else { if （p->rightTree ！= NIL） insert（p->rightTree， data）； else { Node *tmp = new Node（）； tmp->value = data； tmp->leftTree = tmp->rightTree = NIL； tmp->parent = p； p->rightTree = tmp； insert_case（tmp）； } } } void insert_case（Node *p） { if （p->parent == NULL） { root = p； p->color = BLACK； return； } if （p->parent->color == RED） { if （p->uncle（）->color == RED） { p->parent->color = p->uncle（）->color = BLACK； p->grandparent（）->color = RED； insert_case（p->grandparent（））； } else { if （p->parent->rightTree == p && p->grandparent（）->leftTree == p->parent） { rotate_left（p）； rotate_right（p）； p->color = BLACK； p->leftTree->color = p->rightTree->color = RED； } else if （p->parent->leftTree == p && p->grandparent（）->rightTree == p->parent） { rotate_right（p）； rotate_left（p）； p->color = BLACK； p->leftTree->color = p->rightTree->color = RED； } else if （p->parent->leftTree == p && p->grandparent（）->leftTree == p->parent） { p->parent->color = BLACK； p->grandparent（）->color = RED； rotate_right（p->parent）； } else if （p->parent->rightTree == p && p->grandparent（）->rightTree == p->parent） { p->parent->color = BLACK； p->grandparent（）->color = RED； rotate_left（p->parent）； } } } } void DeleteTree（Node *p） { if （！p || p == NIL） { return； } DeleteTree（p->leftTree）； DeleteTree（p->rightTree）； delete p； }public： bst（） { NIL = new Node（）； NIL->color = BLACK； root = NULL； } ~bst（） { if （root） DeleteTree（root）； delete NIL； } void inorder（） { if （root == NULL） return； inorder（root）； cout << endl； } void insert（int x） { if （root == NULL） { root = new Node（）； root->color = BLACK； root->leftTree = root->rightTree = NIL； root->value = x； } else { insert（root， x）； } } bool delete_value（int data） { return delete_child（root， data）； }private： Node *root， *NIL；}；
4。 B樹
B樹也是一種用於查詢的平衡樹，但是它不是二叉樹。
4。1 什麼是B樹
B樹（B-tree）是一種樹狀資料結構，能夠用來儲存排序後的資料。這種資料結構能夠讓查詢資料、循序存取、插入資料及刪除的動作，都在對數時間內完成。B樹，概括來說是一個一般化的二叉查詢樹，可以擁有多於2個子節點。與自平衡二叉查詢樹不同，B-樹為系統最最佳化大塊資料的讀和寫操作。B-tree演算法減少定位記錄時所經歷的中間過程，從而加快存取速度。這種資料結構常被應用在資料庫和檔案系統的實作上。
在B樹中查詢給定關鍵字的方法
是，首先把根結點取來，在根結點所包含的關鍵字K1，…，Kn查詢給定的關鍵字（可用順序查詢或二分查詢法），若找到等於給定值的關鍵字，則查詢成功；否則，一定可以確定要查詢的關鍵字在Ki與Ki+1之間，Pi為指向子樹根節點的指標，此時取指標Pi所指的結點繼續查詢，直至找到，或指標Pi為空時查詢失敗。
4。2 B樹的性質
B樹作為一種
多路搜尋樹
（並不是二叉的）：
1） 定義任意非葉子結點最多隻有M個兒子；且M>2；
2） 根結點的兒子數為［2， M］；
3） 除根結點以外的非葉子結點的兒子數為［M/2， M］；
4） 每個結點存放至少M/2-1（取上整）和至多M-1個關鍵字；（至少2個關鍵字）
5） 非葉子結點的關鍵字個數=指向兒子的指標個數-1；
6） 非葉子結點的關鍵字：K［1］， K［2］， …， K［M-1］；且K［i］ < K［i+1］；
7） 非葉子結點的指標：P［1］， P［2］， …， P［M］；其中P［1］指向關鍵字小於K［1］的子樹，P［M］指向關鍵字大於K［M-1］的子樹，其它P［i］指向關鍵字屬於（K［i-1］， K［i］）的子樹；
8） 所有葉子結點位於同一層；
如下圖為一個M=3的B樹示例：
B樹建立的示意圖
5。 B+樹
5。1 什麼是B+樹
B+樹是B樹的變體，也是一種多路搜尋樹。 其定義基本與B-樹相同，除了：
非葉子結點的子樹指標與關鍵字個數相同；
非葉子結點的子樹指標P［i］，指向關鍵字值屬於［K［i］， K［i+1］）的子樹（B-樹是開區間）；
為所有葉子結點增加一個鏈指標；
所有關鍵字都在葉子結點出現；
下圖為M=3的B+樹的示意圖：
B+樹的搜尋與B樹也基本相同，區別是B+樹只有達到葉子結點才命中（B樹可以在非葉子結點命中），其效能也等價於在關鍵字全集做一次二分查詢；
5。2 B+的性質
所有關鍵字都出現在葉子結點的連結串列中（稠密索引），且連結串列中的關鍵字恰好是有序的；
不可能在非葉子結點命中；
非葉子結點相當於是葉子結點的索引（稀疏索引），葉子結點相當於是儲存（關鍵字）資料的資料層；
更適合檔案索引系統。
下面為一個B+樹建立的示意圖：
6。 B*樹
B*樹是B+樹的變體，在B+樹的非根和非葉子結點再增加指向兄弟的指標，將結點的最低利用率從1/2提高到2/3。
B*樹如下圖所示：
B*樹定義了非葉子結點關鍵字個數至少為（2/3）*M，即塊的最低使用率為2/3（代替B+樹的1/2）；
B+樹的分裂
：當一個結點滿時，分配一個新的結點，並將原結點中1/2的資料複製到新結點，最後在父結點中增加新結點的指標；B+樹的分裂隻影響原結點和父結點，而不會影響兄弟結點，所以它不需要指向兄弟的指標；
B*樹的分裂
：當一個結點滿時，如果它的下一個兄弟結點未滿，那麼將一部分資料移到兄弟結點中，再在原結點插入關鍵字，最後修改父結點中兄弟結點的關鍵字（因為兄弟結點的關鍵字範圍改變了）；如果兄弟也滿了，則在原結點與兄弟結點之間增加新結點，並各複製1/3的資料到新結點，最後在父結點增加新結點的指標；
所以，
B*樹分配新結點的機率比B+樹要低，空間使用率更高。
7。 R樹
同樣也是一種多路搜尋樹，R樹是用來做空間資料儲存的樹狀資料結構。例如給地理位置，矩形和多邊形這類多維資料建立索引。
R樹的核心思想是聚合距離相近的節點並在樹結構的上一層將其表示為這些節點的最小外接矩形（MBR），這個最小外接矩形就成為上一層的一個節點。
因為所有節點都在它們的最小外接矩形中，所以跟某個矩形不相交的查詢就一定跟這個矩形中的所有節點都不相交。葉子節點上的每個矩形都代表一個物件，節點都是物件的聚合，並且越往上層聚合的物件就越多。也可以把每一層看做是對資料集的近似，葉子節點層是最細粒度的近似，與資料集相似度100%，越往上層越粗糙。
8。 Trie樹
8。1 什麼是Trie樹
Trie樹稱為字典樹，又稱單詞查詢樹，Trie樹，是一種樹形結構，是一種雜湊樹的變種。典型應用是用於統計，排序和儲存大量的字串（但不僅限於字串），所以經常被搜尋引擎系統用於文字詞頻統計。
它的優點是：利用字串的公共字首來減少查詢時間，最大限度地減少無謂的字串比較，查詢效率比雜湊樹高。
8。2 Trie樹的三個基本性質
1） 根節點不包含字元，除根節點外每一個節點都只包含一個字元；2） 從根節點到某一節點，路徑上經過的字元連線起來，為該節點對應的字串；3） 每個節點的所有子節點包含的字元都不相同。
8。3 Tire樹的應用
串的快速檢索
給出N個單片語成的熟詞表，以及一篇全用小寫英文書寫的文章，請你按最早出現的順序寫出所有不在熟詞表中的生詞。在這道題中，我們可以用陣列列舉，用雜湊，用字典樹，先把熟詞建一棵樹，然後讀入文章進行比較，這種方法效率是比較高的。
“串”排序
給定N個互不相同的僅由一個單詞構成的英文名，讓你將他們按字典序從小到大輸出。用字典樹進行排序，採用陣列的方式建立字典樹，這棵樹的每個結點的所有兒子很顯然地按照其字母大小排序。對這棵樹進行先序遍歷即可。
最長公共字首
對所有串建立字典樹，對於兩個串的最長公共字首的長度即他們所在的結點的公共祖先個數，於是，問題就轉化為求公共祖先的問題。
推薦閱讀：
［1］ 資料結構與演算法 | 你知道快速排序，那你知道它的衍生應用嗎？Partition函式
［2］ 資料結構與演算法 | 二分查詢：劍指offer53 在排序陣列中查詢數字
關注微信公眾號：
邁微電子研發社
，回覆獲取更多精彩內容。
△微信掃一掃關注「邁微電子研發社」公眾號
知識星球：
社群旨在分享AI演算法崗的秋招/春招準備攻略（含刷題）、面經和內推機會、學習路線、知識題庫等。
△掃碼加入「邁微電子研發社」學習輔導群
