一默色、《算法—深入淺出》N叉樹(shù)的介紹
二斜棚、《算法—深入淺出》紅黑樹(shù)的旋轉(zhuǎn)
三、《算法—深入淺出》紅黑樹(shù)的插入
四、《算法—深入淺出》紅黑樹(shù)的刪除
一弟蚀、前言
計(jì)算機(jī)科班生肯定在大一/大二就學(xué)過(guò)《數(shù)據(jù)結(jié)構(gòu)》或類(lèi)似的這樣的書(shū)蚤霞，書(shū)里有很多最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)與算法，如：
- 排序算法
- 隊(duì)列與棧
- 二叉樹(shù)义钉、多叉樹(shù)昧绣；
- 無(wú)向圖與有向圖；
等等......
要想學(xué)好捶闸，或者弄清楚市面上的各種樹(shù)：
- 二叉搜索樹(shù)（BST => Binary Search Tree）
- 平衡二叉樹(shù)（AVL夜畴，這里的 AVL 是由三個(gè)人創(chuàng)建，取自他們的名字）
- 紅黑樹(shù)（R-B Tree）
- B 樹(shù)（B-Tree => Balance-Tree）删壮，它不是二叉樹(shù)贪绘，是多叉搜索樹(shù)（有些人也叫 B- 樹(shù)）
- B+ 樹(shù)，它是 B 樹(shù)的變體
- B* 樹(shù)央碟，它是 B+ 樹(shù)的變體
二税灌、二叉搜索樹(shù)（BST）
特點(diǎn)：
- 所有非葉子結(jié)點(diǎn)至多擁有兩個(gè)兒子（Left和Right）；
- 所有結(jié)點(diǎn)存儲(chǔ)一個(gè)關(guān)鍵字亿虽；
- 非葉子結(jié)點(diǎn)的左指針指向小于其關(guān)鍵字的子樹(shù)菱涤，右指針指向大于其關(guān)鍵字的子樹(shù)；
如下圖：
- 它的左子樹(shù)上的節(jié)點(diǎn)的值洛勉，都小于根節(jié)點(diǎn)的值粘秆；
- 它的右子樹(shù)上的節(jié)點(diǎn)的值，都大于根節(jié)點(diǎn)的值收毫；
- 至多只有兩個(gè)兒子節(jié)點(diǎn)攻走；
優(yōu)點(diǎn)：
- 查找方便：
- 當(dāng)前節(jié)點(diǎn)值 == 查找的值，查找結(jié)束此再，返回昔搂；
- 當(dāng)前節(jié)點(diǎn)值大于查找的值，則進(jìn)入左子樹(shù)引润；
- 當(dāng)前節(jié)點(diǎn)值小于查找的值，則進(jìn)入右子樹(shù)痒玩；
- 插入節(jié)點(diǎn)淳附、刪除節(jié)點(diǎn)同查找過(guò)程
當(dāng)樹(shù)的左右子樹(shù)高度接近時(shí)，查找的時(shí)間效率接近 O(n) = logN蠢古，基于沒(méi)有空間開(kāi)銷(xiāo) O(1)
但是奴曙，在極端情況下，B樹(shù)會(huì)退化成一棵線性樹(shù)：
此時(shí)草讶，B樹(shù)的查找洽糟、新增、刪除時(shí)間復(fù)雜度都是 O(n) = N
三、平衡二叉樹(shù)（AVL）
AVL樹(shù)的性質(zhì)：
- 完全滿足一棵二叉搜索樹(shù)（BST）所有特性坤溃；
- 左右子樹(shù)高度差小于等于1拍霜；
還是拿BST中的圖來(lái)闡明：
- 根節(jié)點(diǎn)的左、右子樹(shù)高度分別為：3 和 2薪介，因此高度相差 1祠饺，滿足 AVL 第2點(diǎn)；
- 同理汁政，我們也可以發(fā)現(xiàn)道偷，其它子樹(shù)，其左记劈、右子樹(shù)高度也相差 1勺鸦；
基于 AVL 的特點(diǎn)，在搜索/查找方面目木，其時(shí)間復(fù)雜度 O(n) = logN换途；
但是，由于嚴(yán)苛的平衡要求嘶窄，當(dāng)插入或刪除節(jié)點(diǎn)時(shí)怀跛，可能會(huì)不滿足左右子樹(shù)高度差，因此需要遞歸調(diào)整柄冲，可能引起整棵樹(shù)的遞歸 + 旋轉(zhuǎn)操作吻谋。
四、紅黑樹(shù)（R-B Tree）
紅黑樹(shù)滿足 BST 的特性现横，它不需要像 AVL 那樣漓拾，要完全的平衡（左右子樹(shù)高度差不超過(guò)1）。
下圖中戒祠，列出了滿足紅黑樹(shù)的 5 條性質(zhì)骇两，其中，第5點(diǎn)姜盈，是針對(duì) AVL 完全平衡的一個(gè)寬松條件低千。
之后會(huì)有一系列專(zhuān)門(mén)介紹紅黑樹(shù)，以及如何旋轉(zhuǎn)馏颂、插入示血、刪除節(jié)點(diǎn)來(lái)調(diào)整紅黑樹(shù)。
五救拉、多叉搜索樹(shù) B 樹(shù)（ B-Tree ）
B樹(shù)是 BST 樹(shù)的一個(gè)優(yōu)化难审，BST 樹(shù)只能有最多兩棵子樹(shù)，因此當(dāng)節(jié)點(diǎn)很多時(shí)亿絮，樹(shù)的高度就會(huì)很高告喊。
大家可能會(huì)說(shuō)麸拄，高就高唄，但是效率快黔姜！
嗯....確實(shí)拢切，但這些都是在內(nèi)存中操作，當(dāng)然沒(méi)有問(wèn)題地淀；如果是 TB 級(jí)數(shù)據(jù)呢失球，內(nèi)存還放的下么？或者數(shù)量級(jí)更大點(diǎn)帮毁？
這時(shí)我們可能就需要將數(shù)據(jù)存到文件中实苞，而文件是在硬盤(pán)上，硬盤(pán)又有盤(pán)片烈疚、磁道（柱面）黔牵、扇區(qū)，硬盤(pán)的讀寫(xiě)效率取決于數(shù)據(jù)的連續(xù)性（通常一個(gè)扇區(qū) 128 * 2N次方 字節(jié)）爷肝，如果數(shù)據(jù)不連續(xù)猾浦，都是指針控制，那硬盤(pán)的磁頭需要來(lái)回反復(fù)切換盤(pán)片灯抛、磁道（柱面）金赦、扇區(qū)，因此对嚼，效率就會(huì)很低夹抗。
B 樹(shù)以及后面我們會(huì)說(shuō)的 B+ 樹(shù)，都會(huì)應(yīng)用于數(shù)據(jù)庫(kù)中纵竖，海量級(jí)的數(shù)據(jù)漠烧，都以文件的方式來(lái)存儲(chǔ)，因此靡砌，需要考慮內(nèi)存已脓、文件、磁盤(pán)等因素導(dǎo)致的效率問(wèn)題通殃。
首先度液，給出幾個(gè)概念，B / B+ / B* 都會(huì)涉及到：
- M：代表叉數(shù)画舌，M = 2 即 二叉堕担，M = 3 即 三叉；
- K：關(guān)鍵字（可以理解為節(jié)點(diǎn)的值）骗炉；
- P：指針（指向其它節(jié)點(diǎn)的指針）照宝；
先來(lái)看一下 B 樹(shù)蛇受，如下圖（M = 3）：
好了句葵，概念就這 么多，下面來(lái)介紹下 B樹(shù) 的特性：
- 定義任意非葉子結(jié)點(diǎn)最多只有M個(gè)兒子；且M>2乍丈；
- 根結(jié)點(diǎn)的兒子數(shù)為[2, M]剂碴；
- 除根結(jié)點(diǎn)以外的非葉子結(jié)點(diǎn)的兒子數(shù)為[M/2, M]；
- 每個(gè)結(jié)點(diǎn)存放至少M(fèi)/2-1（取上整）和至多M-1個(gè)關(guān)鍵字轻专；（至少2個(gè)關(guān)鍵字）
- 非葉子結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)=指向兒子的指針個(gè)數(shù)-1忆矛；
- 非葉子結(jié)點(diǎn)的關(guān)鍵字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]请垛；
- 非葉子結(jié)點(diǎn)的指針：P[1], P[2], …, P[M]催训；其中P[1]指向關(guān)鍵字小于K[1]的子樹(shù)，P[M]指向關(guān)鍵字大于K[M-1]的子樹(shù)宗收，其它P[i]指向關(guān)鍵字屬于(K[i-1], K[i])的子樹(shù)漫拭；
- 所有葉子結(jié)點(diǎn)位于同一層；
B樹(shù) 查找：
- B-樹(shù)的搜索混稽，從根結(jié)點(diǎn)開(kāi)始采驻，對(duì)結(jié)點(diǎn)內(nèi)的關(guān)鍵字（有序）序列進(jìn)行二分查找，如果命中則結(jié)束匈勋；
- 否則進(jìn)入查詢(xún)關(guān)鍵字所屬范圍的兒子結(jié)點(diǎn)礼旅；
- 重復(fù)1 / 2，直到所對(duì)應(yīng)的兒子指針為空洽洁，或已經(jīng)是葉子結(jié)點(diǎn)痘系；
六、B+ 樹(shù)
B+ 樹(shù)與 B- 樹(shù)基本概念相同诡挂，除了：
- 非葉子結(jié)點(diǎn)的子樹(shù)指針與關(guān)鍵字個(gè)數(shù)相同碎浇；
- 非葉子結(jié)點(diǎn)的子樹(shù)指針P[i]，指向關(guān)鍵字值屬于[K[i], K[i+1])的子樹(shù)（B-樹(shù)是開(kāi)區(qū)間）璃俗；
- 為所有葉子結(jié)點(diǎn)增加一個(gè)鏈指針奴璃；
- 所有關(guān)鍵字都在葉子結(jié)點(diǎn)出現(xiàn)；
B+ 樹(shù)如下圖（M = 3）：
再講 B+ 樹(shù)特性城豁，再?gòu)?qiáng)調(diào)一下：
上圖中的非葉子節(jié)點(diǎn)苟穆，其關(guān)鍵字只是告訴你該去哪里去找真正的數(shù)據(jù)，僅做查找比較使用唱星，真實(shí)數(shù)據(jù)都在葉子節(jié)點(diǎn)中雳旅。
B+ 樹(shù)的特性：
- 所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點(diǎn)的鏈表中（稠密索引），且鏈表中的關(guān)鍵字恰好是有序的间聊；
- 不可能在非葉子結(jié)點(diǎn)命中攒盈；
- 非葉子結(jié)點(diǎn)相當(dāng)于是葉子結(jié)點(diǎn)的索引（稀疏索引），葉子結(jié)點(diǎn)相當(dāng)于是存儲(chǔ)（關(guān)鍵字）數(shù)據(jù)的數(shù)據(jù)層哎榴；
- 更適合文件索引系統(tǒng)型豁；
七僵蛛、B* 樹(shù)
B* 樹(shù)是基于 B+ 樹(shù)再次升級(jí)，特點(diǎn)是：在B+樹(shù)的非根和非葉子結(jié)點(diǎn)再增加指向兄弟的指針迎变。
- B* 樹(shù)定義了非葉子結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)至少為(2/3)*M充尉，即塊的最低使用率為2/3（代替B+樹(shù)的1/2）；
- B+ 樹(shù)的分裂：
- 當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí)衣形，分配一個(gè)新的結(jié)點(diǎn)驼侠，并將原結(jié)點(diǎn)中1/2的數(shù)據(jù)復(fù)制到新結(jié)點(diǎn)，最后在父結(jié)點(diǎn)中增加新結(jié)點(diǎn)的指針谆吴；
- 只影響原結(jié)點(diǎn)和父結(jié)點(diǎn)倒源，而不會(huì)影響兄弟結(jié)點(diǎn)，所以它不需要指向兄弟的指針句狼；
- B*樹(shù)的分裂：
- 當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí)相速，如果它的下一個(gè)兄弟結(jié)點(diǎn)未滿，那么將一部分?jǐn)?shù)據(jù)移到兄弟結(jié)點(diǎn)中鲜锚，再在原結(jié)點(diǎn)插入關(guān)鍵字突诬，最后修改父結(jié)點(diǎn)中兄弟結(jié)點(diǎn)的關(guān)鍵字（因?yàn)樾值芙Y(jié)點(diǎn)的關(guān)鍵字范圍改變了）；
- 如果兄弟也滿了芜繁，則在原結(jié)點(diǎn)與兄弟結(jié)點(diǎn)之間增加新結(jié)點(diǎn)旺隙，并各復(fù)制1/3的數(shù)據(jù)到新結(jié)點(diǎn)，最后在父結(jié)點(diǎn)增加新結(jié)點(diǎn)的指針骏令；
所以蔬捷，B* 樹(shù)分配新結(jié)點(diǎn)的概率比 B+ 樹(shù)要低，空間使用率更高榔袋；
八周拐、總結(jié)
- 二叉搜索樹(shù)：二叉樹(shù)，每個(gè)結(jié)點(diǎn)只存儲(chǔ)一個(gè)關(guān)鍵字凰兑，等于則命中妥粟，小于走左結(jié)點(diǎn)，大于走右結(jié)點(diǎn)吏够；
- B（B-）樹(shù)：多路搜索樹(shù)勾给，每個(gè)結(jié)點(diǎn)存儲(chǔ)M/2到M個(gè)關(guān)鍵字，非葉子結(jié)點(diǎn)存儲(chǔ)指向關(guān)鍵字范圍的子結(jié)點(diǎn)锅知；所有關(guān)鍵字在整顆樹(shù)中出現(xiàn)播急，且只出現(xiàn)一次，非葉子結(jié)點(diǎn)可以命中售睹；
- B+樹(shù)：在B-樹(shù)基礎(chǔ)上桩警，為葉子結(jié)點(diǎn)增加鏈表指針，所有關(guān)鍵字都在葉子結(jié)點(diǎn)中出現(xiàn)昌妹，非葉子結(jié)點(diǎn)作為葉子結(jié)點(diǎn)的索引捶枢；B+樹(shù)總是到葉子結(jié)點(diǎn)才命中沉噩；
- B*樹(shù)：在B+樹(shù)基礎(chǔ)上，為非葉子結(jié)點(diǎn)也增加鏈表指針柱蟀，將結(jié)點(diǎn)的最低利用率從1/2提高到2/3；
