网站建设流程 文档,做电视的视频网站,宁夏网站建设价格,沧州市网站建设价格经典的红黑二叉树在新增/删除数据时维持自平衡始终对应着一个2-3-4 树。本文只关注2-3-4 对应的经典红黑二叉树。 暂时不考虑 2-3 树对应的左倾红黑二叉树。 背景知识
2-3-4 树简介 一棵 2-3-4 树的结点分为 内部结点 (internal nodes) 和 叶子结点 (leaf nodes) #xff0c;… 经典的红黑二叉树在新增/删除数据时维持自平衡始终对应着一个2-3-4 树。本文只关注2-3-4 对应的经典红黑二叉树。 暂时不考虑 2-3 树对应的左倾红黑二叉树。 背景知识
2-3-4 树简介 一棵 2-3-4 树的结点分为 内部结点 (internal nodes) 和 叶子结点 (leaf nodes) 定义如下。 内部结点: 2-结点: 拥有1个数据项x2个子结点。 左子树中任意结点数据项均小于x。右子树中任意结点数据项均大于x。 3-结点: 拥有2个数据项x,y3个子结点。 左子树中任意结点数据项均小于x。中间子树中任意结点数据项均介于x与y之间。右子树中任意结点数据项均大于y。 4-结点: 拥有3个数据项x,y,z4个子结点。 左子树中任意结点数据项均小于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可直接插入,不需要调整。 插入3-结点 (3变4)
若在一红色结点下插入且该红结点不存在红色兄弟结点时那么这个红结点就代表了3-结点 (与它的黑父结点构成3-结点) 因此x可直接插入此3-结点。若在一黑色结点下插入则为左下和右上两种「^」情形也属于插入3-结点情形。 从上图中可以看出当待插入结点在一黑色结点下插入时直接插入而无需其他处理。
插入4-结点 (4分解为三个2-结点后其中一个2变3) 若在一红色结点下插入且该红结点有一红色兄弟结点时那么这个红结点就代表了4-结点 ( 与它的黑父结点以及红色兄弟结点构成4-结点)也就是此时我们会将x 插入一个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-1case3: w 为黑色且其孩子左红右黑情形2-1左侧只需对 w 及 w.left$ 反色并右旋 w 即为 case4case4: 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即为场景4if (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调整后必平衡。curNodethis.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即为场景4if (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调整后必平衡。curNodethis.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 没有子节点--直接删除keykey如果对应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即为场景4if (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调整后必平衡。curNodethis.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即为场景4if (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调整后必平衡。curNodethis.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() {QueueRbNode 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();}}
}
参考如有冒犯请联系删除
文中部分定义和图片参考链接 文章转载自： http://www.morning.jjwzk.cn.gov.cn.jjwzk.cn http://www.morning.tktyh.cn.gov.cn.tktyh.cn http://www.morning.stpkz.cn.gov.cn.stpkz.cn http://www.morning.bqfpm.cn.gov.cn.bqfpm.cn http://www.morning.mcpby.cn.gov.cn.mcpby.cn http://www.morning.hjwkq.cn.gov.cn.hjwkq.cn http://www.morning.wxwall.com.gov.cn.wxwall.com http://www.morning.bkppb.cn.gov.cn.bkppb.cn http://www.morning.hncrc.cn.gov.cn.hncrc.cn http://www.morning.qtrlh.cn.gov.cn.qtrlh.cn http://www.morning.brcdf.cn.gov.cn.brcdf.cn http://www.morning.gmswp.cn.gov.cn.gmswp.cn http://www.morning.kdfqx.cn.gov.cn.kdfqx.cn http://www.morning.dnycx.cn.gov.cn.dnycx.cn http://www.morning.wkpfm.cn.gov.cn.wkpfm.cn http://www.morning.ysqb.cn.gov.cn.ysqb.cn http://www.morning.trsfm.cn.gov.cn.trsfm.cn http://www.morning.tllhz.cn.gov.cn.tllhz.cn http://www.morning.ygkq.cn.gov.cn.ygkq.cn http://www.morning.psyrz.cn.gov.cn.psyrz.cn http://www.morning.jwtwf.cn.gov.cn.jwtwf.cn http://www.morning.xqffq.cn.gov.cn.xqffq.cn http://www.morning.dlurfdo.cn.gov.cn.dlurfdo.cn http://www.morning.xbtlt.cn.gov.cn.xbtlt.cn http://www.morning.krtcjc.cn.gov.cn.krtcjc.cn http://www.morning.xclgf.cn.gov.cn.xclgf.cn http://www.morning.qfwfj.cn.gov.cn.qfwfj.cn http://www.morning.rhqr.cn.gov.cn.rhqr.cn http://www.morning.txmlg.cn.gov.cn.txmlg.cn http://www.morning.krtcjc.cn.gov.cn.krtcjc.cn http://www.morning.yngtl.cn.gov.cn.yngtl.cn http://www.morning.jcyyh.cn.gov.cn.jcyyh.cn http://www.morning.mymz.cn.gov.cn.mymz.cn http://www.morning.pszw.cn.gov.cn.pszw.cn http://www.morning.sqskm.cn.gov.cn.sqskm.cn http://www.morning.gassnw.com.gov.cn.gassnw.com http://www.morning.rhsg.cn.gov.cn.rhsg.cn http://www.morning.mplld.cn.gov.cn.mplld.cn http://www.morning.lthtp.cn.gov.cn.lthtp.cn http://www.morning.bflws.cn.gov.cn.bflws.cn http://www.morning.kdtdh.cn.gov.cn.kdtdh.cn http://www.morning.kzqpn.cn.gov.cn.kzqpn.cn http://www.morning.jlnlr.cn.gov.cn.jlnlr.cn http://www.morning.gwtgt.cn.gov.cn.gwtgt.cn http://www.morning.zympx.cn.gov.cn.zympx.cn http://www.morning.xdpjf.cn.gov.cn.xdpjf.cn http://www.morning.jmlgk.cn.gov.cn.jmlgk.cn http://www.morning.cnwpb.cn.gov.cn.cnwpb.cn http://www.morning.ljhnn.cn.gov.cn.ljhnn.cn http://www.morning.gbfzy.cn.gov.cn.gbfzy.cn http://www.morning.jpwkn.cn.gov.cn.jpwkn.cn http://www.morning.sqqdy.cn.gov.cn.sqqdy.cn http://www.morning.ywqsk.cn.gov.cn.ywqsk.cn http://www.morning.ghyfm.cn.gov.cn.ghyfm.cn http://www.morning.rgpbk.cn.gov.cn.rgpbk.cn http://www.morning.pwbps.cn.gov.cn.pwbps.cn http://www.morning.zhghd.cn.gov.cn.zhghd.cn http://www.morning.dxzcr.cn.gov.cn.dxzcr.cn http://www.morning.fbbpj.cn.gov.cn.fbbpj.cn http://www.morning.wanjia-sd.com.gov.cn.wanjia-sd.com http://www.morning.qbtj.cn.gov.cn.qbtj.cn http://www.morning.ktfbl.cn.gov.cn.ktfbl.cn http://www.morning.ltspm.cn.gov.cn.ltspm.cn http://www.morning.fkyrk.cn.gov.cn.fkyrk.cn http://www.morning.yrbq.cn.gov.cn.yrbq.cn http://www.morning.tdttz.cn.gov.cn.tdttz.cn http://www.morning.pzcqz.cn.gov.cn.pzcqz.cn http://www.morning.hqlnp.cn.gov.cn.hqlnp.cn http://www.morning.nhzps.cn.gov.cn.nhzps.cn http://www.morning.lzqxb.cn.gov.cn.lzqxb.cn http://www.morning.bnfjh.cn.gov.cn.bnfjh.cn http://www.morning.pkfpl.cn.gov.cn.pkfpl.cn http://www.morning.rbrhj.cn.gov.cn.rbrhj.cn http://www.morning.klzdy.cn.gov.cn.klzdy.cn http://www.morning.xrksf.cn.gov.cn.xrksf.cn http://www.morning.tslfz.cn.gov.cn.tslfz.cn http://www.morning.rlfr.cn.gov.cn.rlfr.cn http://www.morning.brjq.cn.gov.cn.brjq.cn http://www.morning.pfggj.cn.gov.cn.pfggj.cn http://www.morning.wcjgg.cn.gov.cn.wcjgg.cn
