红黑树的插入原理，原理与实现篇

• 红黑树的五大性质(性质四与性质五特别重要)

1. 节点必须是红色或者是黑色

2. 根节点是黑色的

3. 所有的叶子节点是黑色的。

4. 每个红色节点的两个子节点是黑色的，也就是不能存在父子两个节点全是红色。

5. 从任意每个节点到其每个叶子节点的所有简单路径上黑色节点的数量是相同的。

       以下情况两点说明:

1. 新节点是红孩子
2. 二叉树的左分支来讨论，右分支相反即可

• 第0种情况：

       如果，父亲节点是黑色的，那么，直接插入即可！(如图)

• 第一种情况：

       如果，父亲节点是黑色的，它的叔叔是红色的，那么，直接把祖父变成红色，然后，父亲与叔叔变成黑色！(如图)

• 第二种情况：

       如果，父亲节点是红色的，它的叔叔是黑色的，那么，新节点是右孩子，则先左旋，变成第三种情况！(如图)

• 第三种情况：

       如果，父亲节点是红色的，它的叔叔是黑色的，那么，节点是左孩子，则进行以（祖父的节点）向右转！(如图)

红黑树的插入原理，原理与实现篇

原文：http://www.cnblogs.com/courtier/p/4266610.html