------------ 本文來自 阿P官方博客
------------ 在線測(cè)試紅黑樹：紅黑樹在線測(cè)試

一、紅黑樹

    自平衡二叉查找樹(Binary Search Tree)
    二叉查找樹：
        基于二叉樹
            左子樹小于根，右子樹大于根
            缺點(diǎn)：如果選錯(cuò)根節(jié)點(diǎn)，整個(gè)樹就不再平衡
    特點(diǎn)
        所有節(jié)點(diǎn)非紅即黑
        根節(jié)點(diǎn)一定是黑色
        紅節(jié)點(diǎn)的子節(jié)點(diǎn)一定是黑色
        最低層的葉子節(jié)點(diǎn)一定是黑色
        從根節(jié)點(diǎn)到任意葉子節(jié)點(diǎn)經(jīng)歷過的黑色節(jié)點(diǎn)一定相同
        新增的節(jié)點(diǎn)顏色一定是紅色節(jié)點(diǎn)
    紅黑樹時(shí)間復(fù)雜度：O(logN) 與二分查找法一致
        第一次查找數(shù)量 n/2
        第二次查找數(shù)量 n/2/2
        第三次查找數(shù)量 n/2/2/2
        …...
        第m次查找數(shù)量 n/(2^m)
        由此我們可以得知時(shí)間復(fù)雜度=logN

二、紅黑樹修正（遵循以下步驟進(jìn)行修正）

    當(dāng)前節(jié)點(diǎn)為紅，父節(jié)點(diǎn)為紅，并且叔父節(jié)點(diǎn)為紅或?yàn)榭?        父節(jié)點(diǎn)、叔父節(jié)點(diǎn)涂黑，祖父節(jié)點(diǎn)涂紅。對(duì)祖父節(jié)點(diǎn)繼續(xù)操作
    當(dāng)前節(jié)點(diǎn)為紅且是右子葉，父節(jié)點(diǎn)為紅，并且叔父節(jié)點(diǎn)為黑
        以當(dāng)前節(jié)點(diǎn)為軸，進(jìn)行左旋
    當(dāng)前節(jié)點(diǎn)為紅且是左子葉，父節(jié)點(diǎn)為紅，并且叔父節(jié)點(diǎn)為黑
        父節(jié)點(diǎn)涂黑，祖父節(jié)點(diǎn)涂紅，以父節(jié)點(diǎn)為軸，進(jìn)行右旋

三、紅黑樹JAVA實(shí)現(xiàn)類

package RBTree;

/**
 * 紅黑樹
 *
 */
public class RBTreeDemo<T extends Comparable<T>> {
    
    Node root;//根節(jié)點(diǎn)
    Node min;//最左節(jié)點(diǎn)
    Node max;//最右節(jié)點(diǎn)
    
