一、紅黑樹概念

紅黑樹是一棵二叉搜索樹，它在每個節點上增加了一個存儲位用來表示節點顏色(紅色或者黑色)，紅黑樹通過約束顏色，可以保證最長路徑不超過最短路徑的兩倍，因而近似平衡，而且在實際應用中發現紅黑樹性能確實比 AVL樹性能高

紅黑樹具有以下性質：

• 每個節點不是紅色就是黑色的
• 根節點和所有外部節點都是黑色的
• 根節點到所有外部節點的簡單路徑上，沒有兩個連續的紅色節點
• 任一節點到其所有后代外部節點的簡單路徑上，黑色節點的數量都相同

引申問題

為什么滿足上面的顏色約束性質，紅黑樹就能保證最長路徑不超過最短路徑的兩倍？
答：最短路徑在極端情況下一定是全黑的，假設其數量是 x，而最長路徑的黑色節點數量也是 x，并且極端情況下，摻雜的紅色節點數量是 x - 1，所以最長路徑肯定不超過最短路徑的兩倍

二、紅黑樹操作

查找 + 插入 + 刪除