b树 数据结构 java 04

红黑树

也是一种子自平衡的二叉搜索树，也叫平衡二叉B树

必须满足以下 5 条性质

1.节点是 RED 或者 BLACK2.根节点是 BLACK3.叶子节点 （外部节点，空）都是 BLACK4.RED 节点的子节点都是 BLACK

从根节点到 叶子节点 的所有 路径上不能2 个连续的 RED 节点 5.从任一节点到 叶子节点 的 所有路径都包含相同数目BLACK节点6.度为0和度为1的节点都需要变成度为2的节点，即加空节点null，空节点默认为黑色，例如17变成度为2，加上两个空（写代码时候不用把null节点加进去，为了配合红黑树而假想出来的）

红黑树的等价变换：黑色节点与红色子节点合在一起变成的AVL树

红黑树 和 4阶B树（ 2-3-4树）具有等价性BLACK 节点与它的 RED 子节点融合在一起，形成 1个B树节点红黑树的 BLACK 节点个数 与 4阶B树的节点总个数 相等后展示的红黑树都会省略 NULL 节点

一、添加操作

B树中，新元素必定是添加到叶子节点 4阶B树所有节点的元素个数 x 都符合 1 ≤ x≤ 3 建议新添加的节点默认为 RED ，这样能够让红黑树的性质 尽快满足（1、2、3、5 都满足，性质 4 不一定） 如果添加的是根节点，染成 BLACK 即可 如下图所示，添加的叶子节点只可以加入如下四种情况中：[17红,25黑,33红]、[46黑,50红]、[72红,76黑]、[88黑]这四种中 其中节点可以加在17左右，33左右，46左，50左右，72左右，76右，88左右这12个地方，分为以下三种情况进行添加

1.1有 4 种情况满足红黑树的性质 4 ：parent 为 BLACK

同样也满足 4阶B树的性质因此不用做任何额外处理如下图：添加40，78，82，90

1.2有 8 种情况不满足红黑树的性质 4 ：parent 为 RED （ Double Red）

如下图：分为两大类

uncle（叔父节点）为red—>前四个节点，10，20，30，36uncle节点不为red（null默认为black节点）—>后四个节点，48，52，60，74

2.1 uncle不是red：分为LL、RR、LR、RL四种情况修复性质4

2.1.1 LL/RR修复情况步骤1染色步骤2旋转

染色：如下图所示，由于红黑树合并为B树是BLACK节点与其RED节点合并，而50是红色节点不会和新添加的叶子节点合并，所以50变为BLACK，呢么为了其【46，50，52】变为B树节点的话，46需要变红（也是因为黑色和红色合并，若46也为黑，呢么需要单独拎出去）旋转：因为若不旋转，38和46都是红色，不会连在一起。所以LL情况进行右旋转，RR情况进行左旋转即：

染色：parent染成BLACK，grand染成RED旋转：grand进行单旋操作—>LL情况进行右旋转，RR情况进行左旋转

2.1.2 LR/RL修复情况步骤1染色步骤2旋转

AVL树中的LR/RL情况需要进行双旋操作，考虑RL情况【46，50，48】最终让48成为根节点，46和50成为48的子节点，所以48变为黑色，46变为红色具体操作：

自己染成BLACK，grand染成RED进行双旋转操作  LR：parent左旋转，grand右旋转  RL：parent右旋转，grand左旋转

2.2 uncle是red：分为LL、RR、LR、RL四种情况上溢修复性质4

2.2.1 考虑LL的上溢情况

必然发生上溢的情况，因为已经有三个元素，再加入必上溢在此取grand即25的节点和父节点合并，那么parent和uncle必须变成黑色，才可以和添加的叶子节点合并同时向上合并的节点25染成红色，作为新添加的节点一样，也就是像递归一样持续向上具体操作：  parent、uncle染成BLACK  grand染成RED，当作是新添加的节点进行处理，向上合并  grand持续向上合并时，可能继续发生上溢，若上溢持续到根节点，只需要将根节点染成BLACK

2.2.2 RR、RL、LR上溢

RR、RL、LR的情况与LL分析一样，具体操作也是一样的

3.1 详细代码

parent：父节点sibling：兄弟节点uncle：叔父节点（parent的兄弟）grand：祖父节点（parent的父节点）红黑树节点的数据结构

private static final boolean RED = false;

private static final boolean BLACK = true;

private static class RBNode extends Node {

boolean color = RED; //默认叶子节点为RED

public RBNode(E element, Node parent) {

super(element, parent);

}

}

红黑树的常用封装方法：一个节点是否为红色、黑色；设置一个节点的颜色

// 设置一个节点的颜色为新颜色

private Node color(Node node, boolean color) {

if (node == null) return node;

((RBNode)node).color = color;

return node;

}

