一、红黑树（Red-Black Tree）是二叉搜索树（Binary Search Tree）的一种。二叉搜索树在最坏的情况下可能会变成一个链表（当所有节点按从小到大的顺序依次插入后）。这种低效产生的原因是树没有维持一定的平衡性，要提高搜索效率，就要想办法来维持树左边的平衡，也就是要尽时降低树的高度，可行的做法就是用一些策略在每次修改树的内容之后都调整树的结构，使之满足一定的平衡条件。其中一种满足一定平衡条件而且目前应用广泛的是红黑树。它可以在每一次插入或删除节点之后都会花O（log N）的时间来对树的结构作修改，以保持树的平衡。而红黑树的查找方法与二叉搜索树完全一样，也能够在O(log N)

作者: Rollen Holt 发表于 2010-12-16 00:34 原文链接

评论: 0　查看评论　发表评论

最新新闻：
· 在线比价搜索引擎Shop.com出售 盖茨曾投资(2010-12-16 08:54)
· 邓元鋆离职背后：诺基亚中国腹背受敌(2010-12-16 08:53)
· 央行：超级网银收费将降低(2010-12-16 08:52)
· Android和iPhone平台2010年度最佳软件和游戏榜单出炉(2010-12-16 08:50)
· 京东遭遇出版社集体逼宫 今日恢复原价改返券(2010-12-16 08:48)

网站导航：博客园首页  我的园子  新闻  闪存  小组  博问  知识库