从2-3-4树开始理解红黑二叉树（JAVA代码手撸版）

2024-06-20 22:28
文章标签 java 代码 二叉树 理解 红黑

本文主要是介绍从2-3-4树开始理解红黑二叉树（JAVA代码手撸版），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

经典的红黑二叉树在新增/删除数据时维持自平衡始终对应着一个2-3-4 树。本文只关注2-3-4 对应的经典红黑二叉树。
暂时不考虑 2-3 树对应的左倾红黑二叉树。

背景知识

2-3-4 树简介

在这里插入图片描述

一棵 2-3-4 树的结点分为 内部结点 (internal nodes) 和 叶子结点 (leaf nodes) ，定义如下。
内部结点:

  • 2-结点: 拥有1个数据项x，2个子结点。

    • 左子树中任意结点数据项均小于x。
    • 右子树中任意结点数据项均大于x。

  • 3-结点: 拥有2个数据项x,y，3个子结点。

    • 左子树中任意结点数据项均小于x。
    • 中间子树中任意结点数据项均介于x与y之间。
    • 右子树中任意结点数据项均大于y。

  • 4-结点: 拥有3个数据项x,y,z，4个子结点。

    • 左子树中任意结点数据项均小于x。
    • 左侧中间子树中任意结点数据项均介于x与y之间。
    • 右侧中间子树中任意结点数据项均介于y与z之间。
    • 右子树中任意结点数据项均大于z。

  • 叶子结点: 无子结点，数据项为 1 项或 2 项或 3项。

2-3-4 树节点变换

插入操作一定是插入叶子节点中，然后根据情况进行调整。

情形具体过程
1.插入至2-结点或3-结点中插入后变为3-结点或4结点 2.插入至4-结点中
(该结点为根结点)4-结点先分解为3个2-结点后 (树高+1) 再插入。 3.插入至4-结点中
(父结点为2-结点)4-结点先分解为3个2-结点，其中一个与父结点合并，使得父结点变为3-结点，然后再插入。 4.插入至4-结点中
(父结点为3-结点)4-结点先分解为3个2-结点，其中一个与父结点合并，使得父结点变为4-结点，然后再插入。 5.插入至4-结点中
(父结点为4-结点) 与上一条类似，但父结点变为5-结点，继续向上 (送入一个结点后) 分解直到：
1. 遇到2-结点或3-结点，转变为情形1。
2. 遇到4-结点，继续上送。
3. 到根处仍为4-结点，转变为情形2。

红黑树5条性质

五大性质描述
1. 颜色红黑树的结点或者为黑色或者为红色。
2. 根结点根结点为黑色。
3. null结点叶子结点的null子结点(上图未画出，通常都不会画出)为黑色。
4. 不可连续红红色结点的子结点为黑色。
5. 完美黑平衡红黑树是「完美黑平衡」的，即任意叶子结点到根结点所经过的黑链数相同。

左旋

以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。左旋只影响旋转结点和其右子树的结构，把右子树的结点往左子树挪了。

红黑树左旋

在这里插入图片描述

java 代码实现如下(带图解)

/**** @param p*/
void rotate_left(RbNode p) {// 1.处理当前节点的父节点if (p.parent == null) {this.root = p.right;//1} else if (p.parent.left != null && p.parent.left.val == p.val) {p.parent.left = p.right;//1} else {p.parent.right = p.right;//1}// 2.处理历史右子节点。（当前父节点）p.right.parent = p.parent;//2RbNode rightLeftNode = p.right.left;p.right.left = p;//3// 3. 处理当前节点p.parent = p.right;//4p.right = rightLeftNode;//5// 4.处理历史右节点的左子节点if (rightLeftNode != null) {rightLeftNode.parent = p;//6}
}

右旋

以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。右旋只影响旋转结点和其左子树的结构，把左子树的结点往右子树挪了。

红黑树右旋

java 代码实现如下(可优化)

/**** @param p*/
void rotate_right(RbNode p) {// 1.处理当前节点的父节点if (p.parent == null) {this.root = p.left;//1} else if (p.parent.left != null && p.parent.left.val == p.val) {p.parent.left = p.left;//1} else {p.parent.right = p.left;//1}// 2.处理历史左子节点。（当前父节点）p.left.parent = p.parent;//2RbNode leftRightNode = p.left.right;p.left.right = p;//3// 3. 处理当前节点p.parent = p.left;//4p.left = leftRightNode;//5// 4.处理历史左节点的右子节点if (leftRightNode != null) {leftRightNode.parent = p;//6}
}

查询某节点的后继节点

