Self-Balancing Binary Search Trees

AVL樹

在 AVL 樹中，任一節點對應的兩棵子樹的最大高度差為 1，也被稱為高度平衡樹，增加和刪除元素的操作則可能需要藉由一次或多次樹旋轉，以實現樹的重新平衡。

紅黑樹

在某些屬性上形成平衡，不追求高度的完全平衡，犧牲了部分平衡性以換取插入和刪除操作時少量的旋轉操作，整體來說效能要優於 AVL 樹。

規則：

  1. 節點是紅色或黑色。
  2. 根是黑色。
  3. 所有葉子都是黑色 (葉子是 NIL 節點)。
  4. 每個紅色節點必須有兩個黑色的子節點。
  5. 從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點。