Tree 红黑树

红黑树是一种二叉平衡树搜索树，相关背景知识此处不再叙述。

节点与关键值之间的关系与普通二叉树 一致，只是在插入时要保证红黑规则，如果插入过程中违反了红黑规则，树则会通过自我调整，改变树的结构和节点的颜色，使之满足红黑规则。满足红黑规则的树是平衡树。

红黑规则如下：

1. 每一个节点不是黑的就是红的
2. 根总是黑的
3. 红色节点的子节点必定是黑的，反之未必
4. 从根到叶节点或空子节点的每条路径中必然包含同样高度的黑色节点（从根到叶节点或空子节点的每条路径中必然有同样的高度）

为了保证红黑规则，程序按照如下方式工作：

新插入的节点（除了根以外）的是红的
插入过程中如果有一个黑色节点且它有两个红色节点，就需要颜色变化，如果该节点是根节点，则根节点不变化
右旋必须有一个左子节点，左旋必须有一个右子节点
旋转时，外侧子孙上升，内侧子孙断开其与父节点的连接，并成为其祖父节点的子节点

向下查找子节点的时候，发现一个黑色节点有两个红色节点时候，就执行一次颜色变化。
之后检查红黑冲突，发生冲突时
    红色节点为X，红色节点的父节点为P，祖父节点为G，
   
    旋转后继续向下查找

插入子节点X后
    如果P为红色
        如果X为G的外侧子孙，旋转一次
            以G为顶点作一次旋转
        如果X为G的内侧子孙，旋转两次

红黑树与Tree-2-3-4 原理非常相似，事实上可以相互转换。

 

Node为辅助类，充当树节点，并记录红黑。

Tree尽提供插入算法，且假设插入的数据不重复。

Tree.ordinal： 打印数据，为测试服务

Tree.main： 提供简单测试。

其他平衡树见：Tree-2-3 , Tree-2-3-4

class Node {
    private int value;    //数值
    private Node parent;
    private Node left;
    private Node right;
    private boolean isBlack;

    Node(int value) { this.value = value; }

    Node insert(int value) {
        Node node = new Node(value);
        if(value < this.value) left(node);
        else right(node);
        return node;
    }

    boolean isCorrect() {    //返回当前节点是否与父节点都是红色，如果是，则返回fasle
        return !(parent != null && !parent.isBlack && !isBlack);
    }

    Node getNext(int value) {    //根据给定的值返回下一个可以插入数据的节点
        if(value < this.value) return left;
        else return right;
    }
   
    void left(Node node) {
        left = node;
        if(node != null) node.parent = this;
    }

    Node left() { return left; }

    void right(Node node) {
        right = node;
        if(node != null) node.parent = this;
    }

    Node right() { return right; }

    int value() { return value; }

    Node getParent() { return parent; }

    boolean isOuter(Node node) {    //判断父节点与当前节点，当前节点与给定子节点是否在同一方向
        return parent.isLeft(this) && this.isLeft(node) ||
            !parent.isLeft(this) && !this.isLeft(node);
    }

    boolean isLeft(Node node) { return node == left; }

    void changeColor() { isBlack = !isBlack; }
   
    boolean isBlack() { return isBlack; }
}

 

class Tree {
    private Node root;    //根节点
    public void insert(int value) {
        if(root == null) {    //添加根节点，并将根置为黑色
            root = new Node(value);
            root.changeColor();
        } else {
            Node current = root;    //从根节点开始向下遍历，寻找可以插入新值的节点
            while(current.getNext(value) != null) {
                fixColor(current);    //如果需要，则修正颜色
                if(!current.isCorrect()) fix(current);    //如果发生红黑冲突，则修正
                current = current.getNext(value);    //继续寻找可以插入新值的下一个节点
            }
            current = current.insert(value);    //在找到的节点下插入新值
            if(!current.isCorrect()) fix(current);    //如果发生红黑冲突，则修正
        }
    }

    private void fixColor(Node node) {    //如果当前节点是红色，且两个子节点是黑色，则翻转颜色
        if(node.isBlack()
                && node.left() != null && !node.left().isBlack()
                && node.right() != null && !node.right().isBlack()) {
            if(node != root) node.changeColor();    //根始终保持黑色
            node.left().changeColor();
            node.right().changeColor();
        }
    }

    private void fix(Node node) {    //修正红黑冲突
        Node p = node.getParent();    //获得父节点
        Node g = p.getParent();    //获得祖父节点
        if(p.isOuter(node)) {    //如果是祖父的外孙，则需要变化两次颜色，做一次旋转
            g.changeColor();
            p.changeColor();
            if(p.isLeft(node)) turnRight(g); //以祖父节点为中心做一次右旋
            else turnLeft(g);
        } else {    //如果是祖父的内孙，则需要变化两次颜色，做两次旋转
            g.changeColor();
            node.changeColor();
            if(!p.isLeft(node)) {
                turnLeft(p);    //以父节点为中心作一次左旋
                turnRight(g);    //以祖父节点为中心做一次右旋
            } else {
                turnRight(p);
                turnLeft(g);
            }
        }
    }

    private void turnLeft(Node node) {    //左旋算法
        Node p = node.getParent();
        Node right = node.right();   
        node.right(right.left());
        right.left(node);
        if(node == root) root = right;
        else if (p.isLeft(node)) p.left(right);
        else p.right(right);
    }

    private void turnRight(Node node) { //右旋算法
        Node p = node.getParent();
        Node left = node.left();
        node.left(left.right());
        left.right(node);
        if(node == root) root = left;
        else if (p.isLeft(node)) p.left(left);
        else p.right(left);
    }

    public void ordinal() {
        System.out.println("===============");
        ordinal(root,0);       
        System.out.println("===============");
    }

    private void ordinal(Node node, int level) {    //打印
        if(node ==  null) return;
        ordinal(node.left() , level + 1);
        System.out.println(node.value() + (node.isBlack() ? " black" : " red") + " " + level);
        ordinal(node.right() , level + 1);
    }


    public static void main(String[] args) {
        Tree t = new Tree();
        t.insert(50);
        t.ordinal();
        t.insert(60);
        t.ordinal();
        t.insert(70);
        t.ordinal();
        t.insert(80);
        t.ordinal();
        t.insert(40);
        t.ordinal();
        t.insert(30);
        t.ordinal();
        t.insert(20);
        t.ordinal();
        t.insert(10);
        t.ordinal();
        t.insert(35);
        t.ordinal();
        t.insert(55);
        t.ordinal();
        t.insert(75);
        t.ordinal();
        t.insert(73);
        t.ordinal();
        t.insert(53);
        t.ordinal();
        t.insert(33);
        t.ordinal();
       
    }
}