    Boolean RED = true;
    Boolean BLACK = false;
    /**
     * 新增
     * @param val
     */
    public void add(T val)
    {
        if (this.root == null) {
            //根節(jié)點(diǎn)為黑色
            this.root = new Node<T>(val, this.BLACK, null, null, null);
            return;
        }
        Node node = this.root;
        //當(dāng)前節(jié)點(diǎn)
        Node current = new Node<T>(val, this.RED, null, null, null);
        //遍歷樹，進(jìn)行插入
        while (true) {
            if (val.compareTo((T) node.val) > 0) {//放右子節(jié)點(diǎn)
                if (node.right == null) {
                    node.right = current;
                    current.parent = node;
                    break;
                }
                node=node.right;
            } else {//放左子節(jié)點(diǎn)
                if (node.left == null) {
                    node.left = current;
                    current.parent = node;
                    break;
                }
                node=node.left;
            }
        }
        //插入完進(jìn)行自平衡
        fixUp(current);
    }
    /**
     * 自平衡
     */
    public void fixUp(Node node)
    {
        //當(dāng)前節(jié)點(diǎn)沒父節(jié)點(diǎn)，則涂黑
        if (node.parent == null) {
            node.color = this.BLACK;
            this.root = node;
            return;
        }
        //當(dāng)前節(jié)點(diǎn)沒有祖父節(jié)點(diǎn)
        if (node.parent.parent == null) {
            return;
        }
        //叔父節(jié)點(diǎn) 可以為空
        Node uncleNode = this.getUncleNode(node);
        //當(dāng)前節(jié)點(diǎn)為紅，且父節(jié)點(diǎn)為紅
        if (node.color == this.RED && node.parent.color == this.RED) {
            //叔父節(jié)點(diǎn)為空或者為紅，就進(jìn)行涂色
            if (uncleNode == null || uncleNode.color == this.RED) {
                node.parent.color = this.BLACK;
                if (uncleNode != null) {
                    uncleNode.color=this.BLACK;
                }
                node.parent.parent.color = this.RED;
                this.fixUp(node.parent.parent);
            } else if (uncleNode.color == this.BLACK) {
                //自己是左子葉
                if (node.parent.left.equals(node)) {
                    this.right(node);
                    this.fixUp(node.parent);//右旋后，修改當(dāng)前節(jié)點(diǎn)顏色
                } else {//自己是右子葉
                    this.left(node);
                    this.fixUp(node.left);//曾經(jīng)的父節(jié)點(diǎn)
                }
            }
        }
    }
    /**
     * 叔父節(jié)點(diǎn)，可以為空
     * @param node
     * @return
     */
    private Node getUncleNode(Node node) {
        Node uncleNode= node.parent.parent.left;
        if (uncleNode == null || node.parent.equals(uncleNode)) {
            uncleNode = node.parent.parent.right;
        }
        return uncleNode;
    }
    /**
     * 當(dāng)前結(jié)點(diǎn)為紅，且處于右子葉上。父節(jié)點(diǎn)為紅，叔父節(jié)點(diǎn)為黑或空時(shí)。以當(dāng)前節(jié)點(diǎn)為軸進(jìn)行左旋
     * 當(dāng)前節(jié)點(diǎn)的祖父節(jié)點(diǎn)，變成自己的父節(jié)點(diǎn)
     * 當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)，變成自己的左節(jié)點(diǎn)
     * 當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)，變成當(dāng)前右節(jié)點(diǎn)的右節(jié)點(diǎn)
     */
    private void left(Node node) {
        Node parent = node.parent;
        Node left = node.left;
        Node pParent = node.parent.parent;
        //祖父節(jié)點(diǎn)
        pParent.left = node;
        //父節(jié)點(diǎn)
        parent.parent = node;
        parent.right = left;
        //左節(jié)點(diǎn)
        left.parent = parent;
        //當(dāng)前節(jié)點(diǎn)
        node.parent = pParent;
        node.left = parent;
    }
    /**
     * 當(dāng)前結(jié)點(diǎn)為紅，且處于左子葉上。父節(jié)點(diǎn)為紅，叔父節(jié)點(diǎn)為黑時(shí)。以父節(jié)點(diǎn)為軸進(jìn)行右旋
     */
    private void right(Node node) {
        Node parent = node.parent;
        Node right = parent.right;
        Node pParent = node.parent.parent;
        Node ppParent = node.parent.parent.parent;
        //涂色
        pParent.color = this.RED;
        parent.color = this.BLACK;
        if (ppParent != null) {
            //祖祖父節(jié)點(diǎn)
            if (ppParent.right.equals(pParent)) {
                ppParent.right = parent;
            } else {
                ppParent.left = parent;
            }
        }
        //祖父節(jié)點(diǎn)
        pParent.left = right;
        pParent.parent=parent;
        //父節(jié)點(diǎn)
        parent.right = pParent;
        parent.parent = ppParent;
        //右子節(jié)點(diǎn)
        right.parent = pParent;
    }
    /**
     * 前序遍歷 從根開始遍歷
     */
    private String preOrder(Node node) {
        if (node == null) {
            return null;//如果左側(cè)樹遍歷完成，返回null
        }
        String strLeft = this.preOrder(node.left);
        if (strLeft == null) {
            strLeft="";
        }
        String strRight = this.preOrder(node.right);
        if (strRight == null) {
            strRight="";
        }
        return strLeft + node.toString() + strRight;
    }
    @Override
    public String toString() {
        //前序遍歷
        return preOrder(this.root);
    }
    /**
     * 結(jié)點(diǎn)類
     */
    private class Node<T>{
        public T val;
        public Boolean color;//紅為true
        public Node left;
        public Node right;
        public Node parent;
        public Node(T val, Boolean color, Node left, Node right, Node parent) {
            super();
            this.val = val;
            this.color = color;
            this.left = left;
            this.right = right;
            this.parent = parent;
        }
        @Override
        public String toString() {
            String left = "-";
            String right = "-";
            if (this.left != null) {
                left = this.left.val.toString();
            }
            if (this.right != null) {
                right =  this.right.val.toString();
            }
            return "[" + left + ", "+this.val.toString() + ", " + right +", "+ getColorName(this.color) + "]";
        }
        private String getColorName(Boolean color) {
            return color == true? "紅" : "黑";
        }
        @Override
        public boolean equals(Object obj) {
            Node obj1 = (Node)obj;
            return obj1.val == this.val;
        }
    }
}