【算法导论】第十三章，红黑树。java

摘要：如果用数组存储二叉树，假设父节点下标为，则其左孩子的下标是，右孩子的下标是。算法基本思路创建一个水平数组，水平数组的长度为满二叉树中的节点总数，将二叉树的所有节点，按满二叉树的样子，投影到水平数组上，每个节点在水平数组中都对就一个位置。

一、结点

package com.company.RedBlackTree;

/**
 * Created by jiayi on 2016/10/29.
 */

enum colors{
    red,black;
};
public class RedBlackTreeNode implements Cloneable {
    colors color;
    int key;
    RedBlackTreeNode left;
    RedBlackTreeNode right;
    RedBlackTreeNode p;
    int depth;
    public RedBlackTreeNode clone() throws CloneNotSupportedException{ //浅拷贝
        RedBlackTreeNode cloned = (RedBlackTreeNode) super.clone();
        return cloned;
    }
    RedBlackTreeNode(){
        color = colors.black;
        key = 0;
        left = null;
        right = null;
        p = null;
        depth = 0;
    }
    RedBlackTreeNode(int key){
        color = colors.black;
        this.key = key;
        left = null;
        right = null;
        p = null;
        depth = 0;
    }

    public boolean equals(RedBlackTreeNode x){
        if(x.key == key && x.color == color && x.left == left && x.right == right){
            return true;
        }else {
            return false;
        }
    }

}

二、红黑树的插入（RBInsert）、删除（RBDelete）、连接（RBJoin）

package com.company.RedBlackTree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Map;
import java.util.HashMap;

/**
 * Created by jiayi on 2016/10/29.
 */
