红黑树Java实现

红黑树的特性：

1. 结点是红色或黑色。

2. 根结点是黑色。

3. 每个叶子结点都是黑色的空结点（NIL结点）。

4. 每个红色结点的两个子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点)

5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。

public class RedBlackTree> {

    //记录根结点
    private Node root;
    //记录树中元素的个数
    private int size;

    private static final boolean RED = false; //false为红色节点
    private static final boolean BLACK = true; //true为黑色节点

    
    private class Node {
        Node left; //左节点
        Node right; //右节点
        Node parent; //父节点
        boolean color; //节点颜色
        T val;  //节点存放的数据

        public Node() {
        }

        public Node(T val) {
            this.val = val;
        }
    }

    public RedBlackTree() {
        root = null;
        size = 0;
    }

    
    private Node rotateLeft(Node node) {
        Node temp = node.right;
        node.right = temp.left;
        temp.left = node;
        //父节点交换
        temp.parent = node.parent;
        node.parent = temp;
        if (node.right != null) {
            node.right.parent = node;
        }
        //进行颜色交换
        boolean tempColor = temp.color;
        temp.color = node.color;
        node.color = tempColor;
        return temp;
    }

    
    private Node rotateRight(Node node) {
        Node temp = node.left;
        node.left = temp.right;
        temp.right = node;
        //父节点交换
        temp.parent = node.parent;
        node.parent = temp;
        if (node.left != null) {
            node.left.parent = node;
        }
        //进行颜色交换
        boolean tempColor = temp.color;
        temp.color = node.color;
        node.color = tempColor;
        return temp;
    }

    
    private void flipColors(Node node) {
        node.left.color = BLACK;
        node.right.color = BLACK;
        node.color = RED;
    }

    //添加节点方法
    public void put(T t) {
        size++;
        root = put(root, t);
        root.color = BLACK;
    }

    
    private Node put(Node root, T val) {
        if (root == null) {
            return new Node(val);
        }
        //和当前节点比较，从而判断节点往哪边添加
        final int compare = root.val.compareTo(val);
        if (compare > 0) {
            Node temp = put(root.left, val);
            temp.parent = root;
            root.left = temp;
        } else {
            Node temp = put(root.right, val);
            temp.parent = root;
            root.right = temp;
        }

        
        if (root.left != null && root.left.color == RED && (root.right == null || root.right.color == BLACK)) {
            //当前节点的左节点的右节点为红色节点(RED),对左节点进行左旋转
            if (root.left.right != null && root.left.right.color == RED) {
                root.left = rotateLeft(root.left);
            }
            //当前节点的左节点的左节点为红色节点(RED),对当前节点进行左旋转
            if (root.left.left != null && root.left.left.color == RED) {
                root = rotateRight(root);
            }
        }

        
        if (root.right != null && root.right.color == RED && (root.left == null || root.left.color == BLACK)) {
            //当前节点的右节点的左节点为红色节点(RED),对右节点进行右旋转
            if (root.right.left != null && root.right.left.color == RED) {
                root.right = rotateRight(root.right);
            }
            //当前节点的右节点的右节点为红色节点(RED),对当前节点进行左旋转
            if (root.right.right != null && root.right.right.color == RED) {
                root = rotateLeft(root);
            }
        }

        
        if (root.left != null && root.left.color == RED && root.right != null && root.right.color == RED) {
            //当前节点的左节点或右节点存在一个红色节点(RED)时,进行颜色反转
            if ((root.left.left != null && root.left.left.color == RED) || (root.left.right != null && root.left.right.color == RED) ||
                    (root.right.left != null && root.right.left.color == RED) || (root.right.right != null && root.right.right.color == RED)) {
                flipColors(root);
            }
        }

        return root;
    }

