1 二叉排序樹、AVL樹

資料結構，就是定義一種性質，並且維護這種性質

BS 樹👉AVL 樹

課程內容#

二叉排序樹#

[又叫二叉搜索樹、二叉查找樹]

基礎知識#

性質：對於任意一個三元組，左子樹 < 根節點 < 右子樹
用途：解決與查找、排名相關的檢索需求
【為什麼樹形結構的查找入口一定是根節點？】
- 首先明白點和邊的含義：集合和關係
- 而根節點代表全集
結構操作：增刪查
- 增
  - 不斷與子樹的根節點比較，遞歸，直到子樹沒有子節點
  - ⭐新節點一定會成為葉節點
- 刪 [節點]
  - 度為 0：直接刪除
  - 度為 1：把子樹 [孤兒子樹] 直接掛到其父節點上
  - 度為 2：[稍麻煩]
    - 找到前驅或者後繼替換原節點
      - 前驅節點：其左子樹中最大值對應的節點 [該節點一定沒有右子樹，度最多為 1]
      - 後繼節點：其右子樹中最小值對應的節點 [該節點一定沒有左子樹，度最多為 1]
      - 【只針對度為 2 的節點，否則需考慮往父節點找、找到什麼程度？】
    - ⭐從而轉換為刪除度為 0 或 1 的節點 [前驅或者後繼] 問題
    - [亦可理解為一維數組的刪除操作]
- 查：根據性質遞歸查找即可
插入順序會影響樹形結構，對應不同的平均查找效率
- 同樣的序列，但不同的插入順序
- 平均查找效率：節點查找次數的期望值。即平均查找次數：查找總次數 / 節點數
  - 假設每個節點等概率地被查找
中序遍歷→從小到大的有序序列
可參考《基礎資料結構》——3 樹與二叉樹 —— 二叉搜索樹

擴展內容#

[具體代碼見代碼演示 —— 二叉排序樹]

刪除操作優化 [代碼演示 —— 二叉排序樹]
- 度為 0 和度為 1 的節點刪除操作可以共用【度為 1】的刪除操作代碼
- 度為 0 的代碼
- 度為 1 的代碼
- 當度為 0 時，temp 指向 NULL，同樣銷毀 root，然後返回 NULL
<排名問題>—— 找排名第k 位的元素
- ⭐增加 size 字段，記錄每棵子樹的節點數量 [包括根節點]
  - 資料結構的精髓，針對具體問題【修改結構定義】
  - 插入、刪除時要更新 size
- 查找條件
  - ① k = LS + 1，根節點就是咱們要找的值
  - ② k < LS + 1，排名第 k 位的元素在左子樹中，到左子樹中繼續找
  - ③ k > LS + 1，排名第 k 位的元素在右子樹中，到右子樹中找排名第 k - LS - 1 位的元素
  - [PS] LS 即左子樹的節點數量
  - 在邊界條件處輸出 [-1 或 key]
<Top-k 問題>—— 找排名前k 位的元素 [排名 <=k 的所有元素]
- 【基於排名問題】
- 查找條件
  - ① k = LS + 1，把左子樹中的值全部輸出
  - ② k < LS + 1，前 k 位元素全都在左子樹中
  - ③ k > LS + 1，根節點和左子樹中的元素，都屬於前 k 位元素
  - 相當於一直縮小樹的大小，從而轉變成第一種情況
  - 解法其實很多 [比如堆]，沒有標準答案
二叉排序樹和快速排序的關係
- 【二叉排序樹是快速排序在思維結構層面用的資料結構】
- 快速排序中的 Partition 操作
  - 把基準值看成二叉排序樹的根節點
  - 每一次 Partition 操作後，基準值和左、右兩邊的關係其實就是👇
  - 根節點和左、右子樹的關係
