目录
错误示范
上述之中是存在null节点的,比如说上面的38的右边就是一个null,25 74 78 86 90下面的就是两个null,进而得知上面的叶子节点的不同之处,一定要注意null的存在.
所以上面的那个不是红黑树,注意空节点(null)的存在,一定要注意假的博客,有些标题很牛逼,但是可能就是错误的.
红黑树的等价变换
◼ 红黑树 和 4阶B树（2-3-4树）具有等价性
◼ BLACK 节点与它的 RED 子节点融合在一起，形成1个B树节点
◼ 红黑树的 BLACK 节点个数 与 4阶B树的节点总个数 相等
◼ 网上有些教程:用2-3树与红黑树进行类比，这是极其不严谨的，2-3树并不能完美匹配红黑树的所有情况
◼ 注意：因为PPT界面空间有限，后面展示的红黑树都会省略 NULL 节点
红黑树VS2-3-4树
◼ 思考：如果上图最底层的 BLACK 节点是不存在的，在B树中是什么样的情形？
整棵B树只有1个节点，而且是超级节点
几个英语单词
辅助函数
package com.mj.tree;
import java.util.Comparator;
public class RBTree<E> extends BBST<E> {
private static final boolean RED = false;
private static final boolean BLACK = true;
public RBTree() {
this(null);
}
public RBTree(Comparator<E> comparator) {
super(comparator);
}
@Override
protected void afterAdd(Node<E> node) {
Node<E> parent = node.parent;
// 添加的是根节点 或者 上溢到达了根节点
if (parent == null) {
black(node);
return;
}
// 如果父节点是黑色，直接返回
if (isBlack(parent)) return;
// 叔父节点
Node<E> uncle = parent.sibling();
// 祖父节点
Node<E> grand = red(parent.parent);
if (isRed(uncle)) { // 叔父节点是红色【B树节点上溢】
black(parent);
black(uncle);
// 把祖父节点当做是新添加的节点
afterAdd(grand);
return;
}
// 叔父节点不是红色
if (parent.isLeftChild()) { // L
if (node.isLeftChild()) { // LL
black(parent);
} else { // LR
black(node);
rotateLeft(parent);
}
rotateRight(grand);
} else { // R
if (node.isLeftChild()) { // RL
black(node);
rotateRight(parent);
} else { // RR
black(parent);
}
rotateLeft(grand);
}
}
@Override
protected void afterRemove(Node<E> node) {
// 如果删除的节点是红色
// 或者 用以取代删除节点的子节点是红色
if (isRed(node)) {
black(node);
return;
}
Node<E> parent = node.parent;
// 删除的是根节点
if (parent == null) return;
// 删除的是黑色叶子节点【下溢】
// 判断被删除的node是左还是右
boolean left = parent.left == null || node.isLeftChild();
Node<E> 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);
}
} 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)) { // 兄弟节点是红色
black(sibling);
red(parent);
rotateRight(parent);
// 更换兄弟
sibling = parent.left;
}
// 兄弟节点必然是黑色
if (isBlack(sibling.left) && isBlack(sibling.right)) {
// 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
boolean parentBlack = isBlack(parent);
black(parent);
red(sibling);
if (parentBlack) {
afterRemove(parent);
}
} else { // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
// 兄弟节点的左边是黑色，兄弟要先旋转
if (isBlack(sibling.left)) {
rotateLeft(sibling);
sibling = parent.left;
}
color(sibling, colorOf(parent));
black(sibling.left);
black(parent);
rotateRight(parent);
}
}
}
private Node<E> color(Node<E> node, boolean color) {
if (node == null) return node;
((RBNode<E>)node).color = color;
return node;
}
private Node<E> red(Node<E> node) {
return color(node, RED);
}
private Node<E> black(Node<E> node) {
return color(node, BLACK);
}
private boolean colorOf(Node<E> node) {
return node == null ? BLACK : ((RBNode<E>)node).color;
}
private boolean isBlack(Node<E> node) {
return colorOf(node) == BLACK;
}
private boolean isRed(Node<E> node) {
return colorOf(node) == RED;
}
@Override
protected Node<E> createNode(E element, Node<E> parent) {
return new RBNode<>(element, parent);
}
private static class RBNode<E> extends Node<E> {
boolean color = RED;
public RBNode(E element, Node<E> parent) {
super(element, parent);
}
@Override
public String toString() {
String str = "";
if (color == RED) {
str = "R_";
}
return str + element.toString();
}
}
}
添加
构建红黑树的时候,心中一定要有B树.先要进行构建一个B树之后才能够进行构建一个红黑树.
◼ 已知
B树中，新元素必定是添加到叶子节点中
4阶B树所有节点的元素个数 x 都符合 1 ≤ x ≤ 3
◼ 建议新添加的节点默认为 RED ，这样能够让红黑树的性质尽快满足（性质 1、2、3、5 都满足，性质 4 不一定）RED节点的parent都是BLANK.
◼ 如果添加的是根节点，染成 BLACK 即可.
添加的所有情况
红黑树之中没有平衡因子这个概念的,就是不存在相应的一个失衡的过程,只要维护好红黑树的五条性质就好了.
添加 - 修复性质4 - LL\RR
其中的六种情况不管,只关心其中的两种情况.
◼ 判定条件： uncle 不是 RED
1. parent 染成 BLACK ， grand 染成 RED
2. grand 进行单旋操作
LL：右旋转
RR：左旋转
在B树之中相应的黑色节点是相应的父节点,所以指出来的一般都是相应的红色的节点.
添加 – 修复性质4 – LR\RL
添加 – 修复性质4 – 上溢 – LL
上面的25是需要将它看成是新添加的节点进行看待,如果要是上溢的话,之间进行一个染色的操作,是不需要旋转的操作.
添加 – 修复性质4 – 上溢 – LL
添加 – 修复性质4 – 上溢 – LR
添加 – 修复性质4 – 上溢 – RL
本文含有隐藏内容，请 开通VIP 后查看