红黑树算法的时间复杂度和AVL相同，但统计性能比AVL树更高。具体怎样，可以看以下这段描述：
AVL trees are actually easier to implement than RB trees because there are fewer cases. And AVL trees require O(1) rotations on an insertion, whereas red-black trees require O(lg n).
In practice, the speed of AVL trees versus red-black trees will depend on the data that you're inserting. If your data is well distributed, so that an unbalanced binary tree would generally be acceptable (i.e. roughly in random order), but you want to handle bad cases anyway, then red-black trees will be faster because they do less unnecessary rebalancing of already acceptable data.On the other hand, if a pathological insertion order (e.g. increasing order of key) is common, then AVL trees will be faster, because the stricter balancing rule will reduce the tree's height.
Splay trees might be even faster than either RB or AVL trees,depending on your data access distribution. And if you can use a hash instead of a tree, then that'll be fastest of all.
相关链接
http://blog.chinaunix.net/u1/35281/showart_279925.html
http://www.ececs.uc.edu/~franco/C321/html/RedBlack/redblack.html
http://www.cppblog.com/converse/archive/2007/11/28/37430.html
|
Richard Lu @ 2008-06-24 13:17
|
|
Richard Lu @ 2008-03-15 16:18
优秀的领袖所必备的几点素质：
1、稳定的情绪 2、有自省能力 3、精密得思考问题的能力 4、有创造性地解决问题 5、克服个人困难 6、有统筹能力、管理自己的时间 7、知己知彼、用人惟才 8、和别人分享你的蓝图 9、社交能力好，交往广泛 10、能鼓励他人 11、愿意倾听别人说话 12、支持他人的想法 13、挑战自己和同伴 14、扮演良师益友的角色 |
|
Richard Lu @ 2008-02-24 17:48
|
|
Richard Lu @ 2008-02-18 20:02
日子一天一天过,不怎么觉得韶华易逝.猛然回头的时候发现身后是一长串的脚印.或深或浅而已.
07年,工作了.每天上班,周末休息,看看书.下下厨.这就是生活?! 工作并不十分忙,偶尔加班,在软件行业这应该算是性价比比较高的工作了吧.平时?好像也没有其他的活动,这不应该是我所向往的生活.至今回想起来.高中的生活最充实.无他,目标明确耳. 后来,面对生活的选择就多了起来.喜欢各个方面都尝试一下.年轻吧. 今年过年的时候忽然我的灯亮了:其实我的目标不仅仅与此. 08年希望能够对下面的几个方面锻炼: 1. 领导力.能够在人群中树立可信赖的形象.在完成自己事情的前提下对周围的人给予帮助.学习以适当的方式给别人施加影响,团结其他人,完成工作.学习Presentation&meeting技能. 措施:提高专业技能,高效完成自己工作.关心其他人遇到的问题,帮助解决. 开发1~2个有助于提高工作效率的小工具. 参与其他项目的讨论,并提出自己的见解.阅读<Presenting to win><高效能人士的7个习惯><战国策> 2.专业能力.进一步学习C++设计思想,.Net. 学习Revit的Framework.学习Revit的几大组成部分中的4~5项 措施:学习3本书<C++><.net via C#><CLI in action>,阅读Revit代码,学习Revit框架.并在Scribble上试验. 3. 提高英语口语水平,能够较流利的使用英语交流.适应英语的思维方式 措施: <高级口语教程> 阅读. 有问题问蛋蛋. 4.学习经济管理知识. 学习货币,贸易会计知识. 学习6sigma. 措施:阅读.有问题请教蛋蛋.归纳公司的管理方法,收集学习公司的管理流程和文档. 5.学习理财. 深入了解基金,股票的投资原理.学习黄金投资原理 措施:购买10K左右基金.目标收益率10%,向阿姨学习股票投资. 6.积累社会关系.增加社会交际面,人士更多人.交4~5个新朋友,并建立较好的关系 措施:参加公司的羽毛球等运动. 7. 建立良好的生活习惯 10:30睡觉.7:00起床,锻炼.或阅读英语. 其他. 努力减肥 目标65kg. 措施:多运动,晚上少吃.少吃/不吃糖果,巧克力等高热量食品. 以上的目标并不高,但是要达成目标需要时时提醒自己,战胜懒惰.更重要的是时刻记住我的目标! |
|
Richard Lu @ 2007-10-26 22:12
前一段时间睡觉老是做梦。那天梦到蛇了。
周公解梦上说梦到蛇咬自己是要发财。
我后来仔细回忆了一下。依稀记得好像是那条蛇咬了一下我。不过既不大清了。
不管了。就当是咬了我吧。我们Dang的作风。^_^。就喜欢听好听的。
那么什么地方可以发点小财呢？
1。 今天中石油IPO，不管三七二十四我就买了一千，希望能中。不过这个希望比中彩票还小。^_^。好在比买彩票要省2快钱的彩票钱。^_^。这里写一下。留作纪念。
2。今天在公司加了一会班。临走的时候发现老板发信要我们推荐人，^_^。不管三七二十三我就发了6，7份简历过去。希望这几个xdjm多少能够进来一个吧。这个概率要比中石油打新股强。不过要看他们能不能进来了。这里也写一下。留作纪念。
这两个月好像范冲，老是不顺心，希望接下来的日子能够好一点吧。
PS。今天看了一下股票，浮亏6％。希望周一能够挣回来。这个概率介于1和2之间吧。这里也写一下。留作纪念
PPS。前面一篇感叹号居然也有6位xdjm阅读了全文。真是。。。。。
不过不知道有那我读出了我当时的心情呢？ 无奖征文。
|