大数据时代必备算法----红黑树
我并不打算列出红黑树详细算法,网上太多了。我觉得作为一个开发工程师,能懂得清华大学严蔚敏那本《数据结构》书上所涉及的全部基本算法就已经足够了。
重要的是活学活用,懂得应用。
对工程师而言,能够理解红黑树是个排序二叉树,以及红黑树作为查找表的以下特点,知道把它用在什么业务场景下,能把它和其他算法组合在一起使用,比如说一个二级排重----根据日志分析哪些IP访问过哪些URL,这已经足够了,再复杂一点的问题肯定也能解决。
红黑树特点
红黑树并不追求"完全平衡",它只要求部分地达到平衡,降低了对平衡的要求,从而提高了性能。
由于它的设计初衷,任何不平衡都会在三次旋转之内解决(重新达到平衡条件)。这个特点,让他的插入删除操作带来的旋转次数变成了一个常数。提高性能的根源就在这儿了。AVL树是完全平衡的二叉搜索树,就是因为完全平衡这个条件实在太苛刻,无法降低旋转次数,使AVL树变成了一个华而不实的算法。
红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。
红黑树的算法时间复杂度和AVL相同,但统计性能比AVL树更高。统计指的是对杂乱无章的,完全无序的数据进行排重。
还有一些更好的,能够做到一步旋转之内达到平衡的查找树,但红黑树能够给我们一个比较"便宜"的解决方案。所谓便宜是算法复杂程度相对容易接受,实现相对容易。
一点经验
数据量太大,此算法就废了
不过以前我做数据挖掘的时候一般用这个算法做排重,虽效率比不上布隆算法和调整好的哈希,但也已经很快了。
nginx的应用层异步事务管理用的这个算法,绝对的核心数据结构。
nginx里面的红黑树的实现,为了保持灵活性,实现像linux链表一样,可以同时挂各种各样不同结构的表项,牺牲了友好的封装性,不太易用。但绝对是好东西。
源码及demo实例
最近我找找以前在google code search里面找的红黑说代码贴过来,并给出如何使用。欢迎大家一起使用。
阅读(1785) | 评论(0) | 转发(0) |