红黑树的特性:
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空 (NIL 或 NULL) 的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。[这里指到叶子节点的路径]
当新添加一个节点到树中后，将其颜色置为 red，遵循以下原则对整个树进行调整：
1、 当插入的节点的父节点为 null，则将该节点颜色置为 black。
2、 当插入节点的父节点颜色为 black，不需要调整。
3、 当插入节点的父节点为 red，其叔父节点亦为红色，则将其父亲节点和叔父节点置为 black，同时将祖父节点置为 red，将祖父节点设置为当前新增节点，重新按照从规则 1 开始判断。
4、 但插入节点的父亲节点为 red，其叔父节点为 black 或 null，则需要分多钟情况考虑。
a) 新增节点为父亲节点右孩子同时父亲节点是祖父节点的左孩子，则进行左旋，将父节点置为新节点，重新按照规则 1 进行判断；
b) 新增节点为父亲节点左孩子，同时父亲节点是租户节点的右孩子，则进行右旋，将父节点置为新节点，重新按照规则 1 进行判断；
5、 不满足上述所有条件，将父节点置为 black，同时，将祖父节点置为 red，进行以下两种情况判断。
a) 如果新增节点是父亲节点的左孩子，同时，父亲节点是祖父孩子的左孩子，则对祖父节点进行右旋
b) 其他情况，对祖父节点左旋。
通过以下序列来实现：35、75、65、56、78、29、41、37、38
第一步，首先加入 35，只有根节点，按照规则 1，将其颜色设置为 black。
第二步，添加 75 节点，由于 75 节点的值大于当前根节点的值 35，因此需要添加到根节点右侧，根据规则 2，其父亲节点为 black，不需要调整。
第三步，添加 65 节点，由于 65 大于 35 且小于 75，因此，需要添加在 75 节点的左节点。根据规则 4（a）规则进行调整，对父亲节点进行右旋，之后按照 5（b），进行调整后，满足条件不需要再次调整。得到如下结果。
第三步，将 56 添加到现有的结果中，需要对先按照规则 3 进行调整，之后按照规则 1 调整，得到如下结果。
第四步，将 78 添加到现有的树中，为 75 的右节点，满足条件 2 不需要进行调整。
第五步，将 29 添加的树中。满足条件 2 不需要进行调整。
第六步。将 41 添加的树中，按照规则 3 对其进行颜色调整，之后在按照规则 2 进行调整，满足条件。
第七步，将 37 添加到树中，需要进行 5（b）调整。
第八步，将 38 添加到树中，按照条件 3 进行调整，将 37 和 56 置 black，同时，将 41 置为 red，将 41 节点置为当前节点重新判断；之后按照 4（a）进行调整，将父节点 35 置为新节点，继续判断；按照 5（a）进行最后调整，满足条件。
红黑树在线生成链接：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
原文
若有收获，就点个赞吧
0 人点赞
