红黑树

大数据时代必备算法----红黑树

我并不打算列出红黑树详细算法，网上太多了。我觉得作为一个开发工程师，能懂得清华大学严蔚敏那本《数据结构》书上所涉及的全部基本算法就已经足够了。
重要的是活学活用，懂得应用。
对工程师而言，能够理解红黑树是个排序二叉树，以及红黑树作为查找表的以下特点，知道把它用在什么业务场景下，能把它和其他算法组合在一起使用，比如说一个二级排重----根据日志分析哪些IP访问过哪些URL，这已经足够了，再复杂一点的问题肯定也能解决。

红黑树特点

红黑树并不追求"完全平衡"，它只要求部分地达到平衡，降低了对平衡的要求，从而提高了性能。
由于它的设计初衷，任何不平衡都会在三次旋转之内解决（重新达到平衡条件）。这个特点，让他的插入删除操作带来的旋转次数变成了一个常数。提高性能的根源就在这儿了。AVL树是完全平衡的二叉搜索树，就是因为完全平衡这个条件实在太苛刻，无法降低旋转次数，使AVL树变成了一个华而不实的算法。
红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。
红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高。统计指的是对杂乱无章的，完全无序的数据进行排重。
还有一些更好的，能够做到一步旋转之内达到平衡的查找树，但红黑树能够给我们一个比较"便宜"的解决方案。所谓便宜是算法复杂程度相对容易接受，实现相对容易。

一点经验

数据量太大，此算法就废了
不过以前我做数据挖掘的时候一般用这个算法做排重，虽效率比不上布隆算法和调整好的哈希，但也已经很快了。
nginx的应用层异步事务管理用的这个算法，绝对的核心数据结构。
nginx里面的红黑树的实现，为了保持灵活性，实现像linux链表一样，可以同时挂各种各样不同结构的表项，牺牲了友好的封装性，不太易用。但绝对是好东西。

源码及demo实例

最近我找找以前在google code search里面找的红黑说代码贴过来，并给出如何使用。欢迎大家一起使用。