/**
* @author klr
* @create 2020-08-29-21:58
*/
public class RedBlackTree<K extends Comparable<K>, V> {
//定义红黑色
private static final boolean RED = false;
private static final boolean BLACK = true;
//定义根节点
private RBNode root;
public RBNode getRoot() {
return root;
}
/**
* 围绕p点左旋
* pf pf
* / /
* p pr(r)
* / \ / \
* pl pr(r) p rr
* / \ / \
* rl rr pl rl
*
* @param p
*/
public void leftRotate(RBNode p) {
if (p != null) {
RBNode r = p.right;//先记录r的信息
p.right = r.left;//r.left为不为null无所谓
if (r.left != null) {
r.left.parent = p;//rl的父节点指向p了
}
r.parent = p.parent;
if (p.parent == null) {
//此时表明p为根节点，旋转后，r称为根节点}
root = r;
} else if (p.parent.left == p) {
//说明p为pf的左节点
p.parent.left = r;//把pf指向r
} else {
p.parent.right = r;
}
r.left = p;
p.parent = r;
}
}
/**
* 右旋为左旋的镜像
* @param p
*/
public void rightRotate(RBNode p) {
if (p != null) {
RBNode l = p.left;//先记录r的信息
p.left = l.right;//r.left为不为null无所谓
if (l.right != null) {
l.right.parent = p;//rl的父节点指向p了
}
l.parent = p.parent;
if (p.parent == null) {
//此时表明p为根节点，旋转后，r称为根节点}
root = l;
} else if (p.parent.right == p) {
//说明p为pf的左节点
p.parent.right = l;//把pf指向r
} else {
p.parent.left = l;
}
l.right = p;
p.parent = l;
}
}
//新增结点
public void put(K key, V value) {
if (key == null) {
throw new NullPointerException();
}
RBNode t = this.root;
//先判断是否有根节点
if (t == null) {
this.root = new RBNode<>(key, (value == null ? key : value), null);
return;
}
//寻找插入位置，定义双亲指针
RBNode parent;
int cmp;
//已有根节点后
do {
parent=t;
cmp = key.compareTo((K) t.getKey());
if (cmp < 0) {
//key小于结点的key说明往左边走
t = t.getLeft();
} else if (cmp > 0) {
t = t.getRight();
} else {
//key相等时替换原来的value值
t.setValue(value == null ? key : value);
return;
}
} while (t != null);
//此时parent为要插入的key结点的父节点，t为空
RBNode<K, Object> e = new RBNode<>(key, (value == null ? key : value), parent);
//别忘了让父节点指向插入的新节点
if (cmp < 0) {
parent.setLeft(e);
} else {
parent.setRight(e);
}
//插入完决定是否旋转
fixAfterPut(e);
}
public boolean color(RBNode node) {
return node == null ? BLACK : node.color;
}
public RBNode parentOf(RBNode node) {
return node != null ? node.parent : null;
}
public RBNode leftOf(RBNode node) {
return node != null ? node.left : null;
}
public RBNode rightOf(RBNode node) {
return node != null ? node.right : null;
}
//只有 新增元素+3结点 需要旋转（4种行态），除了2结点其他需要变色
public void fixAfterPut(RBNode<K, Object> x) {
//新增结点均为红色
x.color = RED;
//只有一个结点（2结点）不用变色和旋转
//此时x和父节点均为红色，需要根据条件选择是否旋转或变色
RBNode y;
while (x != null && x != root && x.getParent().color == RED) {
//x的父节点为爷爷结点的左节点，里面又分为2种情况
//左3
if (parentOf(x)==leftOf(parentOf(parentOf(x)))) {
//叔叔结点
y=rightOf(parentOf(parentOf(x)));
//如果有叔叔结点，说明4节点裂变
if (color(y) == RED) {
//爷爷节点变成红色
parentOf(y).color = RED;
//父节点和叔叔节点变成黑色
parentOf(x).color = BLACK;
y.color = BLACK;
//此时需要递归，防止爷爷节点与它上面的节点都为红色
x = parentOf(parentOf(x));
}else {
//x为父节点的右结点形态时，先左旋一下
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
leftRotate(x);
}
//调整为整体左3的情况
//先变色
parentOf(x).color = BLACK;
parentOf(parentOf(x)).color = RED;
rightRotate(parentOf(parentOf(x)));
}
}
//x的父节点为爷爷结点的右节点
else {
//叔叔结点
y=leftOf(parentOf(parentOf(x)));
//如果有叔叔结点，说明4节点裂变
if (color(y) == RED) {
//爷爷节点变成红色
parentOf(y).color = RED;
//父节点和叔叔节点变成黑色
parentOf(x).color = BLACK;
y.color = BLACK;
//此时需要递归，防止爷爷节点与它上面的节点都为红色
x = parentOf(parentOf(x));
}else {
//x为父节点的右结点形态时，先左旋一下
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rightRotate(x);
}
//调整为整体左3的情况
//先变色
parentOf(x).color = BLACK;
parentOf(parentOf(x)).color = RED;
leftRotate(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
}
static class RBNode<K extends Comparable<K>, V>{
private RBNode parent;
private RBNode left;
private RBNode right;
private boolean color;
private K key;
private V value;
public RBNode() {
}
public RBNode(K key, V value, RBNode parent) {
this.parent = parent;
this.key = key;
this.value = value;
//设置默认颜色为黑色
this.color = BLACK;
}
public RBNode(RBNode parent, RBNode left, RBNode right, boolean color) {
this.parent = parent;
this.left = left;
this.right = right;
this.color = color;
}
public RBNode(RBNode parent, RBNode left, RBNode right, boolean color, K key, V value) {
this.parent = parent;
this.left = left;
this.right = right;
this.color = color;
this.key = key;
this.value = value;
}
public RBNode getParent() {
return parent;
}
public void setParent(RBNode parent) {
this.parent = parent;
}
public RBNode getLeft() {
return left;
}
public void setLeft(RBNode left) {
this.left = left;
}
public RBNode getRight() {
return right;
}
public void setRight(RBNode right) {
this.right = right;
}
public boolean isColor() {
return color;
}
public void setColor(boolean color) {
this.color = color;
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
}
}
网友评论