依据二叉树中序遍历，查找当前节点的后续节点（寻找继承人）

  RbNode findSuccessorNode(RbNode curNode) {if (curNode == null) {return null;}//1. 向下搜索-> 当前节点有 右子节点(红黑二叉树删除节点只使用到这里逻辑).if (curNode.right != null) {RbNode mySuccessorNode = curNode;while (mySuccessorNode.left != null) {mySuccessorNode = mySuccessorNode.left;}return mySuccessorNode;}//2. 向上搜索-> 当前节点没有 右子节点.RbNode parent = curNode.parent;//如果没有父节点，则当前节点是root节点，直接返回nullif (parent == null) {return null;}//如果当前节点是父节点的左子节点,则当前节点的后继节点就是 父节点if (parent.left == curNode) {return parent;}//向上搜索当前节点的父节点...中的第一个左节点while (parent.parent != null && parent.parent.right == parent) {parent = parent.parent;}return parent.parent;
}

关于黑色节点

子节点为空页当作黑色节点

关于插入节点

插入节点一定是红色，且一定插入在叶子节点，然后根据情况去调整二叉树平衡状态。

关于删除节点

删除节点最终一定是删除叶子节点，如果删除的不是叶子节点，需要发现待删除节点的后继节点（必然在叶子节点），然后替换之后再删除。最后根据场景调整。

在线模拟红黑二叉树地址

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

红黑二叉树插入节点

红黑二叉树插入节点与 2-3-4 树插入节点对照来理解。主要有三种 2-节点插入节点；3-节点插入节点；4-节点插入节点。

插入2-结点 (2变3)

若在一黑结点下插入，且该黑结点没有红子结点时，那么这个黑结点就代表了2-结点，也就是此时我们会将 x 插入一个2-结点，因此x可直接插入,不需要调整。

插入2-结点

插入3-结点 (3变4)

  • 若在一红色结点下插入，且该红结点不存在红色兄弟结点时，那么这个红结点就代表了3-结点 (与它的黑父结点构成3-结点)
    ，因此x可直接插入此3-结点。
  • 若在一黑色结点下插入，则为左下和右上两种「^」情形，也属于插入3-结点情形。

在这里插入图片描述

从上图中可以看出，当待插入结点在一黑色结点下插入时，直接插入而无需其他处理。

插入4-结点 (4分解为三个2-结点后其中一个2变3)

若在一红色结点下插入，且该红结点有一红色兄弟结点时，那么这个红结点就代表了4-结点 (
与它的黑父结点以及红色兄弟结点构成4-结点)，也就是此时我们会将x 插入一个4-结点。

插入4-结点

由图可以发现：插入节点的父节点是红色节点且叔叔节点也是红色，则就是插入4-节点的场景。

插入节点代码

 public boolean insert(int value) {//如果根节点为空if (this.root == null) {this.root = new RbNode(value);this.root.color = false;return true;}//寻找位置RbNode myParent = this.root;while (myParent.left != null || myParent.right != null) {//新增数据 如果大于当前节点数值，则继续比较当前节点的右节点if (value > myParent.val) {if (myParent.right == null) {break;}//查看子节点myParent = myParent.right;} else if (value < myParent.val) {if (myParent.left == null) {break;}//查看子节点myParent = myParent.left;} else {return false;}}//初始化当前节点RbNode curNode = new RbNode(value);curNode.parent = myParent;if (value < myParent.val) {myParent.left = curNode;} else if (value > myParent.val) {myParent.right = curNode;} else {return false;}//修正insert_fix(curNode);//节点数量+1size++;return true;
}

插入节点修正代码

    /*** 根据经典红黑树和 2-3-4 完全对应的关系，新增节点总共分为三种场景* - 2-3-4 树 插入2-结点 (2变3)* - 2-3-4 树 插入3-结点 (3变4)* - 2-3-4 树 插入4-结点 (插入4-结点 (4分解为三个2-结点后其中一个2变3))** @param curNode*/
private void insert_fix(RbNode curNode) {if (curNode == null) {return;}//父节点为空，则当前节点就是rootif (curNode.parent == null) {curNode.color = false;return;}//父节点是黑色，不需要修正. (父节点是黑色,覆盖全部 2-3-4树的2节点，部分3节点场景)if (!curNode.parent.color) {return;}//以下场景父节点颜色为红色RbNode myParent = curNode.parent;RbNode myGrandParent = curNode.parent.parent;RbNode myUncle = curNode.parent.parent.left;if (myUncle != null && myUncle.val == myParent.val) {myUncle = curNode.parent.parent.right;}//2-3-4 数 --> 4节点.(父节点和叔叔节点都是红色)if (myUncle != null && myUncle.color) {//第一步交换颜色color_flip_up(curNode.parent.parent);//1. x000。//2. 0x00。//3. 00x0。//4. 000x。//继续上溯调整insert_fix(curNode.parent.parent);return;}//2-3-4 数 --> 3节点.(叔叔节点不是红色或者不存在，父节点是红色) 假设插入节点是x,总共三种情况int min = Math.min(Math.min(curNode.val, myParent.val), myGrandParent.val);int max = Math.max(Math.max(curNode.val, myParent.val), myGrandParent.val);//1. x00。if (curNode.val == min) {//由于排除了 父节点是黑色，所以排除了 第一个0是父节点的场景，因此 只剩一种场景 第二个0是父节点.//所以先对第一和第二个0变色，再对第一个0右旋. 得到第一个0成为父节点，x成为左子节点，第二个0成为右子节点效果。color_flip_up(curNode.parent.parent);rotate_right(curNode.parent.parent);}//2. 0x0else if (curNode.val > min && curNode.val < max) {//场景1 第一个0 是祖父节点。if (curNode.parent.val < curNode.parent.parent.val) {//x左旋；x和第一个0交换颜色；x右旋rotate_left(curNode.parent);color_flip_up(curNode.parent);rotate_right(curNode.parent);}//场景2 第二个0 是祖父节点else {// x右旋；x和第一个0交换颜色；x左旋rotate_right(curNode.parent);color_flip_up(curNode.parent);rotate_left(curNode.parent);}}//3. 00xelse {//由于排除了 父节点是黑色，所以排除了 第二个0是父节点的场景，因此 只剩一种场景 第一个0是父节点.//先将第一个和第二个0 交换颜色，然后左旋第二个0color_flip_up(curNode.parent.parent);rotate_left(curNode.parent.parent);}
}

