红黑树的插入过程

红黑树是一种自平衡的二叉查找树

它具有以下5个性质：

1、节点颜色必须是红色或者黑色

2、根节点是黑色

3、每个叶子节点（NIL节点、空节点）是黑色的

4、每个红色节点的两个子节点都是黑色

5、从任一节点到每个叶子的所有路径都包含数目相同的黑色节点

假设我们插入这些数据：12   23    34   40  45   67    78   89   90  100  110  120   130   140  

1、插入12，12为根节点，根节点一定为黑；插入23，符合红黑树的基本性质，无需做出调整

 不满足红色节点一定有两个黑色子节点，对12 节点左旋，23变成根，颜色变为黑色，12原来为黑色，旋转后这条路径多了一个黑色节点，所以为了满足性质5，必须将其颜色换为红色

红黑树的插入过程

原文：https://www.cnblogs.com/zh718594493/p/12232297.html