引言

根據(jù)《算法》第4版。編寫紅黑樹。

理論

參見:

淺談算法和數(shù)據(jù)結(jié)構(gòu): 八 平衡查找樹之2-3樹

淺談算法和數(shù)據(jù)結(jié)構(gòu): 九 平衡查找樹之紅黑樹

這些也是參考的《算法》

特性

紅黑數(shù)事實(shí)上就是特殊的二叉排序樹。

紅黑樹是一種具有紅色和黑色鏈接的平衡查找樹，同時(shí)滿足：

• 紅色節(jié)點(diǎn)向左傾斜
• 一個(gè)節(jié)點(diǎn)不可能有兩個(gè)紅色鏈接
• 整個(gè)書完全黑色平衡，即從根節(jié)點(diǎn)到所以葉子結(jié)點(diǎn)的路徑上，黑色鏈接的個(gè)數(shù)都相同。

代碼（java）

package org.hirudy.practice;

/**
 * @author: rudy
 * @date: 2016/08/13
 *
 * 紅黑樹實(shí)現(xiàn)
 *
 */
public class RedBlackTreePractice {

    /**
     * 紅黑數(shù)節(jié)點(diǎn)
     * @param <T>
     */
    private static class Node<T> {
        public static final boolean RED_NODE = true;
        public static final boolean BLACK_NODE = false;

        public boolean nodeColor; // 節(jié)點(diǎn)顏色
        public Comparable key; // 當(dāng)前節(jié)點(diǎn)搜索key
        public T value; // 當(dāng)前節(jié)點(diǎn)存儲(chǔ)值

        public int nodeNumber = 0; // 以當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹的節(jié)點(diǎn)個(gè)數(shù)
        public Node leftNode,rightNode; // 當(dāng)前節(jié)點(diǎn)的左右子節(jié)點(diǎn)

        public Node(Comparable key, T value,int number, boolean color){
            this.key = key;
            this.value = value;
            this.nodeNumber = number;
            this.nodeColor = color;
        }

        /**
         * 判斷當(dāng)前節(jié)點(diǎn)類型
         * @return boolean
         */
        public boolean isRed(){
            return this.nodeColor == RED_NODE;
        }

        /**
         * 獲取當(dāng)前節(jié)點(diǎn)及其子節(jié)點(diǎn)個(gè)數(shù)
         * @return int
         */
        public int getSize(){
            return nodeNumber;
        }

        /**
         * 計(jì)算當(dāng)前節(jié)點(diǎn)及其子節(jié)點(diǎn)個(gè)數(shù)
         * @return int
         */
        protected int size(){
            int nodeNumber = 1;
            if (leftNode != null){
                nodeNumber += leftNode.getSize();
            }
            if (rightNode != null){
                nodeNumber += rightNode.getSize();
            }
            return nodeNumber;
        }
    }

    /**
     * 紅黑數(shù)
     * @param <T>
     */
    public static class RedBlackTree<T> {
        private Node<T> root; // 根節(jié)點(diǎn)

        /**
         * 紅黑樹基本操作-左旋轉(zhuǎn)
         * @param Node<T> node
         * @return Node<T>
         */
        protected Node rotateLeft(Node node){
            Node tmp = node.rightNode;
            node.rightNode = tmp.leftNode;
            tmp.leftNode = node;
            tmp.nodeColor = node.nodeColor;
            node.nodeColor = Node.RED_NODE;
            tmp.nodeNumber = node.nodeNumber;
            node.nodeNumber = node.size();
            return tmp;
        }

        /**
         * 紅黑樹基本操作-右旋轉(zhuǎn)
         * @param Node<T> node
         * @return Node<T>
         */
        protected Node rotateRight(Node node){
            Node tmp = node.leftNode;
            node.leftNode = tmp.rightNode;
            tmp.rightNode = node;
            tmp.nodeColor = node.nodeColor;
            node.nodeColor = Node.RED_NODE;
            tmp.nodeNumber = node.nodeNumber;
            node.nodeNumber = node.size();
            return tmp;
        }

        /**
         * 紅黑樹基本操作-顏色旋轉(zhuǎn)
         * @param Node<T> node
         * @return Node<T>
         */
        protected Node rotateColor(Node node){
            node.nodeColor = Node.RED_NODE;
            node.leftNode.nodeColor = Node.BLACK_NODE;
            node.rightNode.nodeColor = Node.BLACK_NODE;
            return node;
        }

        /**
         * 判斷節(jié)點(diǎn)是否為紅節(jié)點(diǎn)
         * @param node
         * @return
         */
        protected boolean isRed(Node node){
            if (node == null){
                return false;
            }
            return node.isRed();
        }

        public Node<T> search(Comparable key){
            return search(key,this.root);
        }

        /**
         * 查詢
         * @param key 查詢關(guān)鍵字
         * @param node 開始查詢的根節(jié)點(diǎn)
         * @return Node 查找到的節(jié)點(diǎn)
         */
        public Node<T> search(Comparable key, Node node){
            if (node == null){
                return null;
            }
            int cmp = key.compareTo(node.key);
            if (cmp < 0){
                return search(key,node.leftNode);
            }else if (cmp > 0){
                return search(key,node.rightNode);
            }else{
                return node;
            }
        }

        /**
         * 從根節(jié)點(diǎn)插入
         * @param key
         * @param value
         */
        public void insert(Comparable key, T value){
            Node<T> node = insertSubTree(this.root, key, value);
            node.nodeColor = Node.BLACK_NODE;
            this.root = node;
        }

        /**
         * 從某個(gè)節(jié)點(diǎn)插入
         * @param key 插入key
         * @param value 插入值
         */
        protected Node insertSubTree(Node node, Comparable key, T value){
            if (node == null){
                return new Node<T>(key, value, 1, Node.RED_NODE);
            }

            // 比較各個(gè)節(jié)點(diǎn)
            int cmp = key.compareTo(node.key);
            if (cmp < 0){
                node.leftNode = insertSubTree(node.leftNode, key, value);
            }else if (cmp > 0){
                node.rightNode = insertSubTree(node.rightNode, key, value);
            }else{
                node.value = value;
            }

            if (!isRed(node.leftNode) && isRed(node.rightNode)){
                node = rotateLeft(node);
            }

            if (isRed(node.leftNode) && isRed(node.leftNode.leftNode)){
                node = rotateRight(node);
            }

            if (isRed(node.leftNode) && isRed(node.rightNode)){
                node = rotateColor(node);
            }
            node.nodeNumber = node.size();

            return node;
        }
    }


    public static void main(String[] args){
        RedBlackTree<String> tree = new RedBlackTree<String>();

        int[] insertValue = new int[]{12,1,9,10,77,2,38,8,4};
        for (int value : insertValue){
            tree.insert(value,"value_" + value);
        }

        Node node = tree.search(77);
        System.out.println(node.value);
        System.out.println("end");
    }
}