Question

红黑树原理之添加节点

Answer 1

在网上看了很多写红黑树的博客，大部分写的都不是很到位，有些关于红黑树的图都是有问题的，很多都没有说清楚什么情况促发哪种操作，看完之后还是不理解，在查看了很多资料之后，决定自己写关于红黑树的理解。分为添加节点篇和删除节点篇，本文为将阐述红黑树的基本原理以及在添加节点时，各种情况下对应的操作。（在看本文前，需要先了解平衡二叉树的原理，因为红黑树的有些操作和二叉平衡树类似）

红黑树之所以被称为红黑树，是因为红黑树的节点的颜色非红即黑，通过对节点颜色的限制和一系列的限制条件来确保红黑树没有任何一条路径是其他路径的两倍长。

红黑树需要满足以下条件：

（1）每个节点非黑即红。

（2）根节点是黑色。

（3）每个叶子节点，即空节点是黑的。

（4）红色节点的两个孩子节点都是黑的

（5）每个节点到子孙节点的所有路径上包含相同数量的黑色节点

如图1所示，就是一颗红黑树：

在插入节点时，总是插入红色节点，这样可以 尽量 避免破坏红黑树的结构，为什么说插入红节点可以 尽量 避免破坏红黑树的结构，假如现在要插入6，即插入到12节点的左孩子，如果6节点是黑色的，那么就会破坏规则（5），即图2中绿色路径上的黑色节点的数量比黄色路径上黑色节点的数量多，如果6节点是红色的，则不会破坏树结构，如图3所示。

红黑树节点的添加可分为以下3种情况

分析：因为插入的是红色节点，所以违背规则（2）根节点是黑色

解决方案：只需要把这个节点的颜色改成黑色即可。

分析：因为插入节点的颜色是红色，不会破坏任何规则。

解决方案：无。

分析：这时又可分为插入节点是父节点的左孩子还是右孩子，以及父节点是祖父节点的左孩子还是右孩子，由于对称性，我们只需要考虑其中一种即可。假设插入的节点是25，即如图4所示的位置。这时破坏了规则（4）红色节点的两个孩子节点都是黑的。

解决方案：将当前节点的父节点和叔叔节点改成黑色，祖父节点改为红色，把当前节点指向祖父节点。如图5所示。

情况4：当前节点的父节点是红色，叔叔节点是黑色，当前节点是其父节点的右孩子。

分析：这时破坏了规则（4）红色节点的两个孩子节点都是黑的。如图5所示。

解决方案：将当前节点的父节点作为新的当前节点，以新的当前节点为支点进行左旋。如图6所示。

[图片上传失败...(image-c45d5d-1594949705288)]

分析：这时破坏了规则（4）红色节点的两个孩子节点都是黑的。如图6所示。

解决方案：父节点改成黑色，祖父节点改成红色，将当前节点改为祖父节点，并以新的当前节点为支点进行右旋。如图7所示。

[图片上传失败...(image-492143-1594949705288)]

以上内容就是关于红黑树添加节点时的操作，本片博客参考了 https://bbs.csdn.net/topics/350253651 。