数据结构学习_02红黑树平衡操作

参考文章 :

• 红黑树原理解析以及Java实现

• 红黑树(五)之 Java的实现

• 废话不多说, 直接开始分析

一、红黑树特性 :

• 1、节点是红色或黑色;
• 2、根节点是黑色;
• 3、所有叶子节点都是黑色;
• 4、每个红色节点必须有两个黑色子节点;
• 5、从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点;

二、插入元素之前 :

• 1、为了保持始终是红黑树的特性, 每次插入元素之后, 都需要进行旋转; 换句话说就是在插入元素之前, 红黑树的特性是完整的;
• 2、在插入元素之前, 红黑树有以下几种结构;

1. 插入节点的父节点为null;
2. 插入节点的父节点为黑色;
3. 插入节点的父节点为红色, 叔叔节点为黑色;
4. 插入节点的父节点为红色, 叔叔节点为红色;

• 3、针对上面四种情况, 有四张图进行描述, 下图采用举例方式, 实际代码需要根据这些特例进行数学归纳法执行;
• 4、为了保持插入之后尽量不破坏红黑树的结构, 插入节点默认为红色;

2.1 父节点为null:

• 此时树实际为空树, 仅修改插入节点的颜色即可;

2.2 父节点为黑色 :

父节点为黑色

• 1、针对上图分两种情况, 一种节点值为350, 插入节点值为50;
• 2、插入节点为350时, 父节点400为黑色, 父节点的子节点为200红色, 此时树的结构被破坏, 所以需要进行旋转操作保证树在插入前后结构不被破坏;

2.3 插入节点的父节点为红色, 叔叔节点为黑色:

插入节点的父节点为红色, 叔叔节点为红色

• 1、插入节点为25时, 其父节点50为红色, 叔叔节点为叶子节点_黑色;
• 2、红黑树的特性(根节点!=null)--->每个节点都有且仅有两个子节点, 如果一个黑色节点有一红一黑两子节点, 则其中黑色节点必定为叶子节点;

2.4 插入节点的父节点为红色, 叔叔节点为红色:

插入节点的父节点为红色, 叔叔节点为红色

• 1、插入节点为25时, 其父节点50为红色, 叔叔节点150为红色;

三、元素插入之后开始进行分析 :

• 1、分析时一定要牢记上面四种情况, 然后根据四种情况进行if...else操作;
• 2、平衡操作是依据jdk1.8 HashMap的红黑树的平衡操作;

3.1 定义基础类:

public class TreeNode {
    public boolean red;
    public TreeNode parent;
    public TreeNode left;
    public TreeNode right;
}

四、红黑树在插入节点前后结构不会被破坏的两种情况:

• 结合上图以及红黑树的特性->当父节点为空, 或者父节点为黑色时, 插入节点不会破坏红黑树的特性;

4.1 插入节点父节点为null :

插入节点父节点为null

• 1、xp = x.parent = null其父节点为null, 所以直接将TreeNode x.red = false;

4.2 插入节点父节点为黑色:

插入节点父节点为黑色

• 1、4L ~ 7L->插入节点的父节点不为空, 且父节点为黑色, 此时红黑树在插入前后结构不会被破坏;

五、插入节点之后, 红黑树结构会破坏:

5.1 插入节点的父节点为红色, 叔叔节点为红色:

• 先分析, 然后开始写代码, 如果父节点为红色, 插入红色节点之后, 不满足红黑树特性4, 导致红黑树结构被破坏, 插入节点的颜色不可能改为黑色, 否则一定会造成红黑树结构被破坏, 且无法修复, 因为此时插入节点之后, 导致包含该插入节点的链路比其他链路多一个节点, 所以只有考虑使其父节点变为黑色;
• 下面代码采用的是递归的方式层层往上层推进;

插入节点的父节点为红色, 叔叔节点为红色

• 1、如上述代码所示, 先置xp.red = false, 但是会造成xppl比xppr多一个黑色节点, 所以在12L处置xppr.red = false, 此时又会造成xpp所在链路比其他链路多一个黑色节点, 所以在14L处置xpp.red = true;
• 2、第一次更改颜色之后, 往上递归一次, 然后判断xppp的节点颜色, 如果xppp.red = true, 则重复第一次的套路, 如果xppp.red = false, 则红黑树处于平衡状态;
• 3、当递归到根节点时, 14L->在递归到根节点时, 根节点被置为红色, 且RootNode.left.red = false, RootNode.right.red = false, 所以此时只需要在5L置RootNode.red = false即可;
• 4、经过上面的一个转换, 红黑树插入节点25之后, 变为如下结构:

插入节点的父节点为红色, 叔叔节点为红色转换之后

5.2 插入节点的父节点为红色, 叔叔节点为黑色:

插入红色节点25以后树的结构

• 从图中可以总结出以下几个规律:
• 1、如果插入节点的父节点为红色, 插入后树的结构一定会被破坏, 然后需要修改插入节点所在链路的节点的颜色使其满足红黑树的特性4, 每条到叶子节点链路的黑色节点个数相同;
• 2、如果叔叔节点为黑色, 则其为空节点, 这点可以用反证法证明, 假设叔叔节点不为null, 则其还有叶子节点, 则插入节点所在链路的黑色节点个数与其叔叔节点所在链路的黑色节点个数一定不同;
• 3、知道上面两个结论以后, 可以按照下面结论来执行红黑树的平衡操作;
• • 3.1 先对红黑树进行翻转, 给其叔叔节点所在链路一个节点, 那么插入节点所在链路的节点必然减少一个;
• • 3.2 在给其叔叔节点所在链路节点时, 还要保证红黑树节点是有序的, 所以只能将xpp给xppr所在链路;
• • 3.3 xp.red = true, 所以xpp.red = false;
    所以翻转之后红黑树结构图如下 :

翻转之后红黑树结构图

• 翻转之后, 红黑树的结构图如上图所示, 此时的操作流程回到了5.1的逻辑;

红黑树翻转操作的实现