// 设置该节点为红色

private Node red(Node node) {

return color(node, RED);

}

// 设置该节点为黑色

private Node black(Node node) {

return color(node, BLACK);

}

// 获取一个节点的颜色，由于颜色用布尔类型存储，所以返回布尔值

private boolean colorOf(Node node) {

return node == null ? BLACK : ((RBNode)node).color;

}

// 一个节点是否为黑色

private boolean isBlack(Node node) {

return colorOf(node) == BLACK;

}

// 一个节点是否为红色

private boolean isRed(Node node) {

return colorOf(node) == RED;

}

@Override

protected Node createNode(E element, Node parent) {

return new RBNode<>(element, parent);

}

BinaryTree中添加判断左孩子、右孩子、返回兄弟节点的方法

public boolean isLeftChild() {

return parent != null && this == parent.left;

}

public boolean isRightChild() {

return parent != null && this == parent.right;

}

public Node sibling() {

if (isLeftChild()) {

return parent.right;

}

if (isRightChild()) {

return parent.left;

}

return null;

}

添加代码

protected void afterAdd(Node node) {

Node parent = node.parent;

// 添加的是根节点 或者 上溢到达了根节点

if (parent == null) {

black(node);

return;

}

// 1.如果父节点是黑色，直接返回

if (isBlack(parent))

return;

// 叔父节点

Node uncle = parent.sibling();

// 祖父节点

Node grand = parent.parent;

// 2.1 叔父节点是红色

if (isRed(uncle)) { // 叔父节点是红色【B树节点上溢】

black(parent);

black(uncle);

// 把祖父节点当做是新添加的节点

afterAdd(grand);

return;

}

// 2.2叔父节点不是红色

if (parent.isLeftChild()) { // L

if (node.isLeftChild()) { // LL

black(parent);

red(grand);

rotateRight(grand);

} else { // LR

black(node);

rotateLeft(parent);

rotateRight(grand);

}

} else { // R

if (node.isLeftChild()) { // RL

black(node);

red(grand);

rotateRight(parent);

rotateLeft(grand);

} else { // RR

black(parent);

red(grand);

rotateLeft(grand);

}

}

}

2.删除操作

B树中，最后真正被删除的元素都在叶子节点中

2.1 删除的情况分析

2.1.1 是红色节点：直接删除不用任何处理

2.1.2 是黑色节点的三种情况

1 拥有两个红色节点的BLACK节点

不可能被直接删除，因为会找到它的子节点替代删除，因此不考虑这种情况 2 拥有一个红色节点的黑色节点3 是黑色叶子节点

2.2 针对2.1.2的2、3情况的分析

2.2.1 拥有一个红色节点的黑色节点：46和76

在二叉搜索树中删除度为1的节点，找到它的子节点取代它判定条件应与颜色挂钩，不能用度为1或0来找到它，这样会很好概括所有情况判定条件：用以替代的子节点是红色处理操作：将替代的子节点染成 BLACK 即可保持红黑树性质

2.2.2 删除黑色叶子节点

(1)只有一个根节点(2)兄弟为黑色

兄弟节点有至少一个红节点兄弟节点没有红节点 (3)兄弟为红色

（1）只有一个跟节点的情况

直接删除即可

（2）兄弟为黑色

首先从二叉搜索树角度删除88，直接去掉即可；但这种情况在B树中叫做下溢，因为四阶B树要求一个节点至少存储一个元素，而现在存储0个元素，所以是下溢在B树中解决下溢的情况，首先考虑兄弟节点可不可以借，可以借就旋转，不可以借，父节点下来合并再在红黑树角度看，兄弟节点必须有红色子节点才可以借给它，否则两个黑色不会在同一行并且兄弟节点必须为黑色（因为若兄弟节点为红色，红色必在父节点中）

a. 兄弟节点有至少一个红节点具体操作

进行旋转操作：如【80，76，78】为LR，先76左旋，再80右旋旋转之后的中心节点继承 parent 的颜色，即原先位置的节点颜色不变旋转之后的左右节点染为 BLACK若有两个红色节点，如第三列图，选【80，76，72】为LL，方便操作，即80右旋

b. 兄弟节点没有红节点具体操作

首先考虑如果在B树中，删除88，兄弟节点76没有多余元素借，那么88的父节点80下移与76合并

针对于红黑树，其实就是兄弟节点sibling【76】 染成 RED 、父节点parent【80】 染成 BLACK，即可修复，（如第一列图，80变为黑色，那么和55不能合并，下移一层，76变为红色，那么和80就合并为一层） 其次抛开颜色而言，如果父节点只有一个元素，下移合并，父节点那层也会发生下溢的情况，呢么把该父节点也当作被删除的节点，递归调用删除之后的方法即可所以加上颜色的判断，如果不会发生下溢，那么父节点必为红色；如果发生下溢，父节点必为黑色