    //删除节点方法
    public void remove(T value) {
        remove(this.root, value);
        //防止空指针异常
        if (this.root != null) {
            this.root.color = BLACK;
        }
    }

    
    private void remove(Node root, T value) {
        Node node = root, parent;
        while (node != null) {
            //和当前节点比较，从而寻找节点
            int cmp = value.compareTo(node.val);
            if (cmp > 0) {
                //删除节点比当前节点大，向右节点寻找
                node = node.right;
            } else if (cmp < 0) {
                //删除节点比当前节点小，向左节点寻找
                node = node.left;
            } else {
                //找到节点，进行删除操作
                size--;
                // 被删除节点的"左右孩子都不为空"的情况。
                if (node.left != null && node.right != null) {
                    // 被删节点的后继节点。(称为"取代节点")
                    // 用它来取代"被删节点"的位置，然后再将"被删节点"去掉。
                    Node replace = getSuccessorNode(node);
                    // "node节点"不是根节点(只有根节点不存在父节点)
                    if (node.parent != null) {
                        if (node.parent.left == node) {
                            node.parent.left = replace;
                        } else {
                            node.parent.right = replace;
                        }
                    } else {
                        // "node节点"是根节点，更新根节点。
                        this.root = replace;
                    }
                    // child是"取代节点"的右孩子，也是需要"调整的节点"。
                    // "取代节点"肯定不存在左孩子！因为它是一个后继节点。
                    Node child = replace.right;
                    parent = replace.parent;
                    // 保存"取代节点"的颜色
                    boolean color = replace.color;
                    // "被删除节点"是"它的后继节点的父节点"
                    if (node == parent) {
                        parent = replace;
                    } else {
                        // child不为空
                        if (child != null) {
                            child.parent = parent;
                        }
                        parent.left = child;
                        replace.right = node.right;
                        node.right.parent = replace;
                    }
                    replace.parent = node.parent;
                    replace.color = node.color;
                    replace.left = node.left;
                    node.left.parent = replace;

                    if (color == BLACK) {
                        fixRemoveAfter(child, parent);
                    }
                    node = null;
                    return;
                }
                //情况1，2，删除节点是叶子节点或者有一个叶子节点
                Node child;
                if (node.left != null) {
                    child = node.left;
                } else {
                    child = node.right;
                }
                parent = node.parent;
                if (child != null) {
                    child.parent = node.parent;
                }

                // "node节点"不是根节点
                if (parent != null) {
                    if (parent.left == node)
                        parent.left = child;
                    else
                        parent.right = child;
                } else {
                    this.root = child;
                }

                if (node.color == BLACK) {
                    fixRemoveAfter(child, child.parent);
                }
                node = null;
            }
        }
    }

    
    private void fixRemoveAfter(Node node, Node parent) {
        Node other;
        while ((node == null || node.color == BLACK) && (node != this.root)) {
            if (parent.left == node) {
                other = parent.right;
                // 子情况3，结点的兄弟结点是红色: 结点2的父结点为轴，进行左旋，父结点变成红色、兄弟结点变成黑色
                if (parent.right != null && parent.right.color == RED) {
                    parent = rotateLeft(parent);
                    other = parent;
                }

                // 子情况2，结点的父亲、兄弟、侄子结点都是黑色: 把结点的兄弟结点改为红色
                if (other != null && (other.left == null || other.left.color == BLACK) &&
                        (other.right == null || other.right.color == BLACK)) {
                    other.color = RED;
                    node = parent;
                    parent = node.parent;
                } else {

                    //子情况5，结点的父结点随意，兄弟结点是黑色右孩子，左侄子结点是红色，右侄子结点是黑色: 以兄弟结点为轴进行右旋,父结点和兄弟结点的颜色交换
                    if (other != null && (other.right == null || other.right.color == BLACK)) {
                        parent.right = rotateRight(other);
                    }
                    //子情况6，结点2的父结点随意，兄弟结点B是黑色右孩子，右侄子结点是红色: 结点2的父结点A为轴左旋，父结点和兄弟结点的颜色交换，并且侄子结点变为黑色
                    parent.parent.left = rotateLeft(parent);
                    parent.parent.right.color = BLACK;
                    break;
                }
            } else {
                other = parent.left;
                // 子情况3，结点的兄弟结点是红色
                if (parent.left != null && parent.left.color == RED) {
                    // Case 1: x的兄弟w是红色的
                    parent = rotateRight(parent);
                    other = parent;
                }
                // 子情况2，结点2的父亲、兄弟、侄子结点都是黑色
                if (other != null && (other.right == null || other.right.color == BLACK) &&
                        (other.left == null || other.left.color == BLACK)) {
                    other.color = RED;
                    node = parent;
                    parent = node.parent;
                } else {

                    //子情况5，结点的父结点随意，兄弟结点是黑色右孩子，左侄子结点是红色，右侄子结点是黑色
                    if (other != null && (other.left == null || other.left.color == BLACK)) {
                        parent.left = rotateLeft(other);
                    }
                    //子情况6，结点2的父结点随意，兄弟结点B是黑色右孩子，右侄子结点是红色
                    parent.parent.right = rotateRight(parent);
                    parent.parent.left.color = BLACK;
                    break;
                }
            }
        }
        if (node != null) {
            node.color = BLACK;
        }
    }

    
    private Node getSuccessorNode(Node node) {
        if (node == null) {
            return null;
        } else if (node.right != null) {  //节点的右子节点不为空
            Node right = node.right;
            //向节点的右侧的左节点开始寻找后继节点
            while (right.left != null) {
                right = right.left;
            }
            return right;
        } else {
            return node;
        }
    }

    //返回红黑树的最大深度
    public int maxDepth() {
        return maxDepth(root);
    }

    //返回红黑树里面的数据总数
    public int size() {
        return size;
    }

    //私有方法，计算某个节点树的深度
    private int maxDepth(Node root) {
        //空树情况，返回0
        if (root == null) {
            return 0;
        }
        int maxLeft = 0;  //记录左节点的深度
        int maxRight = 0; //记录右节点的深度
        if (root.left != null) {
            maxLeft = maxDepth(root.left);
        }
        if (root.right != null) {
            maxRight = maxDepth(root.right);
        }
        return maxLeft > maxRight ? maxLeft + 1 : maxRight + 1;
    }
}