红黑树
昨天下班在地铁上居然听到有人在讨论红黑树,这块虽然一直在用,但早已忘了具体的实现细节,利用周天上午的时间,学习红黑树的知识。
以下红黑树的基本概念来自维基百科红黑树,详细介绍请阅读该文章。
另一篇非常不错的文章:红黑树的变色与旋转
可以拿来直接工程中使用的代码:libtree-github
红黑树(英语:Red–black tree)是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。
红黑树是每个节点都带有颜色属性的二叉查找树,颜色为红色或黑色。在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求:
性质
1.......