- ⭐弄懂下面兩個思考即可理解兩者關係
  - 思考 1：快排的時間複雜度和二叉排序樹的建樹時間複雜度之間的關係
    - 其實是一碼事，建樹過程類似多個 Partirion 過程
  - 思考 2：快速選擇算法和二叉排序樹之間的關係
    - 兩者本質也一樣，前者表現為算法，後者表現為資料結構
  - [個人理解]
    - 快速排序是一堆數先做一次 Partition，分半後繼續
    - 建樹過程則是一個數一個數地 Partition，每次都定好這個數的位置再走下一個

平衡二叉查找樹 —AVL 樹#

解決二叉查找樹中的退化問題

基礎知識#

背景
- 發明者：AV、L，AV 的貢獻更大
- 年代：1962 年
- [神經網絡也誕生於這個年代]
性質
- 本質上也是二叉排序樹，擁有二叉排序樹的所有性質
- 添加性質：左、右子樹的高度差不超過 1 [左、右子樹差不多大]
⭐平衡條件、平衡調整

[進一步] 思考#

高度為 H 的 BS、AVL 樹，所包含的節點數量在什麼範圍？

[二叉樹通用上限：2 ^ H - 1]
<BS> H ~ 2 ^ H - 1
<AVL> low(H - 2) + low(H - 1) + 1 ~ 2 ^ H - 1
- 即 1.5 ^ H ~ 2 ^ H - 1，low (H) 代表高度為 H 的 AVL 樹的最少節點數
- 左邊界是一個斐波那契數列
  - 其增長速度為 1.618 ^ n ≈ 1.5 ^ n 【可用來預估】
- 👉節點數量和高度之間的關係為對數關係，所以查找效率是 O (logN) 級別
❓ [進一步] 普通的二叉排序樹的查找效率一定比 AVL 樹差嗎？
- 不一定，取決於插入序列的順序，但是 AVL 樹的下限高
- 【引申】
  - 樹高 = 生命長度，節點數量 = 生命財富，不同的算法，結果不一樣
  - 教育提高的是底線，而不是上限，上限取決於能力和運氣
    - 上限很大程度取決於一個不可選擇的插入序列，聽天由命

調整⭐#

插入 / 刪除 + 調整：插入操作與二叉排序樹一致，關鍵在於調整 [⭐抓著哪個節點旋]

旋轉#

[失衡的時候使用的基本操作]

左旋
- 抓著根節點，以中心點向左旋轉
  - K3 變成根節點
  - K1 成為 K3 的左子樹
  - K3 原本的左子樹 A 成為 K1 的右子樹 [因為 K3> A > K1]
- "葉節點" 深度變化：A 不變，B - 1，K2 + 1
  - 👉子樹樹高變化：左子樹 + 1，右子樹 - 1
右旋
- 抓著根節點，以中心點向右旋轉
  - K2 變成根節點
  - K1 成為 K2 的右子樹
  - K2 原本的右子樹 B 成為 K1 的左子樹 [因為 K2 < B < K1]
- "葉節點" 深度變化：A - 1，B 不變，K3 + 1
  - 👉子樹樹高變化：左子樹 - 1，右子樹 + 1
左、右旋是對稱操作，本質上影響的是子樹的樹高

失衡類型 && 調整策略#

判斷場景：回溯過程中，第一次發現失衡時，只要失衡就調整
情況對稱：LL ——RR ，LR——RL

① LL

⭐關鍵關鍵⭐：分析 h1、h2、h3、h4 之間的關係 [寫等式]
- 分析
  - 一個一個插入，新插入的節點一定是到 A 子樹導致的 LL 型失衡 [刪，也是一个一个刪]
  - 插入前，一定是平衡的
  - 插入後，K1 的左子樹比右子樹高出 2
    - 即 h (K2) = h (K3) + 2，而
      - h(K2) = h1 + 1
      - h(K3) = max(h3, h4) + 1
- 等式關係 =>
  - h1 = max(h3, h4) + 2 = h2 + 1
  - [PS] |h3 - h4| <= 1
**<調整策略>** 大右旋。結果見上圖，平衡分析見下：
- ① K1：左子樹高度h2= 右子樹高度max(h3, h4) + 1=h1 -1
- ② K2：左子樹高度h1= 右子樹高度h2 + 1
- 已平衡，且可以說是平衡得可怕

