红黑树相当于4阶b树
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);
}
/**
* 1 添加的节点 都是添加在叶子节点上 度为0
* 2 添加的节点默认是红色
* 3 添加的节点父节点是black 那么就无需关注
* 4 添加的节点父节点是red 当uncle节点为black的时候
* 当添加的节点是父节点同侧的时候 将grand染红 parent 染黑 然后对grand左旋或者右旋
* 当添加的节点与父节点异侧的时候 将parent 染红 grand染红 自己染黑 然后对rl lr处理
* 5 当添加的节点父节点是red 当uncle节点为red的时候
* 证明 grand是black 有3个节点了已经 2-3-4树 最多3个 所以需要向上合并 节点进行分裂
* 于是 将parenth和uncle染黑 grand染红向上合并
* @param node
*/
@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);
}
}
/**
* B 树中 真正被删除的就是叶子节点
* 1 删除的节点是红节点 直接删除 无需处理 对应b树 节点>1
* 2 删除的节点是black节点
* 分为 black叶子节点 带一个red节点的black节点 带2个red节点的black节点
* 当为带一个red节点的black节点 将子节点染黑
* 当为带2个red节点的black节点 会找到他的替代品 所以无需关注
* 当为black叶子节点的时候 看旁边节点是否能借 借完是否需要下溢
*
* 1 当sibling为black的时候
* 当带一个red节点的时候 进行旋转 继承parent的颜色 并且节点左右变黑 这时候看需要旋转几次 看图就能明白
* 当不带red节点的时候 就看父节点是红是黑 是红的话 将sibling染红 父节点染黑
* 如果父节点也是黑的 父节点就会下溢
* 2 当sibling为red的时候 将silbling旋转 自己染黑 父节点染红 就又回到了上面的情况
*
* @param node
*/
@Override
protected void afterRemove(Node<E> node) {
// 如果删除的节点是红色
// 或者 用以取代删除节点的子节点是红色
if (isRed(node)) {
return;
}
Node<E> replace = node.left!=null?node.left:node.right;
if(replace!=null&&node.replaceFlag){
black(replace);
return;
}
Node<E> parent = node.parent;
// 删除的是根节点
if (parent == null) return;
// 删除的是黑色叶子节点【下溢】
// 判断被删除的node是左还是右
boolean left;
if(node.uploadFlag){
left = node.isLeftChild();
}else{
left = parent.left == null;
}
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);
red(sibling);
if (parentBlack) {
parent.uploadFlag = true;
afterRemove(parent);
}
black(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);
red(sibling);
if (parentBlack) {
parent.uploadFlag = true;
afterRemove(parent);
}
black(parent);
} else { // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
// 兄弟节点的左边是黑色，兄弟要先旋转
if (isBlack(sibling.left)) {
rotateLeft(sibling);
sibling = parent.left;
}
color(sibling, colorOf(parent));
black(sibling.left);
black(parent);
rotateRight(parent);
}
}
}
// protected void afterRemove(Node<E> node, Node<E> replacement) {
// // 如果删除的节点是红色
// if (isRed(node)) return;
//
// // 用以取代node的子节点是红色
// if (isRed(replacement)) {
// black(replacement);
// 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, 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)) { // 兄弟节点是红色
// 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, null);
// }
// } 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();
}
}
}http://520it.com/binarytrees/ 推荐用这个链接 添加后一个个删除 自己先过一遍删除过程再一个个验证结果
static void test4() {
Integer data[] = new Integer[] {
55, 87, 56, 74, 96, 22, 62, 20, 70, 68, 90, 50
};
RBTree<Integer> rb = new RBTree<>();
for (int i = 0; i < data.length; i++) {
rb.add(data[i]);
}
BinaryTrees.println(rb);
for (int i = 0; i < data.length; i++) {
rb.remove(data[i]);
System.out.println("---------------------------------------");
System.out.println("【" + data[i] + "】");
BinaryTrees.println(rb);
}
}
public static void main(String[] args) {
test4();
}