資料結構 —— 二叉查找樹

二叉查找樹：

• 某節點的左子樹節點值僅包含小于該節點值
• 某節點的右子樹節點值僅包含大于該節點值
• 左右子樹每個也必須是二叉查找樹

根據以上定義可能出現二叉樹有：從數學角度上來講右子樹，顯然不平衡，插叙效率不高。

一、紅黑樹

是一個自平衡(不是絕對的平衡)的二叉查找樹。

定義：

• 每個節點都有紅色或黑色
• 樹的根始終是黑色的 (黑土地孕育黑樹根 )
• 沒有兩個相鄰的紅色節點（紅色節點不能有紅色父節點或紅色子節點，并沒有說不能出現連續的黑色節點）
• 從節點（包括根）到其任何後代NULL節點(葉子結點下方挂的兩個空節點，并且認為他們是黑色的)的每條路徑都具有相同數量的黑色節點

紅黑樹有兩大操作:

1. recolor (重新标記黑色或紅色)
2. rotation (旋轉，這是樹達到平衡的關鍵)

平衡過程中，先嘗試 recolor，如果 recolor 不能達到紅黑樹的 4 點要求，然後我們嘗試 rotation。

參考文章— 紅黑樹

二、AVL樹

參考文章—AVL樹