红黑树的特性

灰太狼 2022-02-19 00:15 164阅读 0赞

# [红黑树的特性][Link 1] #

红黑树的特性:  
（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。

![781971-20171223180755506-1482217758.png][]

第二步，添加75节点，由于75节点的值大于当前根节点的值35，因此需要添加到根节点右侧，根据规则2，其父亲节点为black，不需要调整。

![781971-20171223180800225-88287713.png][]

第三步，添加65节点，由于65大于35且小于75，因此，需要添加在75节点的左节点。根据规则4（a）规则进行调整，对父亲节点进行右旋，之后按照5（b），进行调整后，满足条件不需要再次调整。得到如下结果。

![781971-20171223180805506-914956982.png][]          ![781971-20171223180852834-827809646.png][]                     ![781971-20171223180858506-811855708.png][]

第三步，将56添加到现有的结果中，需要对先按照规则3进行调整，之后按照规则1调整，得到如下结果。

![781971-20171223180917850-607990961.png][]                ![781971-20171223180935881-1169632417.png][]              ![781971-20171223180940834-867472224.png][]

第四步，将78添加到现有的树中，为75的右节点，满足条件2不需要进行调整。

![781971-20171223180949350-2123084333.png][]

第五步，将29添加的树中。满足条件2不需要进行调整。

![781971-20171223180958053-1056473490.png][]

第六步。将41添加的树中，按照规则3对其进行颜色调整，之后在按照规则2进行调整，满足条件。

![781971-20171223181005631-2060728019.png][]                 ![781971-20171223181010225-824550814.png][]

第七步，将37添加到树中，需要进行5（b）调整。

![781971-20171223181018928-502890430.png][]             ![781971-20171223181025162-609685017.png][]

第八步，将38添加到树中，按照条件3进行调整，将37和56置black，同时，将41置为red，将41节点置为当前节点重新判断；之后按照4（a）进行调整，将父节点35置为新节点，继续判断；按照5（a）进行最后调整，满足条件。

![781971-20171223181035256-2108483118.png][]                   ![781971-20171223181042881-244881548.png][]                              ![781971-20171223181052615-1647259953.png][]                         ![781971-20171223181056740-211108095.png][]

红黑树在线生成链接：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

[Link 1]: https://www.cnblogs.com/woniu4/p/8086707.html
[781971-20171223180755506-1482217758.png]: /images/20220219/0bbd1ce9ab98425aba0ed5de3d68c507.png
[781971-20171223180800225-88287713.png]: /images/20220219/dc9c92c2525c4ee880694526bd802377.png
[781971-20171223180805506-914956982.png]: https://images2017.cnblogs.com/blog/781971/201712/781971-20171223180805506-914956982.png
[781971-20171223180852834-827809646.png]: https://images2017.cnblogs.com/blog/781971/201712/781971-20171223180852834-827809646.png
[781971-20171223180858506-811855708.png]: /images/20220219/c89078100cc840db8c682f7e64801db6.png
[781971-20171223180917850-607990961.png]: https://images2017.cnblogs.com/blog/781971/201712/781971-20171223180917850-607990961.png
[781971-20171223180935881-1169632417.png]: https://images2017.cnblogs.com/blog/781971/201712/781971-20171223180935881-1169632417.png
[781971-20171223180940834-867472224.png]: /images/20220219/a9dc179fc4174150916d6edcced6b4c2.png
[781971-20171223180949350-2123084333.png]: /images/20220219/bf902ba5184e4b3d82065a6472c98fd0.png
[781971-20171223180958053-1056473490.png]: /images/20220219/4e68ca68f1564e60b8c64ea162697d73.png
[781971-20171223181005631-2060728019.png]: https://images2017.cnblogs.com/blog/781971/201712/781971-20171223181005631-2060728019.png
[781971-20171223181010225-824550814.png]: /images/20220219/a50aa5aac40a49a59e8d193ff10e4b74.png
[781971-20171223181018928-502890430.png]: https://images2017.cnblogs.com/blog/781971/201712/781971-20171223181018928-502890430.png
[781971-20171223181025162-609685017.png]: /images/20220219/f4aafe2983344971b36ba97c92d0a65c.png
[781971-20171223181035256-2108483118.png]: https://images2017.cnblogs.com/blog/781971/201712/781971-20171223181035256-2108483118.png
[781971-20171223181042881-244881548.png]: https://images2017.cnblogs.com/blog/781971/201712/781971-20171223181042881-244881548.png
[781971-20171223181052615-1647259953.png]: https://images2017.cnblogs.com/blog/781971/201712/781971-20171223181052615-1647259953.png
[781971-20171223181056740-211108095.png]: /images/20220219/21d4f81ffb9345de8ac4299e8d5d239e.png