Question

红黑树原理讲解

Answer 1

性质1: 每个节点要么是 黑色 ,要么是 红色 。
性质2: 根节点是 黑色 。
性质3: 每个叶子节点(NIL)是黑色。
性质4: 每个 红色 节点的两个子节点一定都是 黑色 。
性质5: 任意一个节点到每个叶子节点的路径都包含 数量相同 的 黑节点 。俗称: 黑高 !
从性质5又可以推出:
性质5.1: 如果一个节点存在黑子节点,那么该结点肯定有两个子节点。

插入操作包括两部分工作:

注意: 插入结点,必须为 红色 ,理由很简单,红色在父节点(如果存在)为黑色节点时,红黑树的黑色平衡没被破坏,不需要做自平衡操作。如果插入结点是黑色,那么插入位置所在的子树黑色结点总是1,必须做自平衡。

最简单的一种情景,直接把插入结点作为根结点就行
注意: 根据红黑树性质2: 根结点是黑色。还需要把插入结点设为黑色。

处理: 更新当前结点的值,为插入结点的值

由于插入的结点是红色的,当插入结点的父结点为黑色时,并不会影响红黑树的平衡,直接插入即可,无需做自平衡。

再次回想红黑树的性质2: 根结点是黑色。如果插入结点的父结点为 红结点 ,那么该父结点不可能为根结点,所以插入结点总是存在祖父结点。这一点很重要,因为后序的旋转操作肯定需要祖父结点的参与。

依据红黑树 性质4可知,红色结点不能相连===>祖父结点肯定为黑结点
因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑层数的情况是:黑红红。显然最简单的处理方式是把其改为: 红黑红
处理:
1.将P和U结点改为黑色
2.将PP改为红色
3.将PP设置为当前结点,进行后序处理

注意: 单纯从插入前来看,叔叔结点非红即空(NIL结点),否则的话破坏了红黑树性质5,此路径比其它路径多一个黑色结点。

处理:

处理:

该情景对应情景4.2,只是方向反转,直接看图

处理:

处理: