紅黑樹實現(Java形式)

2-3查詢樹定義

1.任意空連結到根節點的路徑長度都是相等的
2. 4-結點變換為3-結點時, 樹的高度不會發生變化, 只有當根節點是臨時的4-結點時, 分解根節點後, 樹的高度+1
3.普通二叉查詢樹是自頂向下生長的, 2-3查詢樹的自底向上生長的


都是2-3查詢樹
(插入節點過程中產生的4-結點是臨時的!)

紅黑樹定義

在滿足2-3查詢樹的前提上, 使用對結點間連結的==「標記」 == 以
顏色有兩種:
紅色 模擬2-3查詢樹中的3-結點
黑色 普通的結點連結形式

性質:

1. 紅連結均為左連線
   2.沒有任何一個結點同時與兩個紅連結相連(4-結點不存在)
   3.任意空連結到根節點的路徑經過相同的黑連結

左旋和右旋

當某個結點的左子結點為黑色，右子結點為紅色，此時需要左旋

通過左旋. 我們能使只有左連結為紅色
所以會出現下面的情況:
這違反了紅黑樹的規則1, 所以我們仍要操作

但是發現, 還是違反了規則2
所以繼續操作

顏色反轉

額外的2-3參考圖

程式碼:

package cn.datastructure.structure.tree;

/**
 * @author 悠一木碧
 * 紅黑樹實現:
 * 基於了2-3查詢樹的思想:
 * 任意空連結到根節點的路徑長度都是相等的
 * 4-結點變換為3-結點時, 樹的高度不會發生變化, 只有當根節點是臨時的4-結點時, 分解根節點後, 樹的高度+1
 * 普通二叉查詢樹是自頂向下生長的, 2-3查詢樹的自底向上生長的
 * 且:
 * 紅連結均為左連線
 * 沒有任何一個結點同時與兩個紅連結相連
 * 任意空連結到根節點的路徑經過相同的黑連結
 */
public class RedBlackTree<Key extends Comparable<Key>, Value> {
    private Node root;
    private int size;
    private final boolean RED = true;
    private final boolean BLACK = false;

    private class Node{
        public Key key;
        public Value value;
        public Node left;
        public Node right;
//        用來標識父節點指向自己連結的顏色
        public boolean color;

        public Node(Key key, Value value, Node left, Node right, boolean color) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
            this.color = color;
        }

        public Node() {
        }

    }



    public void put(Key key, Value value){
        root = put(root, key, value);
        this.root.color = BLACK;
    }

    private Node put(Node node, Key key, Value value){
        if(null == node){
            size++;
            return new Node(key, value, null, null, BLACK);
        }
        if(key.compareTo(node.key) < 0){
            node.left = put(node.left, key, value);
        } else if(key.compareTo(node.key) > 0){
            node.right = put(node.right, key, value);
        } else{
            node.value = value;
        }

        if(isRed(node.right) && !isRed(node.left)){
            rotateLeft(node);
        }
        if(isRed(node.left) && isRed(node.left.left)){
            rotateRight(node);
        }
        if(isRed(node.left) && isRed(node.right)){
            colorInversion(node);
        }
        return node;
    }

    /**
     * 左旋操作,
     * @param head
     */
    private Node rotateLeft(Node head){
        Node rightSon = head.right;
        head.right = rightSon.left;
        rightSon.left = head;
        rightSon.color = head.color;
        head.color = RED;
        return rightSon;
    }

    /**
     * 右旋操作
     * @param head
     * @return
     */
    private Node rotateRight(Node head){
        Node leftSon = head.left;
        head.left = leftSon.right;
        leftSon.right = head;
        leftSon.color = head.color;
        head.color = RED;
        return leftSon;
    }

    /**
     * 空連結預設為黑色
     * @param node
     * @return
     */
    private boolean isRed(Node node){
        if(null == node){
            return false;
        }
        return node.color == RED;
    }


    /**
     * 相當於拆分掉4-結點, 在紅黑樹中, 臨時的4-結點相當於當前結點的左右連結都是紅色
     * @param node
     */
    private void colorInversion(Node node){
        node.color = RED;
        node.left.color = BLACK;
        node.right.color = BLACK;
    }




    public Value get(Key key){
        return get(root, key);
    }

    private Value get(Node node, Key key){
        if(null == node){
            return null;
        }

        int res = key.compareTo(node.key);

        if(res > 0){
            return get(node.right, key);
        } else if(res < 0){
            return get(node.left, key);
        } else{
            return node.value;
        }
    }



    public int size(){
        return size;
    }

}