紅黑樹 B樹 B+樹 WTF！M3？

• 前言
• 哈夫曼編碼

• 引入
• 小優化
• 進階

• 散列表

• 散列函數的構造

• 直接定址法

• 除留取餘法
• 衝突處理
• 開放定址法

• 線性探測法

• 性能計算 （ASL）

• 刪除元素

• 平方探測法
• 拉鍊法

• 平均查找長度的計算

• 紅黑樹

• AVL樹VS 紅黑樹

• 插入（重要）

• uncle結點為紅的情況（可能需要調整兩次）

• step 1
• step 2

• uncle結點為黑色的情況

• step 1

• 構建一顆紅黑樹的完整過程

• B樹

• 查找（類二叉搜索樹）
• 插入
• 刪除

• B+樹
• B樹 VS B+樹

前言

在學習這篇文章之前建議先學習二叉搜索樹和平衡二叉樹 可以參考我的文章徹底弄懂各種二叉樹
基於就是下文所有PPT和文字都B站藍不過海呀的視頻所寫內容非常優質 十分建議初學者觀看
一切數據結構一旦以動畫的形式呈現就變得不再晦澀難懂了 respect！

哈夫曼編碼

引入

• 通過假如我們想用一串二進制數字來表示一串字符 那麼我們能夠用二進制代表每個字母 例如下圖當中 A=0 B=1 C=10 D=11
• 出現歧義的原因是因為我們在二進制編碼當中出現了相同前綴 導致我們在譯碼的時候會發現結果是不唯一的，

小優化

進階

• 統計在一串字符當中每個字符出現的次數
• 採用合併操作建立哈夫曼樹（每次選擇最小的兩個將他們合二為一）
• 根據給邊賦上權值 左0右1 得到每個字母的哈夫曼編碼
• 這樣能夠保證編出來的碼是最短的 沒有歧義的（允許被正確解碼）

散列表

散列函數的構造

直接定址法

• 這種方式是不適用於關鍵字不連續的情況的 因為假設關鍵字離散分佈 那麼就需要浪費較多的空間 例如下圖當中 我們僅僅是六個離散的關鍵字就要求開闢72個空間來存儲 這是非常浪費空間資源的

除留取餘法

衝突處理

開放定址法

線性探測法

• 線性探測法其實是非常簡單的 因為就是在出現映射衝突的時候一個一個地往前找一旦找到表尾就跳到表頭繼續
• 這個時候就可以解答前面的一個疑惑了 就是本身正常來説對於11取餘數是不會映射到11上的 但是這裏卻留了一個位置出來就是在映射衝突這裏起作用 也就是説很有可能會發生某個關鍵字發生衝突之後使用線性探測法放到了11這裏
• 也就是完全有可能本應映射到對應位置上的關鍵字 但是由於線性探測法的存在就跑到別的位置上去了

性能計算 （ASL）

• 對於成功的情況 我們需要關注的是每個關鍵字的比較次數 然後除以關鍵字總數就可以了
• 對於失敗的情況 我們是以散列到的位置為單位的
• 這裏需要注意的是 我們對於每個位置都需要去比較到空位置為止
• 因為空位置上其實大家會設置一個特殊值（要求不包含關鍵字）就是為什麼空位置也算一次比較次數呢 就
• 以29為例 如果映射到7這個位置上的關鍵字他想要出現查找失敗的情況 我們要求比較到51後面的
• 其次我們不必須計算下表這個位置的次數由於任何數都不會直接映射到這個位置 只有可能是線性探測法 被迫放在這個位置
• 查找失敗 ASL=（每個位置需要比較的次數之和）/許可散裂到的位置總數 （全部都是去掉下表11的）

刪除元素

• 由於我們之前在查找某個元素的時候 倘若對應映射位置上沒有找到就會繼續向前探測 如果探測到空位值上就表明查找失敗了
• 所以我們在刪除元素的時候如果直接刪除的話 就會導致我們在查找的時候破壞我們的查找路徑 所以為了防止該現象 我們在刪除位置上做一個標記 一般也會設為一個特殊值 在查找元素的時候就會直接繼續向下探測

平方探測法

• 引入
• 在前面學習的線性探測法當中大家在計算查找失敗的平均查找長度（ASL）的時候
• 查找長度最大的那幾個位置 都是由於堆積導致的 所以就有了平方探測法 來降低查找失敗的平均查找長度

拉鍊法

