（一）二叉樹

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

二叉樹特點(diǎn)

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

二叉樹的分類

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

二叉樹的存儲

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

二叉樹的遍歷

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

復(fù)雜度問題

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

（二）B樹

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

特點(diǎn)

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

B樹的插入

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

B樹的刪除

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

復(fù)雜度問題

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

B+樹

B+樹其實(shí)就是對B樹的改造。

特點(diǎn)

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

B+樹的插入

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

B+樹的刪除

刪除操作因?yàn)橛兄羔樀拇嬖冢筒恍枰ㄟ^父節(jié)點(diǎn)了，直接通過兄弟結(jié)點(diǎn)移動即可。然后更新父節(jié)點(diǎn)的索引。
刪除步驟同B樹借元素的邏輯。刪除后不足借兄弟結(jié)點(diǎn)的元素，修改父節(jié)點(diǎn)的索引，不足時(shí)進(jìn)行合并，更新父節(jié)點(diǎn)索引。

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

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

B+樹在mysql中的使用

主鍵索引

聯(lián)合索引

葉子結(jié)點(diǎn)最后存儲的是主鍵，因?yàn)槁?lián)合索引是非聚簇索引

2-3樹

紅黑樹

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

特點(diǎn)

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

紅黑樹的插入

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

紅黑樹的刪除

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

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

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

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

樹之間的比較

B樹和B+樹

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