1. 3分鐘理解完全二叉樹蛙粘、平衡二叉樹、二叉查找樹
完全二叉樹： 葉子節(jié)點只能分布在樹的倒數(shù)第1層和倒數(shù)第二層，倒數(shù)第二層的節(jié)點必須是滿的愕宋，倒數(shù)第一層的節(jié)點可以不全是滿的，但是所有的節(jié)點都只能集中在樹的左側(cè)拯杠。這也說明掏婶，倒數(shù)第二層的節(jié)點肯定不會出現(xiàn)只有右子樹，沒有左子樹的情況潭陪。在構(gòu)建完全二叉樹時雄妥，插入節(jié)點一定先插入左子樹，再插入右子樹依溯。
滿二叉樹： 除了葉子節(jié)點老厌，每個節(jié)點都必須同時擁有左子樹和右子樹
當(dāng)我們用數(shù)組實現(xiàn)一個完全二叉樹時，葉子節(jié)點可以按從上到下黎炉、從左到右的順序依次添加到數(shù)組中枝秤，然后知道一個節(jié)點的位置，就可以輕松地算出它的父節(jié)點慷嗜、孩子節(jié)點的位置淀弹。以上面圖中完全二叉樹為例，標(biāo)號為 2 的節(jié)點庆械，它在數(shù)組中的位置也是 2薇溃，它的父節(jié)點就是 (k/2 = 1)，它的孩子節(jié)點分別是 (2k=4) 和 (2k+1=5)缭乘，別的節(jié)點也是類似沐序。
完全二叉樹的特點是：“葉子節(jié)點的位置比較規(guī)律”。因此在對數(shù)據(jù)進(jìn)行排序或者查找時可以用到它堕绩，比如堆排序就使用了它.
二叉樹的提出其實主要就是為了提高查找效率策幼，比如我們常用的 HashMap（每個元素為<key, value>，通過key的值計算存儲位置） 在處理哈希沖突嚴(yán)重時奴紧，拉鏈過長（為了解決沖突特姐，哈希數(shù)組內(nèi)存儲鏈表頭結(jié)點，若沖突數(shù)過多黍氮，會導(dǎo)致鏈表長度過長）導(dǎo)致查找效率降低到逊，就引入了紅黑樹（與2-3樹比較類似铣口，但是給節(jié)點加入了顏色屬性，在插入的過程中通過顏色變換和節(jié)點旋轉(zhuǎn)調(diào)平衡）觉壶。
二叉查找樹（又叫二叉排序樹脑题、二叉搜索樹），它是具有下列性質(zhì)的二叉樹：
- 若左子樹不空铜靶，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值叔遂；（說明二叉搜索樹可以沒有左子樹，只有右子樹）
- 若右子樹不空争剿，則右子樹上所有結(jié)點的值均大于或等于它的根結(jié)點的值已艰；
- 左、右子樹也分別為二叉搜索樹蚕苇。（這里還需要注意跨層比較的問題哩掺。二叉搜索樹的左右子樹里，左子樹上的所有節(jié)點應(yīng)該小于根節(jié)點涩笤，右子樹上的所有節(jié)點應(yīng)該大于根節(jié)點嚼吞。）
注意：二叉查找樹也可以是空樹。此外蹬碧，二叉查找樹可以只有左子樹或者只有右子樹舱禽。
因此，二叉排序樹的中序遍歷一定是從小到大的恩沽。
在最好的情況下誊稚，二叉排序樹的查找效率比較高，是 O(logn)罗心，其訪問性能近似于折半查找里伯；
但最差時候會是 O(n)，比如插入的元素是有序的渤闷，生成的二叉排序樹就是一個鏈表俏脊，這種情況下，需要遍歷全部元素才行（見下圖 b）。
為了避免構(gòu)建二叉排序樹時房匆，形成鏈表的情況酌伊。引入了平衡二叉樹。平衡二叉樹在插入和刪除元素的過程中卷员，就通過旋轉(zhuǎn)的方法保證每個節(jié)點的左右子樹高度差不大于1.
平衡二叉樹定義如下：
- 平衡二叉樹要么是一棵空樹
- 要么保證左右子樹的高度之差不大于 1
- 子樹也必須是一顆平衡二叉樹
平衡二叉樹內(nèi)盈匾，根節(jié)點與其左子樹、右子樹上節(jié)點的值的大小沒有限制毕骡。
平衡二叉樹在添加和刪除時需要進(jìn)行旋轉(zhuǎn)保持整個樹的平衡削饵，內(nèi)部做了這么復(fù)雜的工作后岩瘦，我們在使用它時，插入窿撬、查找的時間復(fù)雜度都是 O(logn)启昧，性能已經(jīng)相當(dāng)好了。
2. 重溫數(shù)據(jù)結(jié)構(gòu)：理解 B 樹迷帜、B+ 樹特點及使用場景 ----掘金 // 漫畫：什么是B-樹？
B樹：即B-樹辆布，又名平衡多路查找樹瞬矩。
1) B樹與平衡二叉樹的不同點有：
- 平衡二叉樹節(jié)點最多有兩個子樹，而
锋玲，M 階 B 樹表示該樹每個節(jié)點最多有 M 個子樹
- 平衡二叉樹每個節(jié)點只有一個數(shù)據(jù)和兩個指向孩子的指針景用，而 B 樹每個中間節(jié)點有 k-1 個關(guān)鍵字（可以理解為數(shù)據(jù)）和 k 個子樹（ k 介于 M/2 和 M 之間，M/2 向上取整）
-
惭蹂，并且葉子節(jié)點只有關(guān)鍵字伞插，指向孩子的指針為 null
2) B樹與平衡二叉樹的相同點有：
- B 樹的節(jié)點數(shù)據(jù)大小也是按照左小右大，子樹與節(jié)點的大小比較決定了子樹指針?biāo)幬恢谩?/li>
3) 一棵 B 樹必須滿足以下條件：
- 根結(jié)點至少有兩個子女盾碗。
- 每個中間節(jié)點都包含k-1個元素和k個孩子媚污，其中 m/2 <= k <= m
- 每一個葉子節(jié)點都包含k-1個元素，其中 m/2 <= k <= m
- 所有的葉子結(jié)點都位于同一層廷雅。
- 每個節(jié)點中的元素從小到大排列耗美，節(jié)點當(dāng)中k-1個元素正好是k個孩子包含的元素的值域分劃。
B樹在插入和刪除元素時航缀，需要嚴(yán)格按照定義進(jìn)行商架，必要時可以拆分節(jié)點/旋轉(zhuǎn)以保證平衡。
因為 B 樹的子樹大小排序規(guī)則，因此在 B 樹中查找數(shù)據(jù)時唬格，一般需要這樣：
(1). 從根節(jié)點開始家破，如果查找的數(shù)據(jù)比根節(jié)點小，就去左子樹找购岗，否則去右子樹
(2). 和子樹的多個關(guān)鍵字進(jìn)行比較汰聋，找到它所處的范圍，然后去范圍對應(yīng)的子樹中繼續(xù)查找
(3). 以此循環(huán)喊积，直到找到或者到葉子節(jié)點還沒找到為止
B+樹
一個m階的B+樹具有如下幾個特征：
- 有k個子樹的中間節(jié)點包含有k個元素（B樹中是k-1個元素）烹困，每個元素不保存數(shù)據(jù)，只用來索引乾吻，所有數(shù)據(jù)都保存在葉子節(jié)點髓梅。
- 所有的葉子結(jié)點中包含了全部元素的信息，及指向含這些元素記錄的指針绎签，且葉子結(jié)點本身依關(guān)鍵字的大小自小而大順序鏈接枯饿。
- 所有的中間節(jié)點元素都同時存在于子節(jié)點，在子節(jié)點元素中是最大（或最泄畋亍）元素奢方。（無論插入/刪除多少元素，最大元素值都要出現(xiàn)在根節(jié)點中）
B+樹的所有非葉子節(jié)點爸舒，都只是提供 子樹最大值 與 根節(jié)點到葉子節(jié)點的索引蟋字，不存儲實際的數(shù)據(jù)，而B-樹的所有非葉子節(jié)點扭勉，都存儲了子樹的索引和真實數(shù)據(jù)鹊奖。因此，B+樹相對B-樹來說更加矮胖涂炎。此外忠聚，相同大小的磁盤頁，可以存儲更多的B+樹節(jié)點唱捣，查詢時可以減少B+樹的查詢次數(shù)两蟀。
B+樹與B-樹的查詢性能對比：
- 單元素查詢
@ B+樹相比B-樹，磁盤IO次數(shù)更少
@ B+樹一直會查詢到葉子節(jié)點才停止查詢爷光；而B-樹查找到對應(yīng)元素立刻停止查詢，除非無對應(yīng)元素才會查找到葉子節(jié)點澎粟。相對來說蛀序，B+樹的查找更加穩(wěn)定欢瞪。- 范圍查詢
B-樹依靠中序遍歷來進(jìn)行范圍查詢（由于B-樹的特性，其中序遍歷一定是遞增序列）徐裸，需要從葉子節(jié)點向根節(jié)點層層遍歷遣鼓；而B+樹所有的數(shù)據(jù)都存儲在葉子節(jié)點，而且通過鏈表連接起來重贺，因此只需查找葉子節(jié)點即可得到一個范圍的數(shù)據(jù)骑祟。綜上所述，B+樹相對于B樹來說優(yōu)勢在于：
(1). 單一節(jié)點存儲更多的元素气笙，使得查詢的IO次數(shù)更少
(2). 所有查詢都要查找到葉子節(jié)點次企，查詢性能穩(wěn)定
(3). 所有葉子節(jié)點形成有序鏈表，便于范圍查詢
B樹和B+樹的應(yīng)用場景：
1). B樹主要應(yīng)用于文件系統(tǒng)及部分?jǐn)?shù)據(jù)庫索引潜圃，如著名的非關(guān)系型數(shù)據(jù)庫MongoDB
2). 大部分關(guān)系型數(shù)據(jù)庫如mySQL缸棵，都使用B+樹作為索引
若不考慮磁盤IO的讀取時間，m階B樹的時間復(fù)雜度為O(log (m^n))
紅黑樹
紅黑樹的原理比較復(fù)雜谭期，先記住紅黑樹的查找堵第，插入和刪除時間復(fù)雜度都可達(dá)到 O(log2^n)
紅黑樹通過下列性質(zhì)來維持自平衡：
- 節(jié)點是紅色或黑色。
- 根是黑色隧出。
- 所有葉子都是黑色（葉子是NIL節(jié)點）踏志。
- 每個紅色節(jié)點必須有兩個黑色的子節(jié)點。（從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點胀瞪。）
- 從任一節(jié)點到其每個葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點（簡稱黑高）针余。
