（一）二叉樹

二叉樹指的是每個節(jié)點最多只能有兩個子樹的有序樹。

二叉樹特點

• 每個結(jié)點最多有兩顆子樹，所以二叉樹中不存在度大于2的結(jié)點。
• 左子樹和右子樹是有順序的，次序不能任意顛倒。
• 即使樹中某結(jié)點只有一棵子樹，也要區(qū)分它是左子樹還是右子樹。

二叉樹的分類

• 斜樹：左斜樹（所有的結(jié)點都只有左子樹）、右斜樹（所有的結(jié)點都只有右子樹）。
• 滿二叉樹：1.椰子結(jié)點只能出現(xiàn)在最下層。2.非葉子結(jié)點的度一定是2。3.同樣深度，滿二叉樹結(jié)點個數(shù)最多，葉子數(shù)最多
• 完全二叉樹：編號為i(1<=i<=n)的結(jié)點與同樣深度的滿二叉樹中編號為i的結(jié)點在二叉樹中位置完全相同

二叉樹的存儲

• 順序存儲：按照數(shù)組模式存儲，數(shù)組下標(biāo)從上往下從左往右標(biāo)注。
• 二叉鏈表：鏈表存儲，結(jié)點數(shù)據(jù)定義為：左孩子指針--數(shù)據(jù)域-右孩子指針

二叉樹的遍歷

• 前序遍歷：根結(jié)點出發(fā)，當(dāng)?shù)谝淮蔚竭_結(jié)點時就輸出結(jié)點數(shù)據(jù)，按照先向左在向右的方向訪問。
• 中序遍歷：根結(jié)點出發(fā)，當(dāng)?shù)诙蔚竭_結(jié)點時就輸出結(jié)點數(shù)據(jù)，按照先向左在向右的方向訪問。
• 后序遍歷：根結(jié)點出發(fā)，當(dāng)?shù)谌蔚竭_結(jié)點時就輸出結(jié)點數(shù)據(jù)，按照先向左在向右的方向訪問。
• 層序遍歷：按照樹的層次自上而下的遍歷二叉樹。

復(fù)雜度問題

空間復(fù)雜度：無論是那種遍歷方式，都需要一個輔助棧來存儲，每個節(jié)點都要進棧和出棧，不過是順序的區(qū)別，所以空間復(fù)雜度始終為O(n)。
時間復(fù)雜度：通過遍歷循環(huán)的方式獲取，足夠大時，時間復(fù)雜度為O(n)

（二）B樹

B樹也稱B-樹,它是一顆多路平衡查找樹。M定義節(jié)點的分支個數(shù)。

特點

• 每個結(jié)點最多只有m個子節(jié)點。
• 每個結(jié)點最多有m-1個關(guān)鍵字。
• 每個非葉子節(jié)點（除了根）具有至少? m/2?子節(jié)點。
• 根節(jié)點最少可以只有1個關(guān)鍵字。
• 具有k個子節(jié)點的非葉節(jié)點包含k -1個鍵。
• 所有葉子節(jié)點都位于同一層，或者說根節(jié)點到每個葉子節(jié)點的長度都相同。

B樹的插入

• 如果該結(jié)點元素個數(shù)小于m-1，直接插入
• 如果該結(jié)點元素個數(shù)等于m-1，引起結(jié)點分裂，取中間元素（偶數(shù)個數(shù)，中間兩個隨機選?。迦氲礁腹?jié)點中
• 重復(fù)之前操作，直到所有節(jié)點符合B樹的規(guī)則。

B樹的刪除

• 1.如果刪除的是葉子結(jié)點的元素，且刪除之后還是大于m/2，則直接刪除
• 2.如果刪除的是葉子結(jié)點的元素，但是刪除之后小于m/2，如果兄弟結(jié)點借元素之后，兄弟結(jié)點仍滿足大于m/2，則將父節(jié)點的元素移到該結(jié)點，將兄弟結(jié)點的元素移動到父節(jié)點。
• 3.如果刪除的是葉子結(jié)點的元素，但是刪除之后小于m/2，如果兄弟結(jié)點借元素之后，兄弟結(jié)點借完之后都不滿足大于m/2，則需要將父節(jié)點的元素移到該結(jié)點，然后跟兄弟結(jié)點合并。
• 4.如果刪除的是非葉子結(jié)點，需要將后繼key覆蓋要刪除的key，將后繼key所在子支刪除，繼續(xù)判斷該結(jié)點是否滿足m/2，如果滿足就刪除完成，如果不滿足，且子支為非葉子結(jié)點，繼續(xù)步驟4，如果子支為葉子結(jié)點，則走2和3.

