（一）二叉樹(shù)

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

二叉樹(shù)特點(diǎn)

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

二叉樹(shù)的分類

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

二叉樹(shù)的存儲(chǔ)

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

二叉樹(shù)的遍歷

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

復(fù)雜度問(wèn)題

空間復(fù)雜度：無(wú)論是那種遍歷方式熬荆，都需要一個(gè)輔助棧來(lái)存儲(chǔ)舟山，每個(gè)節(jié)點(diǎn)都要進(jìn)棧和出棧，不過(guò)是順序的區(qū)別惶看，所以空間復(fù)雜度始終為O(n)捏顺。
時(shí)間復(fù)雜度：通過(guò)遍歷循環(huán)的方式獲取，足夠大時(shí)纬黎，時(shí)間復(fù)雜度為O(n)

（二）B樹(shù)

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

特點(diǎn)

• 每個(gè)結(jié)點(diǎn)最多只有m個(gè)子節(jié)點(diǎn)本今。
• 每個(gè)結(jié)點(diǎn)最多有m-1個(gè)關(guān)鍵字拆座。
• 每個(gè)非葉子節(jié)點(diǎn)（除了根）具有至少? m/2?子節(jié)點(diǎn)。
• 根節(jié)點(diǎn)最少可以只有1個(gè)關(guān)鍵字冠息。
• 具有k個(gè)子節(jié)點(diǎn)的非葉節(jié)點(diǎn)包含k -1個(gè)鍵挪凑。
• 所有葉子節(jié)點(diǎn)都位于同一層，或者說(shuō)根節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)的長(zhǎng)度都相同逛艰。

B樹(shù)的插入

• 如果該結(jié)點(diǎn)元素個(gè)數(shù)小于m-1躏碳，直接插入
• 如果該結(jié)點(diǎn)元素個(gè)數(shù)等于m-1，引起結(jié)點(diǎn)分裂散怖，取中間元素（偶數(shù)個(gè)數(shù)菇绵，中間兩個(gè)隨機(jī)選纫奚），插入到父節(jié)點(diǎn)中
• 重復(fù)之前操作咬最，直到所有節(jié)點(diǎn)符合B樹(shù)的規(guī)則翎嫡。

B樹(shù)的刪除

• 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)的元素移動(dòng)到父節(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覆蓋要?jiǎng)h除的key，將后繼key所在子支刪除慌随，繼續(xù)判斷該結(jié)點(diǎn)是否滿足m/2芬沉，如果滿足就刪除完成，如果不滿足阁猜，且子支為非葉子結(jié)點(diǎn)丸逸，繼續(xù)步驟4，如果子支為葉子結(jié)點(diǎn)剃袍，則走2和3.

復(fù)雜度問(wèn)題

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

B+樹(shù)

B+樹(shù)其實(shí)就是對(duì)B樹(shù)的改造民效。

特點(diǎn)

• 根節(jié)點(diǎn)至少一個(gè)元素
• 非根節(jié)點(diǎn)元素范圍為：m/2 <= k <= m-1
• B+樹(shù)有兩種類型的節(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)不存儲(chǔ)數(shù)據(jù)畏邢，只存儲(chǔ)索引业扒，數(shù)據(jù)都存儲(chǔ)在葉子節(jié)點(diǎn)。
• 內(nèi)部結(jié)點(diǎn)中的key都按照從小到大的順序排列舒萎，對(duì)于內(nèi)部結(jié)點(diǎn)中的一個(gè)key程储，左樹(shù)中的所有key都小于它，右子樹(shù)中的key都大于等于它。葉子結(jié)點(diǎn)中的記錄也按照key的大小排列章鲤。
• 每個(gè)葉子結(jié)點(diǎn)都存有相鄰葉子結(jié)點(diǎn)的指針致板，葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接。
• 父節(jié)點(diǎn)存有右孩子的第一個(gè)元素的索引咏窿。

B+樹(shù)的插入