public class RedBlackTree implements Cloneable{
public RedBlackTreeNode nil;
public RedBlackTreeNode root;
public int N;

public RedBlackTree(){
    nil = new RedBlackTreeNode();
    root = nil;
}
public RedBlackTree(RedBlackTreeNode root){
    this.root = root;
    nil = new RedBlackTreeNode();

}
public void test(int[] a){
    for( int i = 0 ; i < a.length ; i++ ){
        RedBlackTreeNode temp = new RedBlackTreeNode(a[i]);
        RBInsert(temp);
        bfsTree();
        //Print();
    }
    /*bfsTree();
    RedBlackTreeNode temp = RBSearch(root,a[5]);
    RBDelete(temp);
    bfsTree();*/

//Print();
}

  
// 计算某节点在整棵树的第几层(ROOT为第1层)
public int getLevelOfFullTree(RedBlackTreeNode node) {
int depth = 0;

   RedBlackTreeNode t = node;
      while (t != nil) {
            depth++;
            t = t.p;
            }
        return depth;
    }
    // 树形本层节点打印
private void printTreeLevel(String[] nodes)    {
    System.out.print("
|");
    for (int j = 0; j < nodes.length; j++) {
    if (nodes[j] == null||nodes[j].length() == 0) {
        // 打印两位数字的占位符
        System.out.printf("---");
    } else {
        // 打印节点
        System.out.printf("%3s", nodes[j]);
        // 重置数组
        nodes[j] = "";
    }
}
System.out.print("|");

}

  public void bfsTree() {
        System.out.print("
------------------ 树形打印开始 ------------------");

        if (this.root.equals( nil)) {
            System.out.print("
树为pw");
            return;
        }

        // 二叉树的高度
        int maxLevel = getDepth(root);
        // 满二叉树时的总结点数
        int fullTotal = (int) Math.pow(2, maxLevel) - 1;
        // 水平数组
        //int[] nodes = new int[fullTotal];
        String[] nodes = new String[fullTotal];

        // 上一个节点的层次
        int prevLevel = 1;
        // 每层的起始下标
        int start = 0;
        // 每一层的元素的间距
        int stepSize = 0;

        // 广度优先遍历
        Queue queue = new LinkedList<>();
        queue.offer(root);
        RedBlackTreeNode node = nil;
        // 如果用数组存储二叉树，indexMap中存储各节点对应数组的下标
        Map indexMap = new HashMap();
        while (!queue.isEmpty()) {
            // 删除队列头结点
            node = queue.poll();
            // 某节点在整棵树的第几层(ROOT为第1层)
            int levelOfFullTree = getLevelOfFullTree(node);

            // 如果当前深度比前一个节点的尝试大,则开始的新一层的节点访问
            if (levelOfFullTree > prevLevel) {
                // 打印层次的节点
                printTreeLevel(nodes);
            }

            // 计算新的层次的开始下标与步长
            start = (int) Math.pow(2, maxLevel - levelOfFullTree) - 1;
            stepSize = (int) Math.pow(2, maxLevel - levelOfFullTree + 1);
            // System.out.print("
" + "start:" + start + ",stepSize:" + stepSize);

            // 记录节点的下标
            int idx = -1;
            if (node == root) {
                indexMap.put(node.key, 1);
                idx = 1;
            } else{
                if (node == node.p.left) {
                    idx = 2 * indexMap.get(node.p.key) - 1;
                } else if (node == node.p.right) {
                    idx = 2 * indexMap.get(node.p.key);
                }
                indexMap.put(node.key, idx);
            }

            // 计算映射到水平数组的位置
            int y = start + (idx - 1) * stepSize;
            String c;
            if(node.color == colors.black){
                c = "b";
            }else {
                c = "r";
            }
            nodes[y] = String.valueOf(node.key) + c ;
            // System.out.print("
" + "node.value:" + node.value + ",y:" + y);

            // 将节点的左孩子加入队列
            if (!node.left.equals( nil)) {
                queue.offer(node.left);
            }
            // 将节点的右孩子加入队列
            if (!node.right.equals( nil)) {
                queue.offer(node.right);
            }

            // 保留层次数,为下次循环使用
            prevLevel = levelOfFullTree;
        }

        // 打印最底层的节点，因为while的推出，最底层次的节点没有打印，在这里多带带打印
        this.printTreeLevel(nodes);
        System.out.print("
------------------ 树形打印结束 ------------------");
    }

    // 计算以某节点为根的树的深度(从1开始)
    public int getDepth(RedBlackTreeNode node) {
        if (node.equals( nil)) {
            return 0;
        }

        return 1 + Math.max(this.getDepth(node.left), this.getDepth(node.right));
    }
    /**
     * 二叉树的广度优先遍历，按照树形打印此树
     *
 *
 * 算法用到的参数：
 * 1：二叉树的最大深度。
 * 2：每个节点在二叉树中的层次Level，从1开始。
 * 3：每个节点在该层中的序号indexOfLevel，从1开始。
 * 注：
 *  (1)Level和indexOfLevel可以在广度优先遍历时用计数器实现。
 *  (2)Level和indexOfLevel也可以在向树中插入新节点时，初始化到节点中。
 *      如果用数组存储二叉树，假设父节点下标为i，则其左孩子的下标是2*i-1，右孩子的下标是2*i+1。
 *
 * 算法基本思路：
 * (1)：创建一个水平数组，水平数组的长度为 "满二叉树" 中的节点总数，将二叉树的所有节点，按满二叉树的样子，投影到水平数组上，每个节点在水平数组中都对就一个位置。
 * (2)：我们总结一下，对于每一个层级，映射到水平数组后，第一个节点的开始下标=s，本层任意相邻节点的步长(间距)=d，如果下所示
 * 层级   起始下标        步长
 * 1    2^3-1=7     2^4=16
 * 2    2^2-1=3     2^3=8
 * 3    2^1-1=1     2^2=4
 * 4    2^0-1=0     2^1=2
 * (3)：有了以上数据，我们可以计算出，任意一层，任意一节点在水平数组中的下标，
 * 下标=起始下标+(该节点所在层次-1)*步长
 * (4)：OK，每一次每个节点的位置确定了，树形图自然也确定了。
 *
 * 另：
 * 如果想要让输出特别规矩，我们必须：
 * 1：先确定每个节点的值(即输出的内容)最多占多少个字符宽度，假设为flength。
 *     在输出树的过程中，不论遇到空值还是有值，都格式化输出，长度不足flength的，用空格补齐。
 * 2：可以适当的将水平数组扩大一倍，这样每层中的各节点之间的距离拉长了，最终看到的结果是整个树水平放大了。
 *
 */

private RedBlackTreeNode RBSearch(RedBlackTreeNode x, int k){
    while (x != nil){
        if(x.key > k){
            return RBSearch(x.left,k);
        }else if(x.key < k){
            return RBSearch(x.right,k);
        }
        else return x;
    }
    return nil;
}
private void LeftRotate(RedBlackTreeNode x){ // 假设x.right != Nil
    RedBlackTreeNode y = x.right;
    //将y设为新的子树根节点
    x.right = y.left;
    if(y.left != nil){
        y.left.p = x;
    }
    if(x.p.right == x){
        x.p.right = y;
        y.p = x.p;
    }else if(x.p.left == x){
        x.p.left = y;
        y.p = x.p;
    }else{
        y.p = nil;
        root = y;
    }
    //x成为y的左孩子
    y.left = x;
    x.p = y;
    //y的左孩子成为x的右孩子
}
private void RightRotate(RedBlackTreeNode y){
    //使x成为新的根节点
    RedBlackTreeNode x = y.left;
    y.left = x.right;
    if(x.right != nil){
        y.left.p = y;
    }
    if(y.p.left == y){
        y.p.left = x;
        x.p = y.p;
    }else if(y.p.right == y){
        y.p.right = x;
        x.p = y.p;
    }else{
        root = x;
        x.p = nil;
    }
    // y成为x的右孩子
    y.p = x;
    x.right = y;
    //x的右孩子变成y的左孩子
    //y.left = x.right;

}

private void RBInsert(RedBlackTreeNode z){
    RedBlackTreeNode y = nil;
    RedBlackTreeNode x = root;
    while (x != nil){
        y = x;
        if(z.key < x.key){
            x = x.left;
        }else{
            x = x.right;
        }
    }
    z.p = y;
    if(y == nil){
        root = z;
    }else if(z.key < y.key){
        y.left = z;
    }else{
        y.right = z;
    }
    z.right = nil;
    z.left = nil;
    z.color = colors.red;
    RBInsertFixup(z);
    ++N;

}
private void RBInsertFixup(RedBlackTreeNode z){
    while (z.p.color == colors.red){
        //由于z的父节点为红，z也为红，故需要调整
        //首先想把z的父节点set为红--> z.p的分支不满足性质5 --> 将z.p.p set为黑，且将z.uncle set为红
        if(z.p == z.p.p.left){//若z.p是z.p.p的左孩子
            RedBlackTreeNode y = z.p.p.right;//z的叔节点
            if(y.color == colors.red){//case 1 : 如果z的叔节点是红色（与z的父节点颜色一样）
                z.p.color = colors.black;
                y.color = colors.black;
                z.p.p.color = colors.red;
                z = z.p.p;
                ++z.depth;
            }else if(z == z.p.right){ // case 2 : 如果z的叔节点是黑色,且z是右孩子
                z = z.p;
                LeftRotate(z);//左旋，使得红色节点z上移
            }
            z.p.color = colors.black;//case 3
            if(z.p != nil) {
                z.p.p.color = colors.red;
                RightRotate(z.p.p);
            }
        }else{//若z.p是z.p.p的右孩子
            RedBlackTreeNode y = z.p.p.left;
            if(y.color == colors.red){//case 1 : 如果z的叔节点是红色（与z的父节点颜色一样）
                z.p.color = colors.black;
                y.color = colors.black;
                z.p.p.color = colors.red;
                z = z.p.p;
            }else {
                if (z == z.p.left) { // case 2 : 如果z的叔节点是黑色,且z是左孩子
                    z = z.p;
                    RightRotate(z);//左旋，使得红色节点z上移
                }
                z.p.color = colors.black;//case 3
                if(z.p != nil) {
                    z.p.p.color = colors.red;
                    LeftRotate(z.p.p);
                }
            }
        }
    }
    root.color = colors.black;
    root.p = nil;
}

private void RBDelete(RedBlackTreeNode z){

    RedBlackTreeNode y = z;
    colors yOriginalColor = y.color;
    RedBlackTreeNode x = nil;
    if(z.left == nil){ //只有右边节点
        x = z.right;
        RBTranlant(z,z.right);
    }else if(z.right == nil){//只有左边节点
        x = z.left;
        RBTranlant(z,z.left);
    }else{//左右都有节点
        y = TreeMinimum(z.right);//z的后继
        yOriginalColor = y.color;
        x = y.right;
        if(y.p == z){//z.right 就是z的后继
            x.p = y ;//为啥？
        }else{
            //后继是y
            //先用y.right代替y
            RBTranlant(y,y.right);
            //再用y代替z
            y.right = z.right;
            y.right.p = y;
        }
        RBTranlant(z,y);
        y.left = z.left;
        y.left.p = y;
        y.color = z.color;
    }
    if(yOriginalColor == colors.black){
        //当z有一个儿子时，y就是z，x就是z的儿子
        //已知y原为黑色，即z原来为黑色。但是
        //z.child(也就是x)替换z后，可能会改变z位置（也就是现在的x）的黑高，故需要调整x
        //      若x是红色，那么有可能和原来z.p构成双红，以及会破坏x处黑高 --> 把x设置为黑色即可
        //      若x是黑色，会减小黑高，需要调整

        //当z有两个儿子时，y是z的后继，x是y.right
        //z被y替换，已知y是黑色，则会改变z位置（现在y）的黑高。
        //调整：
                    //a.若x是红色，那么有可能和原来y.p构成双红，以及会破坏x处黑高 --> 把x设置为黑色即可
                    //b.若x是黑色，由于y的上移，本分支黑高被破坏，需要调整
        //      2.若z原来是红色，则y被重置为红色。x替换y后，现在x位置处的性质被破坏
        RBDeleteFixup(x);
    }
}
private void RBDeleteFixup(RedBlackTreeNode x){
    while (x != root && x.color == colors.black){
       // bfsTree();
        RedBlackTreeNode w = nil;
        if(x == x.p.left){ //x是一个左孩子
            w = x.p.right;//x的兄弟节点
            if(w.color == colors.red) { //case 1
                colors tempXP = x.p.color;
                x.p.color = w.color;
                w.color = tempXP;
                LeftRotate(x.p);
                w = x.p.right;
            }else{
                if(w.right.color == colors.black){
                    if(w.left.color == colors.black){//case 2
                        w.color = colors.red;
                        x = x.p;
                        --x.depth;
                    }else { // case 3
                        colors temp = w.color;
                        w.color = w.left.color;
                        w.left.color = temp;
                        RightRotate(w);
                        w = x.p.right;
                    }
                }else{// case 4
                    w.color = x.p.color;
                    x.p.color = colors.black;
                    --x.p.depth;
                    ++w.depth;
                    w.right.color = colors.black;
                    LeftRotate(x.p);
                    x =root;
                }
            }
        }else{
            w = x.p.left;//x的兄弟节点
            if(w.color == colors.red) { //case 1
                colors tempXP = x.p.color;
                x.p.color = w.color;
                w.color = tempXP;
                RightRotate(x.p);
                w = x.p.left;
            }else{
                if(w.left.color == colors.black){
                    if(w.right.color == colors.black){//case 2
                        w.color = colors.red;
                        x = x.p;
                    }else { // case 3
                        colors temp = w.color;
                        w.color = w.right.color;
                        w.right.color = temp;
                        LeftRotate(w);
                        w = x.p.left;
                    }
                }else{// case 4
                    w.color = x.p.color;
                    x.p.color = colors.black;
                    w.left.color = colors.black;
                    RightRotate(x.p);
                    x =root;
                }
            }
        }
    }
    x.color = colors.black;
}
private void RBTranlant(RedBlackTreeNode u,RedBlackTreeNode v){//用v替换u
    if(u == u.p.right){//u是u.p的右孩子
        u.p.right = v;
        v.p = u.p;
    }else if( u == u.p.left ){//u是u.p的左孩子孩子
        u.p.left = v;
        v.p = u.p ;
    }else {//u是根节点
        v.p = nil;
        root = v;
    }
}

public RedBlackTree RBJoin(RedBlackTree T1, RedBlackTree T2, int x) throws CloneNotSupportedException {
    RedBlackTreeNode x_root = new RedBlackTreeNode(x);
    x_root.right = T1.root;
    T1.root.p = x_root;

    x_root.left = T2.root;
    T2.root.p = x_root;

    int x_N = Math.max(T1.N,T2.N);
    RedBlackTree newTree = new RedBlackTree(x_root);
    newTree.N = x_N;
    T1.nil = newTree.nil;
    T2.nil =  newTree.nil;
    x_root.p = newTree.nil;

    return newTree;
}

private RedBlackTreeNode TreeMinimum(RedBlackTreeNode x){//得到最小值
    while (x.left != nil){
        x = x.left;
    }
    return x;
}
private RedBlackTreeNode TreeMaximum(RedBlackTreeNode x){//得到最大值
    while (x.right != nil){
        x = x.right;
    }
    return x;
}

}