復(fù)雜度問題

B樹的復(fù)雜度和B+樹類似，統(tǒng)一到B+樹中討論。

B+樹

B+樹其實就是對B樹的改造。

特點

• 根節(jié)點至少一個元素
• 非根節(jié)點元素范圍為：m/2 <= k <= m-1
• B+樹有兩種類型的節(jié)點：內(nèi)部結(jié)點（也稱索引結(jié)點）和葉子結(jié)點。內(nèi)部節(jié)點就是非葉子節(jié)點，內(nèi)部節(jié)點不存儲數(shù)據(jù)，只存儲索引，數(shù)據(jù)都存儲在葉子節(jié)點。
• 內(nèi)部結(jié)點中的key都按照從小到大的順序排列，對于內(nèi)部結(jié)點中的一個key，左樹中的所有key都小于它，右子樹中的key都大于等于它。葉子結(jié)點中的記錄也按照key的大小排列。
• 每個葉子結(jié)點都存有相鄰葉子結(jié)點的指針，葉子結(jié)點本身依關(guān)鍵字的大小自小而大順序鏈接。
• 父節(jié)點存有右孩子的第一個元素的索引。

B+樹的插入

• 1.如果結(jié)點中元素小于m-1，則直接插入。
• 2.如果插入結(jié)點之后大于m-1，則將原有結(jié)點分裂成兩個，如果父節(jié)點不存在，則創(chuàng)建內(nèi)部節(jié)點，存儲右孩子結(jié)點第一個元素的索引，將數(shù)據(jù)插入對應(yīng)的結(jié)點，分裂的兩個結(jié)點指針相連。
• 3.分裂成兩個，如果父節(jié)點存在，則將右孩子結(jié)點的第一個元素的索引，插入父節(jié)點。
• 3.當(dāng)父節(jié)點達到m時，將右孩子結(jié)點的第一個元素的索引用來創(chuàng)建父節(jié)點，原父節(jié)點分裂，分別存儲右孩子結(jié)點的第一個索引。

B+樹的刪除

刪除操作因為有指針的存在，就不需要通過父節(jié)點了，直接通過兄弟結(jié)點移動即可。然后更新父節(jié)點的索引。
刪除步驟同B樹借元素的邏輯。刪除后不足借兄弟結(jié)點的元素，修改父節(jié)點的索引，不足時進行合并，更新父節(jié)點索引。

B+樹的時間復(fù)雜度

假設(shè)一個含有N個值，階為n的B+樹。
很顯然，查詢需要按照樹結(jié)構(gòu)從上往下查詢，當(dāng)樹越高，查詢的復(fù)雜度越高，也就是當(dāng)分叉最少的時候，即只分為兩叉時，復(fù)雜度越高。
而每個節(jié)點的數(shù)值為：n/2 <= k <= n-1，同時，二叉的結(jié)構(gòu)，又將數(shù)分成了兩顆子樹，得到以下公式：(n/2)^h >=N/2;
意思是，每個節(jié)點有至少n/2個選擇對應(yīng)下一個節(jié)點，共有h次這樣的選擇，因此，時間復(fù)雜度為O(log N).

B+樹在mysql中的使用

主鍵索引

聯(lián)合索引

葉子結(jié)點最后存儲的是主鍵，因為聯(lián)合索引是非聚簇索引

2-3樹

紅黑樹

紅黑樹，Red-Black Tree 「RBT」是一個自平衡(不是絕對的平衡)的二叉查找樹(BST)，

特點

• 1.每個節(jié)點都有紅色或黑色
• 2.樹的根始終是黑色的 。
• 3.沒有兩個相鄰的紅色節(jié)點（紅色節(jié)點不能有紅色父節(jié)點或紅色子節(jié)點，并沒有說不能出現(xiàn)連續(xù)的黑色節(jié)點）
• 4.從節(jié)點（包括根）到其任何后代NULL節(jié)點(葉子結(jié)點下方掛的兩個空節(jié)點，并且認為他們是黑色的)的每條路徑都具有相同數(shù)量的黑色節(jié)點
• 5.每個葉子結(jié)點null為黑色

紅黑樹的插入

