红黑树原理备忘

红黑树是由结点组成的数据结构，是一棵自平衡二叉搜索树，它在每个结点上增加了一个存储位来表示结点的颜色，可以是红色或者黑色，通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出两倍，因而近似于平衡的。

树中每个结点包含5个属性：color、key、left、right和p。

红黑树的规则是从根开始，任何节点的左分支中的任何元素总是小于节点本身中的元素。右边的元素总是更大。

红黑树保证了搜索，获取，放置和删除等基本操作采用对数时间O(log n)。

自我平衡是关键。对于每次插入和删除，任何边缘上的树的最大高度保持为O(log n) ，即树连续地平衡自身。

红黑树的五条性质：

1. 每个结点或是红色的，或是黑色的。
2. 根节点时黑色的。
3. 每个叶结点是黑色的。
4. 如果一个结点是红色的，则它的两个子结点都是黑色的。
5. 对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。

一颗具有n个内部结点的红黑树的高度至多为2lg(n+1)。