标准红黑树
概述: 标准红黑树是2-3-4树的一种表示,
特性:
- 1.节点是红色或黑色。
- 2.根是黑色。
- 3.所有叶子都是黑色（叶子是NIL节点）。
- 4.每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红节点。）
- 5.从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点（简称黑高）。
/**
* 标准红黑树: 参考TreeMap源码
* 1.节点是红色或黑色。
* 2.根是黑色。
* 3.所有叶子都是黑色（叶子是NIL节点）。
* 4.每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
* 5.从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点（简称黑高）。
*/
public class RedBlackBST<K,V> {
private Comparator<? super K> comparator;
private boolean RED = true;
private boolean BLACK = false;
private Node<K,V> root;
private int n;
private class Node<K,V>{
K key;
V value;
Node left;
Node right;
Node parent;
boolean color;
public Node(K key, V value, Node parent, boolean color) {
this.key = key;
this.value = value;
this.parent = parent;
this.color = color;
}
}
public RedBlackBST(){
comparator = (x,y) ->{
if(!(x instanceof Comparable) || !(y instanceof Comparable))
throw new RuntimeException("error");
return ((Comparable) x).compareTo(y);
};
}
public RedBlackBST(Comparator<? super K> comparator){ this.comparator = comparator; }
public int size(){ return n; }
//获取
public V get(K key){
Node<K,V> x = getNode(key);
return x == null ? null : x.value;
}
private Node<K,V> getNode(K key){
Node<K,V> x = root;
int cmp;
while(x != null){
cmp = comparator.compare(key,x.key);
if(cmp > 0) x = x.right;
else if(cmp < 0) x = x.left;
else return x;
}
return null;
}
/**
* 插入
* 概述: 按照二叉查找树插入方式进行插入,然后自底向上进行平衡修复
*/
public void put(K key,V value){
if(key == null) return;
Node<K,V> x = root;
if(x == null){ //case1: 插入根节点
root = new Node<>(key,value,null,RED);
root.color = BLACK;
n = 1;
return;
}
int cmp;
Node<K,V> parent;
do {
parent = x;
cmp = comparator.compare(key,x.key);
if (cmp > 0) x = x.right;
else if (cmp < 0) x = x.left;
else {
x.value = value;
return;
}
}while(x != null);
Node<K,V> e = new Node<>(key,value,parent,RED);
if(cmp > 0) parent.right = e;
else parent.left = e;
//插入节点后自底向上进行平衡修复
fixAfterPut(e);
++n;
}
/**
* 删除 (可不拆分处理参考后面remove方法)
* 概述: 借助删除最小节点方法(deleteMin)
* case1: 待删除节点存在右子树,直接用右子树最小节点替换掉待删除节点,然后删除最小节点
* case2: 待删除节点右子树为空,左子树不为空(此时只有一个左节点,且为红节点)
* case3: 待删除节点左右子树都为空,删除当前节点(即最小节点)
*/
public void delete(K key){
Node<K,V> p = getNode(key);
if(p == null) return;
if(p.right != null) { //1.右子树不为空,用右子树最小节点替换掉待删除节点
Node<K, V> s = min(p.right);
p.key = s.key;
p.value = s.value;
deleteMin(s);
}
else if(p.left != null){ // 2.右子树为空, 左子树不为空(此时只有一个左节点且为红节点)
p.key = (K)p.left.key;
p.value = (V)p.left.value;
//deleteMin(p.left); //与下面2行代码等价
p.left.parent = null;
p.left = null;
}
else deleteMin(p); // 3.左右子树都为空时
}
//删除最小
public void deleteMin(){ deleteMin(root); }
/**
* 删除指定子树的最小节点
* 概述: 分2种情况处理(最小节点不存在左子节点)
* 1. 待删除节点(最小节点)只有一个右子节点(此时该右子节点为红节点)
* 2. 待删除节点没有子节点
* @param h
*/
private void deleteMin(Node<K,V> h){
if(h == null) return;
Node<K,V> min = min(h);
Node<K,V> replace = min.right;
if(replace != null){ //1. 最小节点只有一个右子节点(一定红节点)
min.key = replace.key;
min.value = replace.value;
min.right = null;
replace.parent = null;
}
else{ //2. 最小节点没有右子节点,即左右子节点都为空
if(!isRED(min)) fixAfterDelete(min); //删除的为黑色节点,需要平衡修复
if(min == leftOf(min.parent))
min.parent.left = null;
else if(min == rightOf(min.parent)) //p.right == min(p.right),一直从root节点删除则不需要
min.parent.right = null;
else
root = null;
min.parent = null;
}
--n;
}
public K min(){ return min(root).key; }
private Node<K,V> min(Node<K,V> h){
if(h == null) return null;
while(h.left != null)
h = h.left;
return h;
}
/**
* 标准删除
* 概述: 不借助deleteMin,将上面delete方法稍作修改即可
*/
public void remove(K key){
Node<K,V> p = getNode(key);
if(p == null) return;
if(p.left != null && p.right != null){
Node<K,V> s = min(p.right);
p.key = s.key;
p.value = s.value;
p = s;
}
Node<K,V> replace = p.left != null ? p.left : p.right;
if(replace != null){ //replace必为红节点
p.key = replace.key;
p.value = replace.value;
p.left = null;
p.right = null;
replace.parent = null;
}
else{ //p节点没有子节点时
if(!isRED(p)) fixAfterDelete(p); //修复
if(p == leftOf(p.parent))
p.parent.left = null;
else if(p == rightOf(p.parent))
p.parent.right = null;
else root = null;
p.parent = null;
}
--n;
}
//使用leftOf 与 rightOf 方便处理null值
private Node<K,V> leftOf(Node<K,V> h){ return h == null ? null : h.left; }
private Node<K,V> rightOf(Node<K,V> h){ return h == null ? null : h.right; }
/******************************************
************* 核心方法 *******************
******************************************/
//左旋
private void rotateLeft(Node<K,V> h){
if(h == null) return;
Node<K,V> x = h.right;
//左旋
h.right = x.left;
x.left = h;
//更新parent
if(h.right != null) h.right.parent = h;
x.parent = h.parent;
if(x.parent == null) root = x;
else if(h == x.parent.left) x.parent.left = x;
else x.parent.right = x;
h.parent = x;
}
//右旋
private void rotateRight(Node<K,V> h){
if(h == null) return;
Node<K,V> x = h.left;
//右旋
h.left = x.right;
x.right = h;
//更新parent
if(h.left != null) h.left.parent = h;
x.parent = h.parent;
if(x.parent == null) root = x;
else if(h == x.parent.left) x.parent.left = x;
else x.parent.right = x;
h.parent = x;
}
/**
* 插入后修复
* 分情况处理: 具体处理看代码
* case1: 插入为根节点,直接插入变为黑色(put方法中已处理)
* case2: 父节点为黑色时插入红节点不影响平衡
* case3:
* case3.1:父节点为红色,叔叔节点(父节点的兄弟节点)为红色
* case3.2:父节点为红色,叔叔节点为黑色
* 核心思想就是变色修复性质4(消除连续红节点),然后旋转保证黑高不变(性质5)
* 具体情况参考代码或者图解,关键是清楚涉及变动分支的黑高变化情况
*/
private void fixAfterPut(Node<K,V> h){
while(h != null && h != root && isRED(h.parent)){ //此时h, h.parent均不为null
if(h.parent == leftOf(h.parent.parent)){ //此时h.parent.parent不为null
Node<K,V> y = rightOf(h.parent.parent);
if(isRED(y)){ //case3.1修复: 父节点与叔叔节点变黑,祖父节点(父节点的父节点)变红,
h.parent.color = BLACK; //相当于子树黑高+1,根节点黑高-1,保持黑高不变
y.color = BLACK; //接着使用同样方式向上修复变红后的祖父节点
h.parent.parent.color = RED;
h = h.parent.parent;
}
else{ //case3.2修复:将一个红节点颜色转移到祖父节点的右子树,且保证其黑高不变
if(h == rightOf(h.parent)) {//转为2个连续的左红节点处理
rotateLeft(h.parent);
h = h.left;
}
h.parent.color = BLACK; //2个连续红节点都为左节点,变色右旋之后变动分支黑高不变
h.parent.parent.color = RED;
rotateRight(h.parent.parent);
//此时修复完成,将跳出循环
}
}
else{ //于上面对称
Node<K,V> x = leftOf(h.parent.parent);
if(isRED(x)){ //case3.1修复
h.parent.color = BLACK;
x.color = BLACK;
h.parent.parent.color = RED;
h = h.parent.parent;
}
else{ //case3.2修复
if (h == leftOf(h.parent)) {
rotateRight(h.parent);
h = h.right;
}
h.parent.color = BLACK;
h.parent.parent.color = RED;
rotateLeft(h.parent.parent);
//此时修复完成,将跳出循环
}
}
}
root.color = BLACK;
}
/**
* 删除时修复
* 概述: 删除黑节点后要想办法让当前分支黑高+1,可转换为(当前分支的父节点黑高+1,兄弟节点黑高-1)
* 分情况处理: 具体处理细节看代码
* case1: 待删除节点为红节点,直接删除不影响平衡
* case2:
* case2.1: 待删除节点为黑节点,其兄弟节点为红节点
* case2.2: (待删除节点为黑节点,其兄弟节点(sib)为黑节点)
* case2.2.1: 再划分,兄弟节点(sib)的子节点均为黑
* case2.2.2: 兄弟节点(sib)的子节点存在红节点
*/
private void fixAfterDelete(Node<K,V> h){
//**case1: 在删除方法(delete,remove方法)中直接删除
while(h != root && !isRED(h)){ //case2
if(h == leftOf(h.parent)) {
Node<K, V> sib = rightOf(h.parent);
if (isRED(sib)) { //**case2.1处理: 变色左旋后转换为case2.2的情况
sib.color = BLACK;
sib.parent.color = RED;
rotateLeft(sib.parent);
sib = rightOf(h.parent);
}
//case2.2
if (!isRED(leftOf(sib)) && !isRED(rightOf(sib))) { //**case2.2.1处理:
sib.color = RED; //此时兄弟节点黑高-1,问题转换为让父节点黑高+1,用同样方法处理父节点即可
h = sib.parent; //如果父节点为红,直接变黑即可,否则进入循环相同方法处理
} else { //**case2.2.2处理: 大概考虑从sib借过来一个黑节点,sib黑高-1,sib的一个红节点变黑+1,黑高不变
if (!isRED(sib.right)) {
sib.left.color = BLACK; //sib.left为RED必不为null
rotateRight(sib);
sib = rightOf(h.parent);
} //处理后sib右子树黑高+1,左子树黑高不变
sib.color = sib.parent.color;
sib.right.color = BLACK; //sib.right不可能为null,此处sib黑高+1,或者不变(经过前面if语句内处理已经+1)
sib.parent.color = BLACK;
rotateLeft(sib.parent); //旋转后sib的右子树黑高-1,左子树变为sib兄弟节点(h)的右子树黑高不变,h.left黑高+1
break; //此时已达到平衡结束修复
}
}
else{ //与上面对称
Node<K,V> sib = leftOf(h.parent);
if(isRED(sib)){
sib.color = BLACK;
sib.parent.color = RED;
rotateRight(sib.parent);
sib = leftOf(h.parent);
}
if(!isRED(sib.left) && !isRED(sib.right)){
sib.color = RED;
h = h.parent;
}
else{
if(!isRED(sib.left)){
sib.right.color = BLACK;
rotateLeft(sib);
sib = leftOf(h.parent);
}
sib.color = sib.parent.color;
sib.parent.color = BLACK;
sib.left.color = BLACK;
rotateRight(sib.parent);
break;
}
}
}
h.color = BLACK;
}
/******************************************
************* 另一种递归实现 *******************
******************************************/
//一种插入方法的递归实现,不同于上面put方法
public void add(K key,V value){
if(key == null) return;
root = add(root,key,value,false);
root.color = BLACK;
}
private Node<K,V> add(Node<K,V> h,K key,V value,boolean isRight){
if(h == null) return new Node(key,value,null,RED);//不需要维护parent节点
if(isRED(h.left) && isRED(h.right)) flipColors(h); //沿着查找路径消除4节点
int cmp = comparator.compare(key,h.key);
if(cmp > 0 ){
h.right = add(h.right,key,value,true);
if(isRED(h) && isRED(h.right) && !isRight) h = rotateL(h);
if(isRED(h.right) && isRED(h.right.right)){ //逆着查找路径将右倾连续红节点转为4节点
h = rotateL(h);
h.color = BLACK;
}
}
else if(cmp < 0){
h.left = add(h.left,key,value,false);
if(isRED(h) && isRED(h.left) && isRight) h = rotateR(h);
if(isRED(h.left) && isRED(h.left.left)){ //逆着查找路径将左倾连续红节点转为4节点
h = rotateR(h);
h.color = BLACK;
}
}
else h.value = value;
return h;
}
private Node<K,V> rotateL(Node<K,V> h){
Node<K,V> x = h.right;
h.right = x.left;
x.left = h;
x.color = h.color;
h.color = RED;
return x;
}
private Node<K,V> rotateR(Node<K,V> h){
Node<K,V> x = h.left;
h.left = x.right;
x.right = h;
x.color = h.color;
h.color = RED;
return x;
}
private void flipColors(Node<K,V> h){
h.color = !h.color;
h.left.color = !h.left.color;
h.right.color = !h.right.color;
}
private boolean isRED(Node<K,V> h){
if(h == null) return false;
return h.color == RED;
}
//中序遍历方法
public Iterable<K> keys(){
ArrayDeque<K> queue = new ArrayDeque<>();
keys(root,queue);
return queue;
}
//中序遍历
public void keys(Node<K,V> x, Queue<K> queue){
if(x == null) return;
keys(x.left,queue);
queue.add(x.key);
keys(x.right,queue);
}
/******************************************
************* 检测是否为红黑 **************
******************************************/
//检查是否为红黑树
public boolean check(){
if(!isParent(root)) System.out.print("parent维护错误");
if(!isBST()) System.out.println("不是二叉树");
if(isRED(root)) System.out.println("违反性质2");
if(!is4()) System.out.println("违反性质4");
if(!is5()) System.out.println("违反性质5");
return isBST() && !isRED(root) && is4() && is5();
}
//判断是否为二叉查找树
private boolean isBST(){ return isBST(root,null,null); }
private boolean isBST(Node<K,V> x,K max,K min){
if(x == null) return true;
if(max != null && comparator.compare(x.key,max) >= 0) return false;
if(min != null && comparator.compare(x.key,min) <= 0) return false;
return isBST(x.left,x.key,min) && isBST(x.right,max,x.key);
}
//检查红黑树性质4
private boolean is4(){ return is4(root); }
private boolean is4(Node x){ //性质4
if(x == null) return true;
if(isRED(x) && (isRED(x.left) || isRED(x.right))) return false;
return is4(x.left) && is4(x.right);
}
//检查红黑树性质5
private boolean is5(){ //性质5
int black = 0;
Node x = root;
while(x != null){
if(!isRED(x)) black++;
x = x.left;
}
return is5(root,black);
}
private boolean is5(Node x,int black){
if(x == null) return black == 0;
if(!isRED(x)) black--;
return is5(x.left,black) && is5(x.right,black);
}
//检查父节点是否维护正确
private boolean isParent(Node x){
if(x == null) return true;
if(x.left != null && x.left.parent != x) return false;
if(x.right != null && x.right.parent != x) return false;
return isParent(x.left) && isParent(x.right);
}
}