红黑树（中）完整建树过程_1到10构建红黑树过程

作者：Li_阴宅 | 2024-06-20 05:36:10

踩

1到10构建红黑树过程

手撕JAVA（十四）一文中有些地方表述有误，笔者日后在做修改。这里用画图的方式展示两次红黑树的完整建图过程，一次简单，一次复杂，根据建图过程，就可以理解红黑树是如何实现的。

总结的几点为：

1.根节点必为黑色，任何调整动作都无法将根节点染红

2.新插入节点的父节点和uncle节点同为红色，直接染黑父节点和uncle节点，染红祖父节点（如果祖父节点为根节点，就免疫）

3.新插入节点的父节点为红色，uncle节点为空或者黑色分以下两种情况处理：

3.1连续红节点同侧（即父节点如果在树的右子树，子节点也是父节点的右节点），以父节点为基准，左旋。

3.2.连续红节点异侧，先将祖父节点、父节点变色，然后以祖父节点为基准右旋。

3.旋转动作后变为叶子节点的节点染红，变为根节点的节点染黑。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Li_阴宅/article/detail/738765