红黑树

前段时间看到STL map使用的数据结构是红黑树，研究了一下。

红黑树的由来

红黑树是二叉查找树的升级版本。二叉树只是平均树深为O(lg(n))，但是无法保证树深h一定是O(lg(n))。这就是红黑树发明的原因。红黑树为每个node增加一个bit，为color：red or black。

红黑树的属性

1. 节点只有两种颜色：黑的和红的
2. 根一定为黑色
3. 叶节点（NIL）一定是黑的
4. 红节点的两个孩子一定是黑的
5. 每条到叶子节点的路径，所经过的黑色节点数（black height)一定都是相同的。

红黑树的深度

红黑树保证最大深度为2 lg(n+1)，其中n为节点数。这吊炸天，二叉查找树的最坏情况为O(n)，而红黑树做到了O( lg n)。至今仍然无法从直观上得到理解，只是加了颜色，即可获得这么好的属性，真是十分神奇。当然了，实现起来要麻烦很多了，INSERT和DELETE实现起来要比二叉查找树难。