左倾红黑树
概述:
通过二叉查找树可以发现,在最坏情况下(变成长链),性能很差,
因此理想的情况下就是构建一个完美平衡的树,然而维护完美平衡需要额外的开销
红黑树在性能和维护平衡之间进行协调
左倾红黑树特点:
2-3树的一种表示,红连接相连的节点为3节点,所有红连接为左倾
/**
* 左倾红黑树: 详细请参考<<算法第四版>>
* 红黑树的特性:
*（1）每个节点或者是黑色，或者是红色。
*（2）根节点是黑色。
*（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
*（4）如果一个节点是红色的，则它的子节点必须是黑色的。
*（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
*/
public class LLRedBlackBST<Key,Value> {
private Comparator comparator;
private Node root;
private boolean RED = true;
private boolean BLACK = false;
private class Node{
private Key key;
private Value val;
private Node left;
private Node right;
private int n;
private boolean color; //当前节点的颜色
public Node(Key key, Value val, int n, boolean color) {
this.key = key;
this.val = val;
this.n = n;
this.color = color;
}
}
public LLRedBlackBST(Comparator comparator) {
this.comparator = comparator;
}
/**************************************************
* 左倾红黑树特有实现(与二叉查找树不同的部分)
**************************************************/
public void put(Key key,Value val){
if(key == null) return;
root = put(root,key,val);
root.color = BLACK;
}
/**
* 插入
* 与二叉查找树相同方式进行插入,然后自底向上进行修复
* 如果插入后形成的为3节点则不需要处理,
* 如果形成了4节点则需要分解为3个2节点(此时高度会增加1打破平衡),
* 为了保证平衡,将其中的根节点传递到上层(与父节点合并为一个3节点或者4节点)(转换颜色即可,红连接相连为同一层)
* 以此类推,如果传递后还为4节点继续向上传递,仅当传递到root节点变为4节点时,树高会增加1,此时依然保持平衡
*/
private Node put(Node h,Key key,Value val){
if(h == null) return new Node(key,val,1,RED);
int cmp = comparator.compare(key,h.key);
if(cmp > 0) h.right = put(h.right,key,val);
else if(cmp < 0) h.left = put(h.left,key,val);
else h.val = val;
//查找结束逆着查找路径进行平衡修复
return balance(h);
}
/**
* 删除最小值
* 对于红节点,可以直接删除一个节点不影响平衡
* 因此保证在删除时,查找的当前节点为红节点(3节点或者构造的4节点)
*/
public void deleteMin(){
root = deleteMin(root);
if(root != null) root.color = BLACK;
}
private Node deleteMin(Node h){
if(h.left == null) return null;
//左子节点不是红节点,则需要先转换为红节点
if(!isRED(h.left) && !isRED(h.left.left))
h = moveRedLeft(h); //将左节点转换为红节点
h.left = deleteMin(h.left);
return balance(h); //删除成功后逆着删除路径修复
}
/**
* 删除最大值
* 只需将路径中左倾红连接转为右倾,然后就和删除最小值相同思路处理即可
*/
public void deleteMax(){
root = deleteMax(root);
if(root != null) root.color = BLACK;
}
private Node deleteMax(Node h){
//将左倾红连接转为右倾
if(isRED(h.left)) h = rotateRight(h);
if(h.right == null) return null;
//当前节点右子节点不为红节点,则须先转为红节点
if(!isRED(h.right) && !isRED(h.right.left))
h = moveRedRight(h);
h.right = deleteMax(h.right);
return balance(h); //删除结束后逆着删除路径修复
}
/**
*删除
* 概述: 找到待删除节点N,然后用该节点N的右子树的最小节点替换掉该节点即可
* 此时问题就转换为,删除待删除节点N的右子树的最小值,因此和删除最小值相同,
* 保证查找时,当前节点为红节点即可
*/
public void delete(Key key){
if(key == null || !contains(key)) return;
root = delete(root,key);
if(root != null) root.color = BLACK;
}
private Node delete(Node h,Key key){
int cmp = comparator.compare(key,h.key);
if(cmp < 0){
//下一步查询节点不为红节点则先转为红节点
if(!isRED(h.left) && !isRED(h.left.left))
h = moveRedLeft(h);
h.left = delete(h.left,key);
}
else{//大于等于时放到一起,因为查找命中时(相等),要删除右子树最小节点
//此时要保证右子树根节点为红节点(可能需要向父节点借一个节点,此时命中节点可能被传递
//这时还需继续向右查找命中,再进行删除操作)
if(isRED(h.left)) {
h = rotateRight(h);
//右旋后当前节点变化须重新比较
cmp = comparator.compare(key,h.key);
}
if(cmp == 0 && h.right == null) return null;
//下一步查询节点不为红节点则先转为红节点
if(!isRED(h.right) && !isRED(h.right.left)) {
h = moveRedRight(h);
//转为红节点后当前节点变化,需要重新比较
cmp = comparator.compare(key,h.key);
}
if(cmp == 0){ //命中切右子树根节点为红节点时可以执行删除操作
Node x = min(h.right);
h.key = x.key;
h.val = x.val;
h.right = deleteMin(h.right);
}
else h.right = delete(h.right,key);
}
return balance(h); //逆着查找路径修复
}
/**************************************************
* 核心: 左倾红黑树辅助方法(详细情况参考算法第四版分情况图解)
**************************************************/
//是否为红节点
private boolean isRED(Node x){
if(x == null) return false;
return x.color == RED;
}
/**
* 修复为左倾红黑树
* 1.将右倾红连接转为左倾
* 2.将4节点分解为2个2节点和一个红节点(向上传递)
*/
private Node balance(Node h){
if(!isRED(h.left) && isRED(h.right)) h = rotateLeft(h);
if(isRED(h.left) && isRED(h.left.left)) h = rotateRight(h);
if(isRED(h.left) && isRED(h.right)) flipColors(h);
h.n = size(h.left) + size(h.right) + 1;
return h;
}
//左旋: 将右倾红连接变为左倾
private Node rotateLeft(Node h){
Node x = h.right;
h.right = x.left;
x.left = h;
x.color = x.left.color;
x.left.color = RED;
x.n = h.n;
h.n = size(h.left) + size(h.right) + 1;
return x;
}
//右旋: 将左倾红连接变为右倾
private Node rotateRight(Node h){
Node x = h.left;
h.left = x.right;
x.right = h;
x.color = x.right.color;
x.right.color = RED;
x.n = h.n;
h.n = size(h.left) + size(h.right) + 1;
return x;
}
//改变颜色
private void flipColors(Node h){
h.color = !h.color;
h.left.color = !h.left.color;
h.right.color = !h.right.color;
}
/**
* 将当前节点的左子节点(left)变为红节点
* 1.当前节点的右节点(right)为红时,从右节点借一个组成3节点
* 2.否则从当前节点借一个合并左右子节点组成4节点
*/
private Node moveRedLeft(Node h){
flipColors(h); //改变颜色(左右子节点+父节点组成4节点)
if(isRED(h.right.left)){ //当前节点的右节点为红节点(左倾红连接相连)
h.right = rotateRight(h.right);
h = rotateLeft(h);
flipColors(h);
}
return h;
}
//将当前节点的右子节点变为红节点
private Node moveRedRight(Node h){
flipColors(h);
if(isRED(h.left.left)){
h = rotateRight(h);
flipColors(h);
}
return h;
}
/**************************************************
* 左倾红黑树其他实现(与二叉查找树相同,详情参考二叉查找树)
**************************************************/
public int size(){ return size(root); }
private int size(Node x){
if(x == null) return 0;
return x.n;
}
//是否为空
public boolean isEmpty(){ return root == null; }
public Value get(Key key){
if(key == null) return null;
return get(root,key);
}
private Value get(Node x,Key key){
while(x != null){
int cmp = comparator.compare(key,x.key);
if(cmp > 0) x = x.right;
else if(cmp < 0) x = x.left;
else return x.val;
}
return null;
}
public boolean contains(Key key){ return get(key) != null; }
public Key min(){
if(root == null) return null;
return min(root).key;
}
private Node min(Node x){
if(x.left == null) return x;
return min(x.left);
}
public Key max(){
if(root == null) return null;
return max(root).key;
}
private Node max(Node x){
if(x.right == null) return x;
return max(x.right);
}
public Key floor(Key key){
Node t = floor(root,key);
if(t == null) return null;
return t.key;
}
private Node floor(Node x,Key key){
if(x == null) return null;
int cmp = comparator.compare(key,x.key);
if(cmp < 0) x = floor(x.left,key);
else if(cmp >0) {
Node t = floor(x.right, key);
if (t != null) x = t;
}
return x;
}
public Key ceiling(Key key){
Node t = ceiling(root,key);
if(t == null) return null;
return t.key;
}
private Node ceiling(Node x,Key key){
int cmp = comparator.compare(x.key,key);
if(cmp < 0) x = ceiling(x.right,key);
else if(cmp > 0){
Node t = ceiling(x.left,key);
if(t != null) x = t;
}
return x;
}
public Key select(int k){
if(k < 0 || k >= size()) return null;
return select(root,k).key;
}
private Node select(Node x,int k){
int t = size(x.left);
if(t > k) return select(x.left,k);
else if(t < k) return select(x.right,k-t-1);
else return x;
}
public int rank(Key key){ return rank(root,key); }
private int rank(Node x,Key key){
if(x == null) return 0;
int cmp = comparator.compare(key,x.key);
if(cmp < 0) return rank(x.left,key);
else if(cmp > 0) return 1 + size(x.left) + rank(x.right,key);
else return size(x.left);
}
public int height(){ return height(root); }
private int height(Node x){
if(x == null) return 0;
return Math.max(height(x.left),height(x.right))+1;
}
public Iterable<Key> keys(){ return keys(min(),max()); }
public Iterable<Key> keys(Key lo,Key hi){
if(lo == null && hi == null) throw new RuntimeException("参数为null");
ArrayDeque<Key> queue = new ArrayDeque<>();
keys(queue,root,lo,hi);
return queue;
}
private void keys(Queue<Key> queue,Node x,Key lo,Key hi){
if(x == null) return;
int cmplo = comparator.compare(x.key,lo);
int cmphi = comparator.compare(x.key,hi);
if(cmplo > 0) keys(queue,x.left,lo,hi);
if(cmplo >= 0 && cmphi <= 0)queue.offer(x.key);
if(cmphi < 0) keys(queue,x.right,lo,hi);
}
/**************************************************
* 左倾红黑树验证
**************************************************/
public boolean check(){
if(!isBST()) System.out.println("不是二叉树");
if(!isSizeConsistent()) System.out.println("n错误");
if(!isRankConsistent()) System.out.println("rank或select方法错误");
if(!is23()) System.out.println("不是左倾2-3树");
if(!isBalanced()) System.out.println("不是平衡树");
return isBST() && isSizeConsistent() && isRankConsistent() && is23() && isBalanced();
}
//是否为二叉查找树
private boolean isBST(){
return isBST(root,null,null);
}
private boolean isBST(Node x,Key min,Key max){
if(x == null) return true;
if(min != null && comparator.compare(x.key,min) <= 0) return false;
if(max != null && comparator.compare(x.key,max) >= 0) return false;
return isBST(x.left,min,x.key) && isBST(x.right,x.key,max);
}
//验证n
private boolean isSizeConsistent(){ return isSizeConsistent(root); }
private boolean isSizeConsistent(Node x){
if(x == null) return true;
if(size(x.left) + size(x.right) + 1 != size(x)) return false;
return isSizeConsistent(x.left) && isSizeConsistent(x.right);
}
private boolean isRankConsistent(){
for(int i=0;i<size();++i)
if(i != rank(select(i))) return false;
for(Key key : keys())
if(comparator.compare(select(rank(key)),key) != 0) return false;
return true;
}
//验证红黑树性质4,(左倾)
private boolean is23(){ return is23(root); }
private boolean is23(Node x){
if(x == null) return true;
if(isRED(x.right)) return false;
if(isRED(x) && isRED(x.left)) return false;
return is23(x.left) && is23(x.right);
}
//是否平衡树,检验红黑树性质5
private boolean isBalanced(){
int black = 0;
Node x = root;
while(x != null) {
if (!isRED(x)) black++;
x = x.left;
}
return isBalanced(root,black);
}
private boolean isBalanced(Node x,int black){
if(x == null) return black == 0;
if(!isRED(x)) black--;
return isBalanced(x.left,black) && isBalanced(x.right,black);
}
}