• 1.如果結(jié)點(diǎn)中元素小于m-1，則直接插入素征。
• 2.如果插入結(jié)點(diǎn)之后大于m-1集嵌，則將原有結(jié)點(diǎn)分裂成兩個(gè)，如果父節(jié)點(diǎn)不存在御毅，則創(chuàng)建內(nèi)部節(jié)點(diǎn)根欧，存儲(chǔ)右孩子結(jié)點(diǎn)第一個(gè)元素的索引，將數(shù)據(jù)插入對(duì)應(yīng)的結(jié)點(diǎn)端蛆，分裂的兩個(gè)結(jié)點(diǎn)指針相連凤粗。
• 3.分裂成兩個(gè)，如果父節(jié)點(diǎn)存在今豆，則將右孩子結(jié)點(diǎn)的第一個(gè)元素的索引嫌拣，插入父節(jié)點(diǎn)。
• 3.當(dāng)父節(jié)點(diǎn)達(dá)到m時(shí)呆躲，將右孩子結(jié)點(diǎn)的第一個(gè)元素的索引用來(lái)創(chuàng)建父節(jié)點(diǎn)异逐，原父節(jié)點(diǎn)分裂，分別存儲(chǔ)右孩子結(jié)點(diǎn)的第一個(gè)索引插掂。

B+樹(shù)的刪除

刪除操作因?yàn)橛兄羔樀拇嬖诨艺埃筒恍枰ㄟ^(guò)父節(jié)點(diǎn)了，直接通過(guò)兄弟結(jié)點(diǎn)移動(dòng)即可辅甥。然后更新父節(jié)點(diǎn)的索引酝润。
刪除步驟同B樹(shù)借元素的邏輯。刪除后不足借兄弟結(jié)點(diǎn)的元素璃弄，修改父節(jié)點(diǎn)的索引要销，不足時(shí)進(jìn)行合并，更新父節(jié)點(diǎn)索引谢揪。

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

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

B+樹(shù)在mysql中的使用

主鍵索引

聯(lián)合索引

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

2-3樹(shù)

紅黑樹(shù)

紅黑樹(shù)船侧，Red-Black Tree 「RBT」是一個(gè)自平衡(不是絕對(duì)的平衡)的二叉查找樹(shù)(BST)欠气，

特點(diǎn)

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

紅黑樹(shù)的插入

• 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有兩個(gè)連續(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)為紅色，對(duì)祖先節(jié)點(diǎn)進(jìn)行右旋蛤肌。
    • 3.2.2.若新插入節(jié)點(diǎn)為父節(jié)點(diǎn)的右孩子壁却，則將父節(jié)點(diǎn)進(jìn)行左旋，這樣就又變成了3.2.1中的左孩子問(wèn)題裸准。

紅黑樹(shù)的刪除

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

  • 1.1.如果刪除的節(jié)點(diǎn)為紅色展东，則直接刪除
  • 1.2.如果刪除的節(jié)點(diǎn)為黑色
    • 1.2.1.如果刪除節(jié)點(diǎn)的兄弟節(jié)點(diǎn)兩個(gè)孩子結(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)有一個(gè)孩子結(jié)點(diǎn)為NIL，一個(gè)孩子結(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)兩個(gè)孩子都不為NIL。
      • 1.2.3.1.如果兄弟節(jié)點(diǎn)為黑色曾掂，則兩個(gè)孩子節(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)為紅色，則兩個(gè)孩子節(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)的兩個(gè)孩子都不為NIL
  按照二叉查找樹(shù)刪除節(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)的兩個(gè)孩子都為NIL，問(wèn)題轉(zhuǎn)化為被刪除節(jié)點(diǎn)D的兩個(gè)孩子都為NIL的情況筛严。

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

樹(shù)之間的比較

B樹(shù)和B+樹(shù)

• 1.B+樹(shù)數(shù)據(jù)存儲(chǔ)在葉子結(jié)點(diǎn)车胡，B樹(shù)數(shù)據(jù)存儲(chǔ)在各結(jié)點(diǎn)上檬输，B+樹(shù)單一結(jié)點(diǎn)存儲(chǔ)的元素更多，使得IO次數(shù)更少匈棘。
• 2.B+樹(shù)查詢的數(shù)據(jù)都在葉子結(jié)點(diǎn)丧慈，B樹(shù)各結(jié)點(diǎn)都有可能。B+樹(shù)更穩(wěn)定主卫。
• 3.B+樹(shù)所有的葉子結(jié)點(diǎn)形成了一個(gè)有序鏈表逃默，查詢更快。