② LR

⭐關鍵關鍵⭐：分析 h1、h2、h3、h4 之間的關係 [寫等式]
- 分析
  - 一個一個插入，新插入的節點一定是到 B / C 子樹導致的 LR 型失衡
  - 插入前，一定是平衡的
  - 插入後，K1 的左子樹比右子樹高出 2
    - 即 h (K2) = h (D) + 2，而
      - h(K2) = max(h2, h3) + 2
      - h(D) = h4
- 等式關係 =>
  - max(h2, h3) = h4 = h1
  - [PS] |h2 - h3| <= 1

❗ 再次切記！判斷始終發生在回溯過程中第一次失衡時，所以在此之前的所有子樹都是平衡的

**<調整策略>** 小左旋 + 大右旋。結果見下圖：
- 先小左旋轉換成 LL 型，再大右旋 [LL 調整策略]
- 平衡分析
  - 很明顯，左右子樹的高度取決於 h1、h2、h3、h4
  - 而它們之間高度差不超過 1 [h2 或 h3 中的一個可能小 1]

調整策略小結#

發生在回溯階段的，第一个失衡節點處
調整關鍵：四種情況下，ABCD 四棵子樹的樹高關係
四種情況
- LL、LR：最後都需要大右旋
  - LL，大右旋
  - LR，先小左旋，再大右旋
- RL、RR：最後都需要大左旋
  - RL，先小右旋，再大左旋
  - RR，大左旋

[平衡二叉查找樹 —SBTree]#

AVL 通過樹高進行平衡，而 SBTree 是通過節點數量進行平衡
參考 AVL 的學習順序：平衡條件 + 平衡調整 [插入、刪除]

隨堂練習#

第二個序列組成的二叉搜索樹退化成了一個鏈表，插入順序會影響結構
判斷失衡時，從插入節點往上一步一步回溯，有失衡就馬上調整

代碼演示#

二叉排序樹#

5 種基本操作：初始化、銷毀、查找、插入、刪除
增加排序問題 [增加 size 字段]、Top-k 問題解答 [基於排序問題]
[PS]
- 找前驅存在 bug：度為 1 或 0 的節點的前驅不一定存在於子樹中，但此場景不用管
- 遞歸必須考慮邊界條件
- 學會用宏讓代碼更美觀
- 分析二叉樹基本都是討論三種情況：左、根、右
部分結果

【附】隨機生成輸入操作的代碼

生成非等比例的操作類型

AVL 樹#

插入和刪除後，注意重新計算樹高【時刻記得維護結構定義】
- 插入 / 刪除節點時 + 左旋 / 右旋調整時
⭐引入了 NIL 節點，代替 NULL🆒[紅黑樹也需要用到]
- NULL 不可訪問
- NIL 是一個實際節點，可以訪問
- 【方便代碼實現】
LL、LR 以及 RL、RR 最後一個操作分別都是大右旋以及大左旋

附加知識點#

分析二叉樹情況時，基本都是分三種情況：左、根、右

思考點#

普通的二叉排序樹的查找效率一定比 AVL 樹差嗎？
- 不一定，取決於插入序列的順序，但是 AVL 樹的下限高
- 【引申】
  - 樹高 = 生命長度，節點數量 = 生命財富，不同的算法，結果不一樣
  - 教育提高的是底線，而不是上限，上限取決於能力和運氣
    - 上限很大程度取決於一個不可選擇的插入序列，聽天由命

Tips#

學 C++ 的前提：系統編程、網絡知識、算法結構、C 語言
所謂算法設計及分析能力：分類討論 [分幾種情況] 及歸納總結 [多種情況合為一種] 的能力
- 程序 = 算法 + 資料結構
- 通過刷題提高該種能力的人是天賦型選手
推薦極客專欄 ——人人都能學會的編程入門課—— 向傳統學習方法發起的挑戰