紅黑樹（Red Black Tree）介紹
- November 27, 2019
- Liu, An-Chi 劉安齊
¶ 紅黑樹簡介
紅黑樹是一種特別的資料結構，他具有跟 AVL Tree 一樣可以自動平衡的功能。
一個紅黑樹具有一下特性：
- 每個 node 只有黑與紅
- Root 必須是黑
- 每個葉子（leaf）是
NIL且為黑 - 如果一個 node 是紅，那他的 child 都會是黑
- 每一條從 root 到 leaf 的路徑所包含的黑色 node 數量都一樣
遵循這樣的規則，可以確保在增加和刪除節點時，保持著樹的平衡狀態。紅黑數保證當 node 數量是 n 時，他的高度最多不會超過 2log(n+1)。
在現實生活中，常常用來實作 set 和 dictionary，C++ 中的 std::set 和 std::map 背後正是紅黑樹。