平衡查找樹

定義

父節(jié)點的左子樹和右子樹的高度之差不能大于1

2-3查找樹

定義

2-3樹運行每個節(jié)點保存1個或者兩個的值。對于普通的2節(jié)點(2-node)，他保存1個key和左右兩個自己點。對應(yīng)3節(jié)點(3-node)，保存兩個Key，2-3查找樹的定義如下：

1. 要么為空，要么：
2. 對于2節(jié)點，該節(jié)點保存一個key及對應(yīng)value，以及兩個指向左右節(jié)點的節(jié)點，左節(jié)點也是一個2-3節(jié)點，所有的值都比key要小，右節(jié)點也是一個2-3節(jié)點，所有的值比key要大。
3. 對于3節(jié)點，該節(jié)點保存兩個key及對應(yīng)value，以及三個指向左中右的節(jié)點。左節(jié)點也是一個2-3節(jié)點，所有的值均比兩個key中的最小的key還要?。恢虚g節(jié)點也是一個2-3節(jié)點，中間節(jié)點的key值在兩個跟節(jié)點key值之間；右節(jié)點也是一個2-3節(jié)點，節(jié)點的所有key值比兩個key中的最大的key還要大。

如果中序遍歷2-3查找樹，就可以得到排好序的序列。在一個完全平衡的2-3查找樹中，根節(jié)點到每一個為空節(jié)點的距離都相同。

變換方法

1. 向2-結(jié)點插入新鍵，將2-結(jié)點變成3-結(jié)點
2. 向3-結(jié)點插入新鍵，將3-結(jié)點變成4-結(jié)點，然后轉(zhuǎn)換成3個2-結(jié)點組成的2-3樹，樹的高度增加1
3. 從下往上，依次變換，可以有中間狀態(tài)，但是最后必須都為2-結(jié)點和3-結(jié)點

結(jié)點變換示意圖

紅黑樹

思想

用標準的二叉查找樹和一些額外的信息來表示2-3樹。紅鏈接將兩個2-結(jié)點連接起來構(gòu)成一個3-結(jié)點，黑鏈接則是2-3樹中的普通鏈接。

定義

紅黑樹是含有紅黑鏈接并且滿足下列條件的二叉查找樹：

1. 紅鏈接均為左鏈接
2. 沒有任何一個結(jié)點同時和兩個紅鏈接相連
3. 該樹是完美紅黑平衡的，即任意空鏈接到根節(jié)點路徑上的黑鏈接數(shù)量相同

相關(guān)操作

顏色表示

結(jié)點的數(shù)據(jù)結(jié)構(gòu)：鍵+值+左右子樹+結(jié)點總數(shù)+顏色
結(jié)點的顏色是指指向該節(jié)點鏈接的顏色

旋轉(zhuǎn)

旋轉(zhuǎn)原因：當(dāng)出現(xiàn)紅色右鏈接或者兩條連續(xù)的紅色鏈接時
旋轉(zhuǎn)操作：左旋是將兩個鍵中較小者作為根節(jié)點變?yōu)檩^大者作為根節(jié)點；右旋是將兩個鍵中較大者作為根節(jié)點變?yōu)檩^小者作為根節(jié)點。旋轉(zhuǎn)后返回一條鏈接重置父節(jié)點中相應(yīng)的鏈接。

顏色變化

如果一個結(jié)點的兩條鏈接都是紅色的，使用flipColors將子結(jié)點的顏色由紅變黑，同時父結(jié)點的顏色由黑變紅

根節(jié)點的顏色總是黑色

在每次插入后，都需要將根結(jié)點的顏色設(shè)為黑色。

2-節(jié)點插入新鍵

左邊：直接新增紅色結(jié)點
右邊：增加紅色結(jié)點后，左旋并修正根節(jié)點的鏈接root = rotateLeft(root)

2-結(jié)點插入示意圖

3-節(jié)點插入新鍵

右邊：增加紅色結(jié)點以后，進行顏色轉(zhuǎn)換
左邊：增加紅色結(jié)點后，右旋，再進行顏色轉(zhuǎn)換
中間：增加紅色結(jié)點后，先左旋下層鏈接，在右旋上層鏈接，在進行顏色轉(zhuǎn)換

