一、红黑树构建过程

上图所示过程如下：

1. 新插入节点默认为红色，5<10，插入到左子节点，插入后左子树深度为2（叶子节点黑色+根节点 黑色），右子树深度为也是2（叶子节点黑色+根节点黑色），满足红黑树规则。

2. 新插入节点为红色，9<10，需要在左子树进行插入，再和5比较，大于5，放到5的右子树中，此时各个叶子节点到根节点的深度依然是2，但5和9两个节点都是红色，不满足规则第4条，需要进行左旋、右旋操作，使其符合规则。可以看出经过操作后，左右子树又维持了平衡。

上图所示过程如下：

1. 插入节点3后，可以看到又不符合红黑树的规则了，而此时的情况，需要采用颜色反转的操作，就是把5、10两个节点变为黑色，5、10的父节点变为红色，但父节点9是根节点，不能为红色，于是再将 9 变为黑色，这样整个树的深度其实增加了1层。

2. 继续插入6节点，对树深度没有影响。

3. 插入7节点后，6、7节点都为红节点，不满足规则4，需要进行颜色反转调整，也就是7的父节点和 叔叔节点变为黑色，爷爷节点5变为红色。

上图所示过程如下：

1. 继续插入节点19，对树深度没有影响，红黑树的规则都满足，无需调整。

2. 插入节点32后，又出现了不满足规则4的情况，此时节点32没有叔叔节点，如果颜色反转的话，左 右子树的深度就出现不一致的情况，所以需要对爷爷节点进行左旋操作。

3. 父节点取代爷爷节点的位置，父节点变为黑色，爷爷节点变为父节点的左子树变为红色。

上图所示过程如下： 1. 插入节点24后，红黑树不满足规则4，需要调整。 2. 此时父节点32和叔叔节点10都为红色，需要进行颜色反转，爷爷节点19变为红色，父节点、叔叔节点变为黑色，颜色反转树的深度不发生变化。

上图所示过程如下： 1.插入节点17后，未破坏红黑树规则，不需要调整。