紅黑樹(Red-Black Tree)

紅黑樹的功效等同平衡二元搜尋樹,但是效率更勝一籌。可以直接使用 STL 的 set 、 map ,但是沒有排名功能。

特性:

  • 根結點必須是黑色
  • 節點可為紅色或黑色
  • leaf node 一定是黑色
  • 不允許連續兩個節點都為紅色

參考資料