自平衡的二叉查找樹
紅黑樹(Red Black Tree) 是一種自平衡的二叉查找樹，常用於實現關聯數組。
紅黑樹在1972年由Rudolf Bayer發明，最初被稱爲平衡二叉B樹(symmetric binary B-trees)，後由Leo J. Guibas 和 Robert Sedgewick 在1978年修改爲現在的“紅黑樹”。紅黑樹通過在每個節點增加一箇顏色屬性（紅色或黑色），並遵循一組特定的規則來保持其平衡，這些規則包括所有葉子節點是黑色的，每個節點到其所有子孫節點的路徑上包含相同數量的黑節點等，確保了紅黑樹在插入和刪除操作時能保持相對平衡的狀態，從而提供接近最優的查找性能。