Neutrino's Blog: 紅黑樹（Red Black Tree）介紹 - 劉安齊

紅黑樹（RedBlackTree）介紹 2019-11-27 Liu,An-Chi劉安齊 ¶紅黑樹簡介 紅黑樹是一種特別的資料結構，他具有跟AVLTree一樣可以自動平衡的功能。

一個紅黑樹具有一下特性： 每個node只有黑與紅 Root必須是黑 每個葉子（leaf）是NIL且為黑 如果一個node是紅，那他的child都會是黑 每一條從root到leaf的路徑所包含的黑色node數量都一樣 遵循這樣的規則，可以確保在增加和刪除節點時，保持著樹的平衡狀態。

紅黑數保證當node數量是n時，他的高度最多