• 1.插入數(shù)字，如果是root節(jié)點，則標(biāo)記為黑色
• 2.插入數(shù)字，父節(jié)點為根結(jié)點，則標(biāo)記為紅色
• 3.插入數(shù)字，新節(jié)點的父節(jié)點為紅色。此時因為不允許有兩個連續(xù)的紅色結(jié)點，所以需要調(diào)整：
  • 3.1.父節(jié)點的兄弟結(jié)點為紅色，則將父節(jié)點和父節(jié)點的兄弟結(jié)點標(biāo)為黑色，并將祖先結(jié)點標(biāo)為紅色，此時，需要判斷祖先結(jié)點的父節(jié)點屬性。
  • 3.2.父節(jié)點的兄弟結(jié)點為黑色，此時又分為幾種情況：
    • 3.2.1.若新插入節(jié)點為父節(jié)點的左孩子，則將父節(jié)點標(biāo)為黑色，祖先節(jié)點標(biāo)為紅色，對祖先節(jié)點進行右旋。
    • 3.2.2.若新插入節(jié)點為父節(jié)點的右孩子，則將父節(jié)點進行左旋，這樣就又變成了3.2.1中的左孩子問題。

紅黑樹的刪除

• 1.被刪除的節(jié)點的兩個孩子都為NIL

  • 1.1.如果刪除的節(jié)點為紅色，則直接刪除
  • 1.2.如果刪除的節(jié)點為黑色
    • 1.2.1.如果刪除節(jié)點的兄弟節(jié)點兩個孩子結(jié)點都為NIL，則刪除該節(jié)點，并將兄弟節(jié)點標(biāo)為紅色，且父節(jié)點標(biāo)為黑色。
    • 1.2.2.如果刪除節(jié)點的兄弟節(jié)點有一個孩子結(jié)點為NIL，一個孩子結(jié)點不為NIL
      • 1.2.2.1.當(dāng)不為NIL的孩子節(jié)點為右孩子時，將該孩子節(jié)點標(biāo)為黑色，兄弟節(jié)點標(biāo)為和父節(jié)點相同的顏色，父節(jié)點標(biāo)為黑色，在根據(jù)父節(jié)點進行一次左旋
      • 1.2.2.2.當(dāng)不為NIL的孩子節(jié)點為左孩子時，將該孩子節(jié)點標(biāo)為黑色，兄弟節(jié)點標(biāo)為紅色，以兄弟節(jié)點進行一次右旋，轉(zhuǎn)為右孩子的情況，將右孩子標(biāo)為和父節(jié)點相同的顏色，父節(jié)點標(biāo)為黑色，兄弟節(jié)點表為黑色，再以父節(jié)點進行左旋。
    • 1.2.3.如果刪除節(jié)點的兄弟節(jié)點兩個孩子都不為NIL。
      • 1.2.3.1.如果兄弟節(jié)點為黑色，則兩個孩子節(jié)點一定為紅色，此時，將兄弟節(jié)點的右孩子節(jié)點標(biāo)為黑色，將兄弟節(jié)點標(biāo)為和父節(jié)點相同的顏色，將父節(jié)點標(biāo)為黑色，并將兄弟節(jié)點的左孩子節(jié)點放到父節(jié)點的右孩子節(jié)點上，以父節(jié)點進行左旋。
      • 1.2.3.2.如果兄弟節(jié)點為紅色，則兩個孩子節(jié)點一定為黑色，此時，將兄弟節(jié)點標(biāo)為黑色，兄弟節(jié)點的左孩子節(jié)點標(biāo)為紅色，將兄弟節(jié)點的左孩子放到父節(jié)點的右孩子節(jié)點上，已父節(jié)點進行左旋。

• 2.刪除節(jié)點的兩個孩子都不為NIL
  按照二叉查找樹刪除節(jié)點的方法找到D的后繼節(jié)點S，交換D和S的內(nèi)容（顏色保持不變），被刪除節(jié)點變?yōu)镾，如果S有不為NIL的節(jié)點，那么繼續(xù)用S的后繼節(jié)點替換S，直到被刪除節(jié)點的兩個孩子都為NIL，問題轉(zhuǎn)化為被刪除節(jié)點D的兩個孩子都為NIL的情況。

• 3.刪除節(jié)點有一個孩子節(jié)點為NIL
  這個孩子節(jié)點一定是紅色，此時，用這個孩子節(jié)點替換刪除的節(jié)點。

樹之間的比較

B樹和B+樹

• 1.B+樹數(shù)據(jù)存儲在葉子結(jié)點，B樹數(shù)據(jù)存儲在各結(jié)點上，B+樹單一結(jié)點存儲的元素更多，使得IO次數(shù)更少。
• 2.B+樹查詢的數(shù)據(jù)都在葉子結(jié)點，B樹各結(jié)點都有可能。B+樹更穩(wěn)定。
• 3.B+樹所有的葉子結(jié)點形成了一個有序鏈表，查詢更快。