（3）兄弟为红色

删除88，但它的兄弟节点其实是55为红色的情况站在B树角度看，删除88，88的位置产生下溢，那么还得看兄弟节点76能不能借在红黑树角度看，76拿下来较麻烦，因为76不是88的兄弟节点，88的兄弟是55，也就是说76是88的兄弟的儿子，需要先拿到兄弟再拿到儿子，看它能不能借东西给你，换了一层关系，所以较为复杂现在考虑的就是兄弟节点是红色，实则能借东西给它的是兄弟的儿子那么强制让兄弟的孩子作它的兄弟，又回到了黑兄弟的情况，即可套用上面（2）的逻辑现在需要解决怎么让76作为88的兄弟，在AVL树中实则就是LL情况【80，55，46】，让80右旋转，那么80的左边指向76；那么在红黑树角度（加入颜色），实质就是让88的父节点变成红色，兄弟染成黑色，进行旋转（即下图第一行第一个到第二个是旋转、变色，再到第三个图就是删除88）

2.3 总结

1.删除红色叶子节点，直接删除，不用其他处理2.删除黑色节点

2.1拥有一个红色节点，将替代的子节点染成 BLACK 即可保持红黑树性质2.2没有红色节点（即删除黑色叶子节点），会出现下溢

2.2.1兄弟节点为黑色，且有至少一个红节点，借它一个红的2.2.2兄弟节点为黑色，且没有红节点，父节点下移合并

2.2.2.1父节点为红色下移2.2.2.2父节点为黑色，那么父节点当作被删除的节点再回调方法 2.2.3兄弟节点为红色，强制让兄弟的孩子作它的兄弟，又回到了兄弟节点为黑色的情况

2.4 具体代码

protected void afterRemove(Node node, Node replacement) {

// 如果删除的节点是红色

if (isRed(node)) return;

// 用以取代node的子节点是红色

if (isRed(replacement)) {

black(replacement);

return;

}

Node parent = node.parent;

// 删除的是根节点

if (parent == null) return;

// 删除的是黑色叶子节点【下溢】

// 判断被删除的node是左还是右

/**

* Node sibling = node.sibling() 其实获取不到

* 因为可以拿到 node.parent，但是 node.parent的 left 或 right 已经不指向它了

*/

boolean left = parent.left == null || node.isLeftChild(); // 或的右边是考虑删除是黑节点回调时候，它的父节点的left还在，所以不为空，用后者来判断

Node sibling = left ? parent.right : parent.left;

if (left) { // 被删除的节点在左边，兄弟节点在右边

if (isRed(sibling)) { // 兄弟节点是红色

black(sibling);

red(parent);

rotateLeft(parent);

// 更换兄弟

sibling = parent.right;

}

// 兄弟节点必然是黑色

if (isBlack(sibling.left) && isBlack(sibling.right)) {

// 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并

boolean parentBlack = isBlack(parent);

black(parent);

red(sibling);

if (parentBlack) {

afterRemove(parent, null);

}

} else { // 兄弟节点至少有1个红色子节点，向兄弟节点借元素

// 兄弟节点的左边是黑色，兄弟要先旋转

if (isBlack(sibling.right)) {

rotateRight(sibling);

sibling = parent.right;

}

color(sibling, colorOf(parent));

black(sibling.right);

black(parent);

rotateLeft(parent);

}

} else { // 被删除的节点在右边，兄弟节点在左边

if (isRed(sibling)) { // 兄弟节点是红色 --> 先转成黑色 后面写黑色节点代码 类似先处理删除度为2的情况，再删除度为0或1的

black(sibling);

red(parent);

rotateRight(parent);

// 更换兄弟

sibling = parent.left; // 即实现了强制将原先兄弟节点的孩子作为兄弟

}

// 兄弟节点必然是黑色

if (isBlack(sibling.left) && isBlack(sibling.right)) { // black_88 or red_88

// 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并 // black_86 black_90 black_86 black_90

black(parent);

red(sibling);

if (isBlack(parent)) { // 如果父节点为黑色，并且向下合并，那么父节点也出现下溢情况，所以把该节点当作被删除的节点回调方法

afterRemove(parent, null);

}

} else { // 兄弟节点至少有1个红色子节点，向兄弟节点借元素

// 兄弟节点的左边是黑色，兄弟要先旋转

if (isBlack(sibling.left)) {

rotateLeft(sibling);

sibling = parent.left;

}

color(sibling, colorOf(parent));

black(sibling.left);

black(parent);

rotateRight(parent);

}

}

}

相关文章