C++:RB-tree
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
红黑树的性质
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的，则它的两个孩子结点是黑色的
- 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
- 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
红黑树的插入操作
- 按照二叉搜索的树规则插入新节点
- 检测新节点插入后，红黑树的性质是否造到破坏
为了方便讨论，假设新节点为X，其父节点为P，祖父节点为G，伯父节点(父节点之兄弟节点)为S，曾祖父节点为GG.现在，根据二叉搜索树的规则，新节点X必为叶节点，根据红黑树规则4，X必为红。若P亦为红(这就违反了规则3,必须调整树形)，则G必为黑(因为原为RB-tree,必须遵循规则3)。于是，根据X的插人位置及外围节点(S 和GG)的颜色，有了以下四种考虑。
- 状况1:S为黑且X为外侧插人。对此情况，我们先对P,G做一次单旋转，并更改P,G颜色，即可重新满足红黑树的规则3。
- 状况2: S为黑且x为内侧插人。对此情况，我们必须先对P.X做次单旅转并更改G,X颜色，再将结果对G做-次单旋转，即可再次满足红黑树规则3.
- 状况3: s为红且X为外侧插人。对此情况，先对P和G做-次单旋转，开改变X的颜色。此时如果GG为黑，一切搞定， 如图5-15C.但如果GG为红，则问题就比较大些，唔… 见状况4。
- 状况4: S为红且X为外侧插人。对此情况，先对P和G做一次单旋转，并改变X的颜色。此时如果GG亦为红，还得持续往上做，直到不再有父子连续为红的情况。