Chinaunix首页 | 论坛 | 博客
  • 博客访问: 633872
  • 博文数量: 356
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 2287
  • 用 户 组: 普通用户
  • 注册时间: 2013-04-08 17:08
文章分类

全部博文(356)

文章存档

2023年(3)

2022年(7)

2021年(33)

2020年(47)

2019年(36)

2018年(221)

2017年(1)

2015年(1)

2013年(7)

我的朋友

分类: 大数据

2018-12-06 14:56:39

原文地址:红黑树 作者:weizhulinux

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

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

红黑树特点

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

一点经验

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

源码及demo实例

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

阅读(1785) | 评论(0) | 转发(0) |
0

上一篇:trie树

下一篇:IO之内核buffer----"buffer cache"

给主人留下些什么吧!~~