紅黑樹

紅黑樹是一種自平衡二叉查找樹，在O(log n)時間内做查找，插入和删除等操作。統計性能優化于平衡二叉樹（AVL樹）。

紅黑兩色保證樹的高度近似平衡，

節點是五元組：color（顔色），key（資料），left（左孩子），right（右孩子）和p（父節點）。

顔色是紅或者黑。

根和葉子必須是黑色。

某一節點為紅，則兩個孩子必須是黑的。

從任一節點到其葉子的所有簡單路徑都包含相同數目的黑色節點。

節點的插入：

（1）插入新節點必須為紅色，時間O（N）。導緻出現兩個連續紅色節點的沖突，則通過顔色調換（color flips）和樹旋轉來調整。如果插入黑色會導緻根到葉子的路徑上有一條路上，多了一個額外黑節點，會很難調整。

（2）自上而下調整為紅黑樹。

調整方法有三種情況，詳細見http://dongxicheng.org/structure/red-black-tree/