3-結(jié)點插入示意圖

紅色鏈接在樹中向上傳遞

插入點到根節(jié)點的路徑上的每個結(jié)點必須完成以下操作：

1. 如果右子結(jié)點是紅色，而左子結(jié)點是黑色==> 左旋
2. 如果左子結(jié)點是紅色而它的左子節(jié)點是紅色==> 右旋
3. 如果左右子結(jié)點都是紅色==>顏色轉(zhuǎn)換

紅色鏈接傳遞示例

代碼實現(xiàn)

package edu.princeton.cs.algs4.chapter3;

/**
 * 使用紅黑樹實現(xiàn)的符號表
 * Created by tianxianhu on 2017/3/7.
 */
public class RedBlackBST<Key extends Comparable<Key>, Value> {

    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private Node root;

    private class Node{
        Key key;
        Value val;
        Node left, right;
        int N;
        boolean color; // 其父節(jié)點指向它的鏈接的顏色

        Node (Key key, Value val, int N, boolean color) {
            this.key = key;
            this.val = val;
            this.N = N;
            this.color = color;
        }

    }

    private boolean isRed (Node x) {
        if (x == null)
            return false;
        return RED == x.color;
    }

    public int size() {
        return size(root);
    }

    private int size(Node x) {
        if (x == null)
            return 0;
        return x.N;
    }

    /**
     * 尋找key，找到則更新它的值，否則為它創(chuàng)建一個新節(jié)點，同時更新節(jié)點數(shù)量
     * 創(chuàng)建的節(jié)點默認為紅色，可能會影響紅黑樹的平衡，需要進行調(diào)整
     * 1.如果左：黑 右：紅 ==> 左旋 ==> 2
     * 2.如果左：紅 左左：紅 ==> 右旋 ==> 3
     * 3.如果左：紅 右：紅 ==> flip
     * @param key
     * @param val
     */
    public void put(Key key, Value val) {
        if (key == null) throw new IllegalArgumentException("first argument to put() is null");
        if (val == null) {
            delete(key);
            return;
        }
        root = put(root, key, val);
        root.color = BLACK; // 根節(jié)點的顏色始終是黑色的
    }

    private Node put(Node x, Key key, Value val) {
        if (x == null)
            return new Node(key, val, 1, RED);
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            x.left = put(x.left, key, val);
        } else if (cmp > 0) {
            x.right = put(x.right, key, val);
        } else {
            x.val = val;
        }
        // 調(diào)整鏈接，保證紅黑樹的平衡
        if (isRed(x.right) && !isRed(x.left))
            x = rotateLeft(x);
        if (isRed(x.left) && isRed(x.left.left))
            x = rotateRight(x);
        if (isRed(x.left) && isRed(x.right))
            flipColors(x);
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }

    /**
     * 左旋改變h的右子節(jié)點
     * 1. 改變鏈接
     * 2. 改變顏色
     * 3. 更新計數(shù)
     * @param h
     * @return
     */
    private Node rotateLeft(Node h) {
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        x.color = h.color;
        h.color = RED;
        x.N = h.N;
        h.N = 1 + size(h.left) + size(h.right);
        return x;
    }

    /**
     * 右旋轉(zhuǎn)h的左鏈接
     * 1. 改變鏈接
     * 2. 改變顏色
     * 3. 更新計數(shù)
     */
    private Node rotateRight(Node h) {
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        x.color = h.color;
        h.color = RED;
        x.N = h.N;
        h.N = 1 + size(h.left) + size(h.right);
        return x;
    }

    /**
     * 左子節(jié)點和右子節(jié)點都為紅色的時候，將左右子節(jié)點變成黑色，根節(jié)點變成紅色
     * @param x
     */
    private void flipColors(Node x) {
        if (x == null)
            return;
        x.left.color = BLACK;
        x.right.color = BLACK;
        x.color = RED;
    }

    //TODO: 待實現(xiàn)
    public void delete(Key key) {

    }
}