红黑二叉树删除节点

删除操作据说是最难的部分，掌握了删除逻辑约等于掌握了红黑二叉树。

2-3-4 树删除节点的场景

以key 是否在叶子结点中划分

2-3-4树删除 x 情形删除操作
情形1: x 不在叶子结点中用x 的后继键值替换 x，然后删除后继键值
※ 后继键必为某叶子结点中的最小键
情形2: x 在叶子结点中直接删除目标键值
※ 若目标键在2-结点中，删除后失去2-3-4树结构性质，要调整

红黑树删除结点情形

红黑树删除结点 x 情形删除操作
情形a: x 有左右子结点用后继结点 (的键值) 替换 x (的键值)，然后删除后继结点
※ 删除后继结点必为情形b或情形c
情形b: x 有一个子结点建立子结点与 x.parent$ 的链接，然后删除 x
※ x 及其子结点构成3-结点，删除后不影响同构
情形c: x 无子结点删除 x
※ x 对应2-3-4树中的多种情形，可能为红或黑，若为2-3-4树中的2-结点，则删除后失同构，需调整

删除调整

通过上述分析，我们发现仅有 x 无孩子结点且为黑 时才需要恢复同构。
为方便叙述，我们将前述归约出的4种情形与「算法导论」给出的 case1~4 对照如下。

算法导论4情形对应前述4情形
case1: w 为红色情形x-3
只需对 x.p$ 置红及 w 反色并左旋 x.p$ 后转为后续情形
case2: w 为黑色，且其孩子左黑右黑情形1-1
case3: w 为黑色，且其孩子左红右黑情形2-1左侧
只需对 w 及 w.left$ 反色并右旋 w 即为 case4
case4: w 为黑色，且其孩子左黑右红或左红右红情形2-1右侧 & 情形3-1

※ w 是待删除结点 X 的兄弟结点。

删除修复场景

删除操作代码

public boolean remove(int value) {//find 节点RbNode curNode = find(value);if (curNode == null) {return false;}//元素数量减少1size--;//当前节点 无父节点且无孩子节点，则当前节点是跟节点且只剩唯一节点。if (curNode.parent == null && curNode.left == null && curNode.right == null) {curNode.parent = curNode.left = curNode.right = null;this.root = null;return true;}//1. 2-3-4数key 不在叶子节点中。（根据中序遍历可知: 此时当前节点一定有后继节点，且后继节点一定在叶子节点中）。if (curNode.left != null && curNode.right != null) {RbNode successorNode = findSuccessorNode(curNode);//交换数值curNode.val = successorNode.val;//指针指向调整curNode = successorNode;}//2. 2-3-4数key 在叶子节点中（直接删除目标键值然后修正2-3-4数平衡）。RbNode children = curNode.left != null ? curNode.left : curNode.right;//2-a. 红黑二叉树节点 curNode 有一个子节点（左子节点或者右子节点）。// [此种场景保证了 curNode一定是黑色，其子节点一定是红色。删除curNode后，子节点变黑即可保持红黑树性质。不需要调整]if (children != null) {//先处理父节点关系RbNode parent = curNode.parent;if (parent == null) {this.root = children;} else if (parent.left.val == curNode.val) {parent.left = children;} else {parent.right = children;}//再处理当前节点curNode.parent = curNode.left = curNode.right = null;//最后处理子节点children.parent = parent;children.color = false;}//2-b. 红黑二叉树节点 curNode 没有子节点。 此种场景最复杂，当curNode 是红色需要修正。else {//待删除的节点是黑色 则需要修复if (!curNode.color) {remove_fix(curNode);}RbNode parent = curNode.parent;if (parent != null) {//先处理父节点if (parent.left != null && curNode.val == parent.left.val) {curNode.parent.left = null;} else {curNode.parent.right = null;}//再处理当前节点curNode.parent = null;}}return true;
}

