紅黑樹

一、為什麼會有紅黑樹？       

紅黑樹也是一種二叉查找樹。對于普通的二叉查找樹來說，如果不經任何處理，左右子樹的高度相差嚴重時，查找的效率會退化為連結清單。為了維護左右子樹高度的平衡，引入了AVL二叉樹。AVL樹嚴格符合平衡二叉查找樹的定義，即任何節點的左右子樹高度相差不超過1，是一種高度平衡的二叉查找樹。平衡二叉樹中平衡的意思，其實就是讓整棵樹左右看起來比較對稱、比較平衡，降低樹的高度，相應的插入、删除、查找等操作的效率高一些。紅黑樹是一種近似平衡的二叉樹，之是以說近似平衡，是因為它對平衡的要求比AVL要低，是以維護平衡的成本也要低一些，實際開發過程中紅黑樹的應用範圍要較AVL樹較廣。

二、紅黑樹的定義

1. 根節點是黑色的
2. 每個葉子節點都是黑色的空節點，也就是說，葉子節點不存儲資料
3. 任何相鄰的節點不能同時為紅色
4. 每個節點，從該節點到達其可達葉子節點的所有路徑，都包含相同數目的黑色節點。

三、紅黑樹的時間複雜度

紅黑樹的高度近似log2n，是以它是近似平衡，插入、删除、查找操作的時間複雜度都是O(logn)。

四、關于紅黑樹

對于一般開發人員來說，了解紅黑樹的來曆、時間複雜度和應用就足夠了。至于紅黑樹左旋右旋及着色操作等不是需要硬性了解的内容。個人觀點而已。