• 我們還是採用除留取餘法來構造 只不過每個位置上都是一個空指針
• 可是映射到同一個位置上的元素我們可以採用指針的方式將他們串聯起來
• 對於元素的查找是跟前面有所不同的 在對需要查找的元素取餘之後 我們只必須順着鏈表往下找就可以了
• 包括刪除這裏由於採用了鏈表的方式並不用跟開放定址法那裏提到的兩種方式一樣 在刪除位置上打標記而是直接刪除就好了

平均查找長度的計算

紅黑樹

• 首先我們對於紅黑樹要有一個最基本的認知就是我們之前學習的平衡二叉樹就是對於二叉排序樹在極端情況下查找效率的優化（即當數據原本就有序的情況之下 我們所構建的二叉排序樹是一顆斜樹 從而它的查找效率就退化成了鏈表的查找效率O（N） 因此我們引入平衡二叉樹來處理極端情況）
• 而對於紅黑樹本質上也是對於我們二叉排序樹的優化 所以紅黑樹和AVL樹的前提都得是一顆二叉排序樹 即一定是滿足左<根<右
• 只不過和二叉排序樹的處理策略不一樣罷了
  

AVL樹VS 紅黑樹

• 在這裏我們需知道的是平衡二叉樹對於平衡的要求是比較嚴格的 故而在刪除和查找方面效率是不如紅黑樹的
• 解釋一下為什麼在紅黑樹中左右子樹的高度相差不超過兩倍 ？
• 首先我們根據黑路同的性質可以知道根結點到每個葉子結點所經過的路徑上黑色葉子結點個數相同
• 其次大家根據不紅紅的性質 也就是在一條路徑上面不會出現連續的兩個紅色結點
• 所以假設目前這顆紅黑樹根結點到葉子結點所經過的黑色結點為3個
• 那麼在保持這條性質的基礎之上 最長的路徑一定是黑 紅 黑 紅 黑 即任意結點的左右子樹的高度相差最大不超過兩倍

插入（重要）

uncle結點為紅的情況（可能需要調整兩次）

• 這種情況在插入這裏是得我們特別注意的 因為之後我們要介紹的uncle結點如果為黑色 那麼我們調整的方式是和AVL樹當中LL RR LR RL型保持一致的 唯一不同的是我們應該檢查每次調整過後是否違反了紅黑樹的四條性質

step 1

我們會對叔父爺變色 隨後將爺爺變成插入結點 即我們會再次檢查爺爺是否滿足紅黑樹的性質

所以在前面提到需要調整兩次

step 2

就是檢查爺爺是否滿足要求 如果不滿足就去看爺爺的uncle結點然後再次處理（當然如果爺爺是根結點 那麼我們只需要檢查是否為黑色 即是否符合根葉黑的性質）

uncle結點為黑色的情況

step 1

對於叔叔是黑色結點的情況我們首要目的就是判斷類型 發生問題的結點是位於什麼位置 比如説 如果是根結點左孩子的右子樹 那麼就是LR型 調整方法其實在前面已經説過了 即先左旋左孩子 然後右旋爺爺

構建一顆紅黑樹的完整過程

B樹

• 由來
• 無法跟硬盤進行直接交互的就是我們每次尋找節點進行比較 而每次比較都得由CPU去處理 而CPU
• 也就意味着我們必須將信息讀入內存才可以 而訪問硬盤這個操作是很耗時的
• 即為了解決平衡二叉樹查找數據訪問硬盤次數過多的問題
• 也就是説我們現在只要求將樹高儘可能降低就能減少我們的硬盤訪問次數
• 於是大家利用磁盤連續讀取速度快的特性 使得一個節點存儲多個內容 從而達到降低樹高的目的
• 此時就可以將我們的這棵樹看成多叉 平衡 搜索樹 ——B樹

• （分別對應其三個特性——平衡 有序 多路）

查找（類二叉搜索樹）

• 查找失敗就會走到失敗節點上

插入

• 這個過程是比較形象的 如果忘記了的話還是建議去看一下視頻
• 這個相比刪除是比較簡單的
• 只應該先搞清楚這個到底是幾階B樹 這是我們判斷溢出的基礎
• 值得注意的是 我們的插入操控是有可能需要多次調整的 但是每次調整的手段都是比較單一
• 就是取中間元素接着兩邊分裂開來

刪除

• 什麼叫下溢出 舉個例子來説就是 對於5階B樹而言 他每個節點至少為——5/2上取整-1這麼多個元素的
• 即每個節點至少需要兩個元素
• 那麼刪除就非常有可能導致一個節點裏面元素少於2個 這就叫做下溢出

B+樹

B樹 VS B+樹