定義一棵“紅黑樹”
紅黑樹中的節點，一類被标記為黑色，一類被标記為紅色，除此之外，一顆紅黑樹還需要滿足：
1 根節點是黑色的。
2 每個葉子節點都是黑色的空節點，也就是說，葉子節點不存儲資料。
3 任何相鄰的節點都不能同時為紅色，也就是說，紅色節點是被黑色節點隔開。
4 每個節點，從該節點到達其可達葉子節點的所有路徑，都包含相同數目的黑色節點。
紅黑樹的近似平衡
平衡二叉查找樹的初衷，是為了解決二叉查找樹因為動态更新導緻的性能退化問題。是以，“平衡”的意思可以等價為性能不退化。“近似平衡”就等價為性能不會退化的太嚴重。
總結
紅黑樹是一種平衡二叉查找樹。它是為了解決普通二叉查找樹在資料更新的過程中，複雜度退化的問題而産生的。紅黑樹的高度近似
，是以它是近似平衡，插入、删除、查找操作的時間複雜度都是
。