删除修复代码

void remove_fix(RbNode curNode) {//2-3-4 树 3-节点和 4-节点 或者根节点 直接删除即可。 不需要修补逻辑//当前节点是红色 则停止修正。（删除修复操作在遇到被删除的节点是红色节点或者到达root节点时，修复操作完毕。）//需要做的处理是从兄弟节点上借调黑色的节点过来，如果兄弟节点没有黑节点可以借调的话，就只能往上追溯，将每一级的黑节点数减去一个，使得整棵树符合红黑树的定义。//删除操作的总体思想是从兄弟节点借调黑色节点使树保持局部的平衡，如果局部的平衡达到了，就看整体的树是否是平衡的，如果不平衡就接着向上追溯调整。//算法导论4情形。 vs 2-3-4 四种情形.(w 是待删除节点的兄弟节点)//删除修复操作分为四种情况(删除黑节点后)：//case 1: w是红色。[只需对当前节点父节点置红以及w节点变黑并且左旋当前节点的父节点，即可转换成下述 2-4场景]//case 2: w是黑色，且其孩子左黑右黑//case 3: w是黑色，且其孩子左红右黑。（只需对 w 和 w.left 变色，然后右旋w，即为场景4）//case 4: w是黑色，且其孩子左黑右红或者左红右红while (curNode.val != this.root.val && colorBlack(curNode)) {//待删除节点是左节点(一切为了 右边兄弟左旋).if (curNode.parent.left != null && curNode.val == curNode.parent.left.val) {RbNode w = curNode.parent.right;//case 1: w是红色。[只需对当前节点父节点置红以及w节点变黑并且左旋当前节点的父节点，即可转换成下述 2-4场景]if (w.color) {//1.w置黑w.color = false;//2. 待删除节点父节点置红curNode.parent.color = true;//3.待删除节点父节点左旋rotate_left(curNode.parent);//更新兄弟节点位置w = curNode.parent.right;}//case 2:w是黑色，且其孩子左黑右黑(w变换颜色，然后向上调整).if (colorBlack(w.left) && colorBlack(w.right)) {//此时 w 一定是黑色(反色目的是让它作为一个3-结点中的红色结点)。w.color = true;//继续向上调整[唯一一个向上调整]curNode = curNode.parent;//如果当前节点是红色 则已经平衡if (curNode.color) {break;}} else {//case 3: w是黑色，且其孩子左红右黑。（只需对 w 和 w.left 变色，然后右旋w，即为场景4）if (colorBlack(w.right)) {//w.left 置黑w.left.color = false;//w 置红w.color = true;//右旋wrotate_right(w);//调整兄弟节点w = curNode.parent.right;}//case 4: w是黑色，且其孩子左黑右红或者左红右红.//置w和curNode.parent 相同颜色w.color = curNode.parent.color;//置curNode.parent 黑色curNode.parent.color = false;//置w.right 黑色w.right.color = false;//左旋curNode.parentrotate_left(curNode.parent);//兄弟节点不存在或者兄弟节点的子节点不存在 则表示已经平衡. 另：case3和case4调整后必平衡。curNode=this.rootw = curNode.parent.right;if (w == null || (w.left == null && w.right == null)) {break;}}} else {//待删除节点是右节点RbNode w = curNode.parent.left;//case 1: w是红色。[只需对当前节点父节点置红以及w节点变黑并且左旋当前节点的父节点，即可转换成下述 2-4场景]if (w.color) {//curNode.parent 置黑curNode.parent.color = true;//w置黑w.color = false;//curNode.parent右旋rotate_right(curNode.parent);//更新兄弟节点位置w = curNode.parent.left;}//case 2:w是黑色，且其孩子左黑右黑(w变换颜色，然后向上调整).if (colorBlack(w.left) && colorBlack(w.right)) {//此时 w 一定是黑色(反色目的是让它作为一个3-结点中的红色结点)。w.color = true;//继续向上调整[唯一一个向上调整]curNode = curNode.parent;//如果当前节点是红色 则已经平衡if (curNode.color) {break;}} else {//case 3: w是黑色，且其孩子右红左黑。（只需对 w 和 w.right 变色，然后右旋w，即为场景4）if (colorBlack(w.left)) {//w.right 置黑w.right.color = false;//w 置红w.color = true;//左旋wrotate_left(w);//调整兄弟节点w = curNode.parent.left;}//case 4: w是黑色，且其孩子左红右黑或者左红右红.//置w和curNode.parent 相同颜色w.color = curNode.parent.color;//置curNode.parent 黑色curNode.parent.color = false;//置w.left 黑色w.left.color = false;//右旋curNode.parentrotate_right(curNode.parent);//兄弟节点不存在或者兄弟节点的子节点不存在 则表示已经平衡. 另：case3和case4调整后必平衡。curNode=this.rootw = curNode.parent.left;if (w == null || (w.left == null && w.right == null)) {break;}}}}// while结束要么是case3/case4调整后已平衡 x被被置为root后主动退出，// 要么是case1/case2 x为红。若为前者无需此句(此时的root一定是黑的)// 若为后者，说明此时的x结点是原3-结点或4-结点出借的结点，如果还保持红色，// 将无法脱离原3-结点或4-结点 (2-3-4树)，因此必须置黑。// 此句也可以写成这样: if(x != root) x.color = BLACK//curNode.color = false;
}

