紅黑樹

性質

• 紅黑性質

  1. 節點紅或黑
  2. root 節點是黑的
  3. 每個葉節點是黑的
  4. 紅節點的兒子都是黑的
  5. 對每個節點，從該節點到其子孫節點的所有路徑上的包含相同的黑節點。

• 好的查詢樹性質

  一棵有 $n$ 個內節點的紅黑樹的高度至多為 $2\log{(n+1)}$。

操作

• 旋轉

  旋轉操作可以不改變二叉查詢樹的性質而對樹進行調整，可以有左旋(逆時針)和右旋(順時針)。 複雜度為 $O(1)$，因為全部都是指標的移動。

• 插入

  先將紅黑樹當作是普通的二叉查詢樹進行插入，並著為紅色，然後使用一個輔助函式進行調整：

  1. 首先確定紅黑性質有哪些不能繼續保持。(在這一點上，性質 1，3，5都是會成立的。) 當插入的 z 是根節點時，性質 2 被破壞。如果 z 的父節點是紅色的，性質 4 被破壞。

  2. 之後對插入節點 z 進行迭代操作。分三種情況進行討論。

• 刪除

  思想和插入類似，都是先按照普通二叉樹進行，然後進行調整。但是情況多了一點更復雜。

AVL 樹

之前經常聽到 AVL 樹，但是在書裡面卻是以練習題的形式出現的。

操作

• Balance

  分四種情況，對單個節點直接最多兩次旋轉即可。

  然後再分情況對子樹進行檢驗，如果改變了平衡因子的子樹們的平衡因子都還是0，-1，1的話說明已經平衡，否則再進行平衡操作。