红黑树

作者：HaigLee
https://www.jianshu.com/u/67ec21fb270d
本文由 HaigLee 发布。未经许可，禁止转载。

AVL树和（2,4）树具有许多好的特性，但是它们也有一些缺点。例如：AVL树删除后可能需要执行的多重组操作（旋转），（2,4）树在插入和删除之后可能需要进行许多分裂或者融合操作。然而红黑树没有这些缺点，在一次更新之后，它使用O(1)次结构变化来保持平衡。
从形式上来讲，红黑树是一棵带有红色和黑色节点的二叉搜索树，具有下面的属性：

• 根属性：根节点是黑色的；
• 红色属性：红色节点（如果有的话）的子节点是黑色的；
• 深度属性：具有零个或者一个子节点的所有节点都具有相同的黑色深度（被定义为黑色祖先节点的数量）。

另外，红黑树和（2,4）树（不包括它们的琐碎外部节点）之间有一个有趣的对应使红黑树的定义更为直观，即给定一棵红黑树，我们可以构建一棵相应的（2,4）树：合并每一个红色节点w到它的父节点，从w存储条目到其父节点，并使w的子节点变得有序。

作者：HaigLee
https://www.jianshu.com/u/67ec21fb270d
本文由 HaigLee 发布。未经许可，禁止转载。