紅黑樹

前段時間看到STL map使用的數(shù)據(jù)結構是紅黑樹，研究了一下。

紅黑樹的由來

紅黑樹是二叉查找樹的升級版本。二叉樹只是平均樹深為O(lg(n))，但是無法保證樹深h一定是O(lg(n))。這就是紅黑樹發(fā)明的原因。紅黑樹為每個node增加一個bit，為color：red or black。

紅黑樹的屬性

1. 節(jié)點只有兩種顏色：黑的和紅的
2. 根一定為黑色
3. 葉節(jié)點（NIL）一定是黑的
4. 紅節(jié)點的兩個孩子一定是黑的
5. 每條到葉子節(jié)點的路徑，所經(jīng)過的黑色節(jié)點數(shù)（black height)一定都是相同的。

紅黑樹的深度

紅黑樹保證最大深度為2 lg(n+1)，其中n為節(jié)點數(shù)。這吊炸天，二叉查找樹的最壞情況為O(n)，而紅黑樹做到了O( lg n)。至今仍然無法從直觀上得到理解，只是加了顏色，即可獲得這么好的屬性，真是十分神奇。當然了，實現(xiàn)起來要麻煩很多了，INSERT和DELETE實現(xiàn)起來要比二叉查找樹難。