红黑树相信大家有一定的了解，红黑树是一种应用很广泛的数据结构，详情点这里。
比如在linux内核，nginx等众多开源软件中有应用。
红黑树的关键点就是 节点的插入删除。
插入节点的关键是:
插入新节点总是红色节点
如果插入节点的父节点是黑色, 能维持性质
如果插入节点的父节点是红色, 破坏了性质. 故插入算法就是通过重新着色或旋转, 来维持性质
删除节点的关键是:
如果删除的是红色节点, 不破坏性质
如果删除的是黑色节点, 那么这个路径上就会少一个黑色节点, 破坏了性质. 故删除算法就是通过重新着色或旋转, 来维持性质
通过google可以 发现有很多文章已经把红黑树分析的很好了，现在罗列一下，供以后学习。
Linux 内核红黑树的实现代码位于：
lib/rbtree.c，同时头文件在include/linux/rbtree.h
中，内核中很多模块都使用了红黑树，详细介绍参见内核文档 Documentation/rbtree.txt。
等
原文：http://blog.csdn.net/daniel_ustc/article/details/18367053