紅黑樹簡介

紅黑樹是一種特別的資料結構,他具有跟 AVL Tree 一樣可以自動平衡的功能。

一個紅黑樹具有一下特性:

  • 每個 node 只有黑與紅
  • Root 必須是黑
  • 每個葉子(leaf)是 NIL 且為黑
  • 如果一個 node 是紅,那他的 child 都會是黑
  • 每一條從 root 到 leaf 的路徑所包含的黑色 node 數量都一樣

遵循這樣的規則,可以確保在增加和刪除節點時,保持著樹的平衡狀態。紅黑數保證當 node 數量是 n 時,他的高度最多不會超過 2log(n+1)

在現實生活中,常常用來實作 set 和 dictionary,C++ 中的 std::setstd::map 背後正是紅黑樹。

Continue reading