完整代码demo


import java.util.LinkedList;
import java.util.Queue;/*** 对应2-3-4 树；* 规则、设定：* 新插入的节点是红色的;* 新插入节点的父节点是红色才需要修复；* 不支持插入相同的数字，如果插入数字相同直接返回。* 在线验证调试: https://www.cs.usfca.edu/~galles/visualization/RedBlack.html*/
public class RBTree {static class RbNode {/*** 父级*/RbNode parent;/*** true:红色；false 黑色[默认]*/boolean color;/*** 节点数值,简单起见也当作key使用*/int val;/*** 左节点*/RbNode left;/*** 右节点*/RbNode right;public RbNode(int val) {this.val = val;//新插入的节点是红色的this.color = true;}}/*** 主节点*/RbNode root;/*** 尺寸*/int size;public boolean insert(int value) {//如果根节点为空if (this.root == null) {this.root = new RbNode(value);this.root.color = false;return true;}//寻找位置RbNode myParent = this.root;while (myParent.left != null || myParent.right != null) {//新增数据 如果大于当前节点数值，则继续比较当前节点的右节点if (value > myParent.val) {if (myParent.right == null) {break;}//查看子节点myParent = myParent.right;} else if (value < myParent.val) {if (myParent.left == null) {break;}//查看子节点myParent = myParent.left;} else {return false;}}//初始化当前节点RbNode curNode = new RbNode(value);curNode.parent = myParent;if (value < myParent.val) {myParent.left = curNode;} else if (value > myParent.val) {myParent.right = curNode;} else {return false;}//修正insert_fix(curNode);//节点数量+1size++;return true;}/*** 根据经典红黑树和 2-3-4 完全对应的关系，新增节点总共分为三种场景* - 2-3-4 树 插入2-结点 (2变3)* - 2-3-4 树 插入3-结点 (3变4)* - 2-3-4 树 插入4-结点 (插入4-结点 (4分解为三个2-结点后其中一个2变3))** @param curNode*/private void insert_fix(RbNode curNode) {if (curNode == null) {return;}//父节点为空，则当前节点就是rootif (curNode.parent == null) {curNode.color = false;return;}//父节点是黑色，不需要修正. (父节点是黑色,覆盖全部 2-3-4树的2节点，部分3节点场景)if (!curNode.parent.color) {return;}//以下场景父节点颜色为红色RbNode myParent = curNode.parent;RbNode myGrandParent = curNode.parent.parent;RbNode myUncle = curNode.parent.parent.left;if (myUncle != null && myUncle.val == myParent.val) {myUncle = curNode.parent.parent.right;}//2-3-4 数 --> 4节点.(父节点和叔叔节点都是红色)if (myUncle != null && myUncle.color) {//第一步交换颜色color_flip_up(curNode.parent.parent);//1. x000。//2. 0x00。//3. 00x0。//4. 000x。//继续上溯调整insert_fix(curNode.parent.parent);return;}//2-3-4 数 --> 3节点.(叔叔节点不是红色或者不存在，父节点是红色) 假设插入节点是x,总共三种情况int min = Math.min(Math.min(curNode.val, myParent.val), myGrandParent.val);int max = Math.max(Math.max(curNode.val, myParent.val), myGrandParent.val);//1. x00。if (curNode.val == min) {//由于排除了 父节点是黑色，所以排除了 第一个0是父节点的场景，因此 只剩一种场景 第二个0是父节点.//所以先对第一和第二个0变色，再对第一个0右旋. 得到第一个0成为父节点，x成为左子节点，第二个0成为右子节点效果。color_flip_up(curNode.parent.parent);rotate_right(curNode.parent.parent);}//2. 0x0else if (curNode.val > min && curNode.val < max) {//场景1 第一个0 是祖父节点。if (curNode.parent.val < curNode.parent.parent.val) {//x左旋；x和第一个0交换颜色；x右旋rotate_left(curNode.parent);color_flip_up(curNode.parent);rotate_right(curNode.parent);}//场景2 第二个0 是祖父节点else {// x右旋；x和第一个0交换颜色；x左旋rotate_right(curNode.parent);color_flip_up(curNode.parent);rotate_left(curNode.parent);}}//3. 00xelse {//由于排除了 父节点是黑色，所以排除了 第二个0是父节点的场景，因此 只剩一种场景 第一个0是父节点.//先将第一个和第二个0 交换颜色，然后左旋第二个0color_flip_up(curNode.parent.parent);rotate_left(curNode.parent.parent);}}/*** 左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。* 左旋只影响旋转结点和其右子树的结构，把右子树的结点往左子树挪了。** @param p*/void rotate_left(RbNode p) {// 1.处理当前节点的父节点if (p.parent == null) {this.root = p.right;//1} else if (p.parent.left != null && p.parent.left.val == p.val) {p.parent.left = p.right;//1} else {p.parent.right = p.right;//1}// 2.处理历史右子节点。（当前父节点）p.right.parent = p.parent;//2RbNode rightLeftNode = p.right.left;p.right.left = p;//3// 3. 处理当前节点p.parent = p.right;//4p.right = rightLeftNode;//5// 4.处理历史右节点的左子节点if (rightLeftNode != null) {rightLeftNode.parent = p;//6}}/*** 右旋： 以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。* 右旋只影响旋转结点和其左子树的结构，把左子树的结点往右子树挪了。** @param p*/void rotate_right(RbNode p) {// 1.处理当前节点的父节点if (p.parent == null) {this.root = p.left;//1} else if (p.parent.left != null && p.parent.left.val == p.val) {p.parent.left = p.left;//1} else {p.parent.right = p.left;//1}// 2.处理历史左子节点。（当前父节点）p.left.parent = p.parent;//2RbNode leftRightNode = p.left.right;p.left.right = p;//3// 3. 处理当前节点p.parent = p.left;//4p.left = leftRightNode;//5// 4.处理历史左节点的右子节点if (leftRightNode != null) {leftRightNode.parent = p;//6}}/*** @param node*/void color_flip_up(RbNode node) {node.color = true;//子节点变黑if (node.left != null) {node.left.color = false;}if (node.right != null) {node.right.color = false;}}/*** 是否是黑色。* 注：空节点当作黑色** @param node* @return*/boolean colorBlack(RbNode node) {return node == null || !node.color;}/*** 2-3-4 树 删除key 按照key 是否在叶子节点中划分为两种场景：* 1. key 不在叶子节点中-->用key 后继键值替换key，然后删除后继键值（后继键必为某叶子结点中的最小键）。* 2. key 在叶子节点中-->直接删除目标键值（若目标键在2-结点中，删除后失去2-3-4树结构性质，要调整）。* <p>* 红黑树删除节点key 情形以删除节点的子节点情况划分3种场景* 1. key 有左右子节点-->用候机节点替换key（数值和节点关系），然后删除后继节点（删除后继节点必为情形2或者情形3？不是 1/2/3？）。* 2. key 有一个子节点-->简历子节点与 key节点的父节点的链接，然后删除key节点（key极其子节点构成3-节点，删除后不影响同构）。* 3. key 没有子节点-->直接删除key（key如果对应2-3-4树中的2-节点，则删除后失去同构，需修正。）。* <p>* ⚠️：依据BST数删除节点的规则（交换当前节点和后继绩点，然后删除后继节点）。无论删除的结点在何处，最终都会 删除一个对应于2-3-4树上的叶子结点。** @param value* @return*/public boolean remove(int value) {//find 节点RbNode curNode = find(value);if (curNode == null) {return false;}//元素数量减少1size--;//当前节点 无父节点且无孩子节点，则当前节点是跟节点且只剩唯一节点。if (curNode.parent == null && curNode.left == null && curNode.right == null) {curNode.parent = curNode.left = curNode.right = null;this.root = null;return true;}//1. 2-3-4数key 不在叶子节点中。（根据中序遍历可知: 此时当前节点一定有后继节点，且后继节点一定在叶子节点中）。if (curNode.left != null && curNode.right != null) {RbNode successorNode = findSuccessorNode(curNode);//交换数值curNode.val = successorNode.val;//指针指向调整curNode = successorNode;}//2. 2-3-4数key 在叶子节点中（直接删除目标键值然后修正2-3-4数平衡）。RbNode children = curNode.left != null ? curNode.left : curNode.right;//2-a. 红黑二叉树节点 curNode 有一个子节点（左子节点或者右子节点）。// [此种场景保证了 curNode一定是黑色，其子节点一定是红色。删除curNode后，子节点变黑即可保持红黑树性质。不需要调整]if (children != null) {//先处理父节点关系RbNode parent = curNode.parent;if (parent == null) {this.root = children;} else if (parent.left.val == curNode.val) {parent.left = children;} else {parent.right = children;}//再处理当前节点curNode.parent = curNode.left = curNode.right = null;//最后处理子节点children.parent = parent;children.color = false;}//2-b. 红黑二叉树节点 curNode 没有子节点。 此种场景最复杂，当curNode 是红色需要修正。else {//待删除的节点是黑色 则需要修复if (!curNode.color) {remove_fix(curNode);}RbNode parent = curNode.parent;if (parent != null) {//先处理父节点if (parent.left != null && curNode.val == parent.left.val) {curNode.parent.left = null;} else {curNode.parent.right = null;}//再处理当前节点curNode.parent = null;}}return true;}/*** 中序遍历，查找当前节点的后续节点（寻找继承人）** @param curNode* @return*/RbNode findSuccessorNode(RbNode curNode) {if (curNode == null) {return null;}//1. 向下搜索-> 当前节点有 右子节点if (curNode.right != null) {RbNode mySuccessorNode = curNode;while (mySuccessorNode.left != null) {mySuccessorNode = mySuccessorNode.left;}return mySuccessorNode;}//2. 向上搜索-> 当前节点没有 右子节点.RbNode parent = curNode.parent;//如果没有父节点，则当前节点是root节点，直接返回nullif (parent == null) {return null;}//如果当前节点是父节点的左子节点,则当前节点的后继节点就是 父节点if (parent.left == curNode) {return parent;}//向上搜索当前节点的父节点...中的第一个左节点while (parent.parent != null && parent.parent.right == parent) {parent = parent.parent;}return parent.parent;}/*** 删除修复。【只有当前节点是黑色才会修复】** @param curNode*/void remove_fix(RbNode curNode) {//2-3-4 树 3-节点和 4-节点 或者根节点 直接删除即可。 不需要修补逻辑//当前节点是红色 则停止修正。（删除修复操作在遇到被删除的节点是红色节点或者到达root节点时，修复操作完毕。）//需要做的处理是从兄弟节点上借调黑色的节点过来，如果兄弟节点没有黑节点可以借调的话，就只能往上追溯，将每一级的黑节点数减去一个，使得整棵树符合红黑树的定义。//删除操作的总体思想是从兄弟节点借调黑色节点使树保持局部的平衡，如果局部的平衡达到了，就看整体的树是否是平衡的，如果不平衡就接着向上追溯调整。//算法导论4情形。 vs 2-3-4 四种情形.(w 是待删除节点的兄弟节点)//删除修复操作分为四种情况(删除黑节点后)：//case 1: w是红色。[只需对当前节点父节点置红以及w节点变黑并且左旋当前节点的父节点，即可转换成下述 2-4场景]//case 2: w是黑色，且其孩子左黑右黑//case 3: w是黑色，且其孩子左红右黑。（只需对 w 和 w.left 变色，然后右旋w，即为场景4）//case 4: w是黑色，且其孩子左黑右红或者左红右红while (curNode.val != this.root.val && colorBlack(curNode)) {//待删除节点是左节点(一切为了 右边兄弟左旋).if (curNode.parent.left != null && curNode.val == curNode.parent.left.val) {RbNode w = curNode.parent.right;//case 1: w是红色。[只需对当前节点父节点置红以及w节点变黑并且左旋当前节点的父节点，即可转换成下述 2-4场景]if (w.color) {//1.w置黑w.color = false;//2. 待删除节点父节点置红curNode.parent.color = true;//3.待删除节点父节点左旋rotate_left(curNode.parent);//更新兄弟节点位置w = curNode.parent.right;}//case 2:w是黑色，且其孩子左黑右黑(w变换颜色，然后向上调整).if (colorBlack(w.left) && colorBlack(w.right)) {//此时 w 一定是黑色(反色目的是让它作为一个3-结点中的红色结点)。w.color = true;//继续向上调整[唯一一个向上调整]curNode = curNode.parent;//如果当前节点是红色 则已经平衡if (curNode.color) {break;}} else {//case 3: w是黑色，且其孩子左红右黑。（只需对 w 和 w.left 变色，然后右旋w，即为场景4）if (colorBlack(w.right)) {//w.left 置黑w.left.color = false;//w 置红w.color = true;//右旋wrotate_right(w);//调整兄弟节点w = curNode.parent.right;}//case 4: w是黑色，且其孩子左黑右红或者左红右红.//置w和curNode.parent 相同颜色w.color = curNode.parent.color;//置curNode.parent 黑色curNode.parent.color = false;//置w.right 黑色w.right.color = false;//左旋curNode.parentrotate_left(curNode.parent);//兄弟节点不存在或者兄弟节点的子节点不存在 则表示已经平衡. 另：case3和case4调整后必平衡。curNode=this.rootw = curNode.parent.right;if (w == null || (w.left == null && w.right == null)) {break;}}} else {//待删除节点是右节点RbNode w = curNode.parent.left;//case 1: w是红色。[只需对当前节点父节点置红以及w节点变黑并且左旋当前节点的父节点，即可转换成下述 2-4场景]if (w.color) {//curNode.parent 置黑curNode.parent.color = true;//w置黑w.color = false;//curNode.parent右旋rotate_right(curNode.parent);//更新兄弟节点位置w = curNode.parent.left;}//case 2:w是黑色，且其孩子左黑右黑(w变换颜色，然后向上调整).if (colorBlack(w.left) && colorBlack(w.right)) {//此时 w 一定是黑色(反色目的是让它作为一个3-结点中的红色结点)。w.color = true;//继续向上调整[唯一一个向上调整]curNode = curNode.parent;//如果当前节点是红色 则已经平衡if (curNode.color) {break;}} else {//case 3: w是黑色，且其孩子右红左黑。（只需对 w 和 w.right 变色，然后右旋w，即为场景4）if (colorBlack(w.left)) {//w.right 置黑w.right.color = false;//w 置红w.color = true;//左旋wrotate_left(w);//调整兄弟节点w = curNode.parent.left;}//case 4: w是黑色，且其孩子左红右黑或者左红右红.//置w和curNode.parent 相同颜色w.color = curNode.parent.color;//置curNode.parent 黑色curNode.parent.color = false;//置w.left 黑色w.left.color = false;//右旋curNode.parentrotate_right(curNode.parent);//兄弟节点不存在或者兄弟节点的子节点不存在 则表示已经平衡. 另：case3和case4调整后必平衡。curNode=this.rootw = curNode.parent.left;if (w == null || (w.left == null && w.right == null)) {break;}}}}// while结束要么是case3/case4调整后已平衡 x被被置为root后主动退出，// 要么是case1/case2 x为红。若为前者无需此句(此时的root一定是黑的)// 若为后者，说明此时的x结点是原3-结点或4-结点出借的结点，如果还保持红色，// 将无法脱离原3-结点或4-结点 (2-3-4树)，因此必须置黑。// 此句也可以写成这样: if(x != root) x.color = BLACK//curNode.color = false;}public RbNode find(int value) {RbNode myParent = this.root;while (myParent != null) {if (value > myParent.val) {if (myParent.right == null) {return null;}myParent = myParent.right;} else if (value < myParent.val) {if (myParent.left == null) {return null;}myParent = myParent.left;} else {return myParent;}}return null;}/*** 广度优先遍历*/public void printTree() {Queue<RbNode> queue = new LinkedList<>();if (this.root == null) {return;}//首次queue.add(this.root);//开始遍历while (!queue.isEmpty()) {//遍历int length = queue.size();for (int i = 0; i < length; i++) {//从队尾取出数据RbNode n = queue.poll();System.out.print((n.color ? "R" : "B") + ":" + n.val + "\t");//从队首增加if (n.left != null) {queue.add(n.left);}if (n.right != null) {queue.add(n.right);}}System.out.println();}}public static void main(String[] args) {RBTree rbTree = new RBTree();System.out.println(rbTree.insert(1));System.out.println(rbTree.insert(2));System.out.println(rbTree.insert(3));System.out.println(rbTree.insert(4));System.out.println(rbTree.insert(5));
//        rbTree.printTree();System.out.println(rbTree.insert(6));
//        rbTree.printTree();System.out.println(rbTree.insert(7));
//        rbTree.printTree();System.out.println(rbTree.insert(8));
//        rbTree.printTree();System.out.println(rbTree.insert(9));
//        rbTree.printTree();System.out.println(rbTree.insert(10));
//        rbTree.printTree();System.out.println("###### 开始删除操作 ######");for (int i = 10; i >= 1; i--) {if (i == 1) {System.out.println(i);}System.out.println(rbTree.remove(i));rbTree.printTree();}}
}

参考（如有冒犯请联系删除）

文中部分定义和图片参考链接

这篇关于从2-3-4树开始理解红黑二叉树（JAVA代码手撸版）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1079424。

相关文章

JVM 的类初始化机制

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时，有没有考虑过 JVM 是如何把静态的字节码（byte code）转化为运行时对象的呢，这个问题看似简单，但清楚的同学相信也不会太多，这篇文章首先介绍 JVM 类初始化的机制，然后给出几个易出错的实例来分析，帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段，分别是：loading 、Linking、initialization
阅读更多...
Spring Security 基于表达式的权限控制

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权，允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true （Spring security默认会带有ROLE_前缀）,去
阅读更多...
浅析Spring Security认证过程

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程，特意画了如下的类图，包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口，接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti
阅读更多...
Spring Security--Architecture Overview

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类，它们之间的依赖，构建起了整个框架。想要理解整个架构，最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文（security context）的信息。当前操作的用户是谁，该用户是否已经被认证，他拥有哪些角色权限…这些都被保
阅读更多...
Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
Java架构师知识体认识

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物
阅读更多...
Java进阶13讲__第12讲_1/2

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory
阅读更多...
认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
JAVA智听未来一站式有声阅读平台听书系统小程序源码

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来，一站式有声阅读平台听书系统 🌟&nbsp;开篇：遇见未来，从“智听”开始 在这个快节奏的时代，你是否渴望在忙碌的间隙，找到一片属于自己的宁静角落？是否梦想着能随时随地，沉浸在知识的海洋，或是故事的奇幻世界里？今天，就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统，它正悄悄改变着我们的阅读方式，让未来触手可及！ 📚&nbsp;第一站：海量资源，应有尽有 走进“智听
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2