二叉查找树的弊端在于要求构造树的键必须是随机的. 我们希望二叉查找树无论怎么构造他. 他的运行时间都是对数级别的.

在一课含有N个节点的树中. 希望树高为~~lgN, 这样能保证所有查找都能在~~lgN次比较内结束. 就和二分查找一样. 不幸的是. 在动态插入中保证树的完美平衡代价太高了.

2- 节点, 含有一个键和两条链接. 左链接指向的2-3树中的键都小于改节点. 右链接指向的2-3树中的键都大于改节点.
3- 节点, 含有二个键和三条链接. 左链接指向的2-3树中的键都小于该节点, 中链接指向的2-3树中的键都位于该节点的连个键之间. 右链接指向的2-3树中的键都大于该节点

查找

要判断一个键是否存在树中, 先将它和根节点中的键进行比较. 如果他和其中任意一个相等. 就命中. 否则就根据比较结果找到指向相应的区间的链接. 并在其指向的子树中递归地继续查找. 如果这是个空连接. 为命中.

插入

2- 节点中插入新建

如果未命中的查找结束语一个2- 节点. 直接把2- 节点替换为一个3- 节点, 将要插入的键保存在其中即可, 如果未命中的查找结束于一个3- 节点.

假设需要向一个颗只含有一个3- 节点的树中插入一个新建. 为了插入这个建. 先临时将新键存入改节点中. 使之成为一个4- 节点. 它很自然地拓展了以前的节点并含有3个键和4条连接. 创建一个4- 节点很方便, 也很容易将其装换为一个由3个2- 节点组成的2-3树. 其中一个节点含有中键.一个节点含有三个键中的最小者, 一个节点含有3个键中的最大者. 这颗树即是一颗含有3个节点的二叉查找树. 同时也是一颗完美平衡的2-3树. 见图1:

向一个父节点2-的3-节点插入新键

构造一个4-节点并将其分解. 但此时我们不会为中键创建一个新节点, 而是将其移动至原来的父节点中. 见图2:

向一个父节点为3-的节点的3-节点插入新键

构建一个4-节点, 然后将它的中键插入它的父节点中.父节点也成为4-节点, 然后在这个节点上进行相同的变换. 即分解这个父节点并将它的中键插入到它的父节点中去. 见图3:

![](/images/2-3树插入.jpg)

性质

和标准的二叉查找树由上向下生长不同. 2-3树的生长是由下向上的. 在二叉查找树中. 按照升序插入10个建会得到高度为9的一颗最差的树. 如果使用2-3树, 树的高度是2.

命题在一颗大小为N的2-3树中, 查找和插入操作访问的节点必然不超过lgN个

2-3树和二叉查找树大不相同. 可以确定的是即便是在最坏的情况下2-3树任有较好的性能. 每个操作中处理每个节点的时间都不会超过一个较小的常熟. 且这两个操作都会访问一条路径上的节点, 所以任何查找或者插入的成本都肯定不会超过对数级别. 例如: 含有10亿个节点的一颗2-3树的高度仅在19-30直接.最多只需要访问30个节点就能够在10亿个键中进行任意查找和插入操作.

这个真正的实现差距很大. 尽管可以用不同的数据类型表示2-和3-并写出变换所需的代码. 需要处理的情况实在太多了. 需要维护两种不同类型的节点, 实现这些不仅需要大量的代码. 而却所产生的额外开销可能会使算法比标准二叉查找树更慢. 平衡一棵树的初衷是为了消除最坏情况, 希望这种保障所需的代码越少越好.

红黑二叉查找树

2-3的算法不难理解. 但是实现起来太难了. 红黑二叉查找树结构简单. 代码量不大.

替换3- 节点

基本思想就是用标准的二叉查找树和一些额外的信息来表示2-3树. 将树中链接分为两种:

洪链接将两个2-节点连起来构成一个3-节点. 黑链接则是2-3树中的普通链接

这种表法的优点就是无需修改就可以直接使用标准二叉查找树的get()方法.

定义

红链接均为左链接
没有任何一个节点同时和两条红链接相连.
该树是完美黑色平衡的. 即任意空链接到根节点的路径上的黑链接数量相等

颜色表示

因为每个节点都只会有一条指向自己的链接. 将链接的颜色保存在表示节点的Node数据类型的布尔变量color中, 如果指向它的链接是红色的, 该变量为true, 黑色则为false, 约定空链接为黑色.

旋转

在实现一些操作时,会出现红色右链接或者两条连续的红链接. 但在操作完成前这些情况都会被小心地旋转并修复. 旋转操作回改变红链接的指向.



 *
 * 左旋转
 *
 *                 |                                           |
 *          h -> ( E )                                       ( S ) <- x
 *              /    \                                     //   
 *          (小于E)   ( S ) <- x         ----->     h->  ( E )  (大于S)
 *                   /                                 /   
 *             (介于E和  (大于S)                      (小于E) (E和S之间)
 *             S之间)
 * @param h 目标节点
 * @return Node 节点
 */
private Node (Node h) {
    Node x = h.right;
    h.right = x.left;
    x.left = h;
    x.color = x.left.color;
    x.left.color = RED;
    x.size = h.size;
    h.size = size(h.left) + size(h.right) + 1;
    return x;
}

/**
 *
 *      右旋转
 *
 *                 |                                         |
 *               ( S ) <- h                           x -> ( E )
 *              //                                       /    \
 *    x->   ( E )  (大于S)        ----->               (小于E)  ( S ) <- h
 *          /                                                 /   
 *     (小于E) (E和S之间)                                  (介于E和  (大于S)
 *                                                         S之间)
 * @param h 目标节点
 * @return Node 节点
 */
private Node rotateRight(Node h) {
    Node x = h.left;
    h.left = x.right;
    x.right = h;
    x.color = x.right.color;
    x.right.color = RED;
    x.size = h.size;
    h.size = size(h.left) + size(h.right) + 1;
    return x;
}

新键大于原树中的连个键. 因此他被链接到3-节点的右链接, 此事树是平衡的. 根节点为中间节点, 它有两条红色链接分别和较小和较大的节点相连. 我们需要将两条红色链接都变成黑色. 就可以得到一颗由三个节点组成的. 高度为2的平衡树.
新键小于原树中的两个键,.它会被链接到最左边的空链接. 这样就产生了两条连续的红链接. 这样只需要将上层的红链接右旋就得到了第一种情况.
如果新键在两个老键之间. 这又会产生两条连续的红链接. 一条红色的左链接连接着一条红色的右链接. 此时需要将下层的右红色链接左旋即可得到第二种情况.

总的来说通过0次 1次 2次选择以及颜色变化就可以得到期望的结果.

颜色转换

private void flipColors(Node h) {
       h.color = !h.color;
       h.left.color = !h.left.color;
       h.right.color = !h.right.color;
   }

完整实现

/**
 * @author Darcy
 * Created By Darcy on 2019-03-27 18:59
 */
public class RedBlackBST<Key extends Comparable<Key>, Value> {
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private Node root;

    /**
     *                                 h
     *                             |/_
     *  h.left.color = RED    (    E    )        h.right.color = BLACK
     *                  _|  //            |/_
     *                    ( C )         ( J )
     *                   /            //   
     *               ( A ) ( D )    ( G )
     *              /    /       /   
     *    // 红色节点   / 黑色节点
     */
    private class Node {
        /**
         * 键
         */
        private Key key;

        /**
         * 值
         */
        private Value val;

        /**
         * 左右链接
         */
        private Node left, right;

        /**
         * 由其父节点指向它的链接颜色
         */
        private boolean color;

        /**
         * 这个子树中的节点总数
         */
        private int size;

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


    public RedBlackBST() {
    }


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

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


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


    public boolean isEmpty() {
        return root == null;
    }


    public Value get(Key key) {
        if (key == null) {
            throw new IllegalArgumentException("argument to get() is null");
        }
        return get(root, key);
    }

    private Value get(Node x, Key key) {
        while (x != null) {
            int cmp = key.compareTo(x.key);
            if (cmp < 0) {
                x = x.left;
            } else if (cmp > 0) {
                x = x.right;
            } else {
                return x.val;
            }
        }
        return null;
    }


    public boolean contains(Key key) {
        return get(key) != null;
    }

    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;
    }

    private Node put(Node h, Key key, Value val) {
        if (h == null) {
            return new Node(key, val, RED, 1);
        }

        int cmp = key.compareTo(h.key);
        if (cmp < 0) {
            h.left = put(h.left, key, val);
        } else if (cmp > 0) {
            h.right = put(h.right, key, val);
        } else {
            h.val = val;
        }

        if (isRed(h.right) && !isRed(h.left)) {
            h = rotateLeft(h);
        }
        if (isRed(h.left) && isRed(h.left.left)) {
            h = rotateRight(h);
        }
        if (isRed(h.left) && isRed(h.right)) {
            flipColors(h);
        }
        h.size = size(h.left) + size(h.right) + 1;
        return h;
    }


    public void deleteMin() {
        if (isEmpty()) {
            throw new NoSuchElementException("BST underflow");
        }

        if (!isRed(root.left) && !isRed(root.right)) {
            root.color = RED;
        }

        root = deleteMin(root);
        if (!isEmpty()) {
            root.color = BLACK;
        }
    }

    private Node deleteMin(Node h) {
        if (h.left == null) {
            return null;
        }
        if (!isRed(h.left) && !isRed(h.left.left)) {
            h = moveRedLeft(h);
        }
        h.left = deleteMin(h.left);
        return balance(h);
    }


    public void deleteMax() {
        if (isEmpty()) {
            throw new NoSuchElementException("BST underflow");
        }
        if (!isRed(root.left) && !isRed(root.right)) {
            root.color = RED;
        }
        root = deleteMax(root);
        if (!isEmpty()) {
            root.color = BLACK;
        }
    }

    private Node deleteMax(Node h) {
        if (isRed(h.left)) {
            h = rotateRight(h);
        }
        if (h.right == null) {
            return null;
        }
        if (!isRed(h.right) && !isRed(h.right.left)) {
            h = moveRedRight(h);
        }
        h.right = deleteMax(h.right);
        return balance(h);
    }


    public void delete(Key key) {
        if (key == null) {
            throw new IllegalArgumentException("argument to delete() is null");
        }
        if (!contains(key)) {
            return;
        }
        if (!isRed(root.left) && !isRed(root.right)) {
            root.color = RED;
        }
        root = delete(root, key);
        if (!isEmpty()) {
            root.color = BLACK;
        }
    }

    private Node delete(Node h, Key key) {
        if (key.compareTo(h.key) < 0) {
            if (!isRed(h.left) && !isRed(h.left.left)) {
                h = moveRedLeft(h);
            }
            h.left = delete(h.left, key);
        } else {
            if (isRed(h.left)) {
                h = rotateRight(h);
            }
            if (key.compareTo(h.key) == 0 && (h.right == null)) {
                return null;
            }
            if (!isRed(h.right) && !isRed(h.right.left)) {
                h = moveRedRight(h);
            }
            if (key.compareTo(h.key) == 0) {
                Node x = min(h.right);
                h.key = x.key;
                h.val = x.val;
                // h.val = get(h.right, min(h.right).key);
                // h.key = min(h.right).key;
                h.right = deleteMin(h.right);
            } else {
                h.right = delete(h.right, key);
            }
        }
        return balance(h);
    }

    /**
     *
     * 左旋转
     *
     *                  |                                           |
     *          h -> ( E )                                       ( S ) <- x
     *              /    \                                     //   
     *          (小于E)   ( S ) <- x         ----->     h->  ( E )  (大于S)
     *                   /                                 /   
     *             (介于E和  (大于S)                      (小于E) (E和S之间)
     *             S之间)
     * @param h 目标节点
     * @return Node 节点
     */
    private Node rotateLeft(Node h) {
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        x.color = x.left.color;
        x.left.color = RED;
        x.size = h.size;
        h.size = size(h.left) + size(h.right) + 1;
        return x;
    }

    /**
     *
     *      右旋转
     *
     *                  |                                        |
     *               ( S ) <- h                           x -> ( E )
     *              //                                       /    \
     *    x->  ( E )  (大于S)        ----->               (小于E)   ( S ) <- h
     *          /                                                 /   
     *     (小于E) (E和S之间)                                  (介于E和  (大于S)
     *                                                         S之间)
     * @param h 目标节点
     * @return Node 节点
     */
    private Node rotateRight(Node h) {
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        x.color = x.right.color;
        x.right.color = RED;
        x.size = h.size;
        h.size = size(h.left) + size(h.right) + 1;
        return x;
    }
    private void flipColors(Node h) {
        h.color = !h.color;
        h.left.color = !h.left.color;
        h.right.color = !h.right.color;
    }


    private Node moveRedLeft(Node h) {
        flipColors(h);
        if (isRed(h.right.left)) {
            h.right = rotateRight(h.right);
            h = rotateLeft(h);
            flipColors(h);
        }
        return h;
    }


    private Node moveRedRight(Node h) {
        flipColors(h);
        if (isRed(h.left.left)) {
            h = rotateRight(h);
            flipColors(h);
        }
        return h;
    }

    private Node balance(Node h) {
        if (isRed(h.right)) {
            h = rotateLeft(h);
        }
        if (isRed(h.left) && isRed(h.left.left)) {
            h = rotateRight(h);
        }
        if (isRed(h.left) && isRed(h.right)) {
            flipColors(h);
        }
        h.size = size(h.left) + size(h.right) + 1;
        return h;
    }


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

    private int height(Node x) {
        if (x == null) {
            return -1;
        }
        return 1 + Math.max(height(x.left), height(x.right));
    }


    public Key min() {
        if (isEmpty()) {
            throw new NoSuchElementException("calls min() with empty symbol table");
        }
        return min(root).key;
    }

    private Node min(Node x) {
        if (x.left == null) {
            return x;
        } else {
            return min(x.left);
        }
    }


    public Key max() {
        if (isEmpty()) {
            throw new NoSuchElementException("calls max() with empty symbol table");
        }
        return max(root).key;
    }

    private Node max(Node x) {
        // assert x != null;
        if (x.right == null) {
            return x;
        } else {
            return max(x.right);
        }
    }


    public Key floor(Key key) {
        if (key == null) {
            throw new IllegalArgumentException("argument to floor() is null");
        }
        if (isEmpty()) {
            throw new NoSuchElementException("calls floor() with empty symbol table");
        }
        Node x = floor(root, key);
        if (x == null) {
            return null;
        } else {
            return x.key;
        }
    }

    private Node floor(Node x, Key key) {
        if (x == null) {
            return null;
        }
        int cmp = key.compareTo(x.key);
        if (cmp == 0) {
            return x;
        }
        if (cmp < 0) {
            return floor(x.left, key);
        }
        Node t = floor(x.right, key);
        if (t != null) {
            return t;
        } else {
            return x;
        }
    }


    public Key ceiling(Key key) {
        if (key == null) {
            throw new IllegalArgumentException("argument to ceiling() is null");
        }
        if (isEmpty()) {
            throw new NoSuchElementException("calls ceiling() with empty symbol table");
        }
        Node x = ceiling(root, key);
        if (x == null) {
            return null;
        } else {
            return x.key;
        }
    }

    private Node ceiling(Node x, Key key) {
        if (x == null) {
            return null;
        }
        int cmp = key.compareTo(x.key);
        if (cmp == 0) {
            return x;
        }
        if (cmp > 0) {
            return ceiling(x.right, key);
        }
        Node t = ceiling(x.left, key);
        if (t != null) {
            return t;
        } else {
            return x;
        }
    }


    public Key select(int k) {
        if (k < 0 || k >= size()) {
            throw new IllegalArgumentException("argument to select() is invalid: " + k);
        }
        Node x = select(root, k);
        return x.key;
    }

    private Node select(Node x, int k) {
        // assert x != null;
        // assert k >= 0 && k < size(x);
        int t = size(x.left);
        if (t > k) {
            return select(x.left, k);
        } else if (t < k) {
            return select(x.right, k - t - 1);
        } else {
            return x;
        }
    }

    public int rank(Key key) {
        if (key == null) {
            throw new IllegalArgumentException("argument to rank() is null");
        }
        return rank(key, root);
    }

    private int rank(Key key, Node x) {
        if (x == null) {
            return 0;
        }
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            return rank(key, x.left);
        } else if (cmp > 0) {
            return 1 + size(x.left) + rank(key, x.right);
        } else {
            return size(x.left);
        }
    }


    public Iterable<Key> keys() {
        if (isEmpty()) {
            return new Queue<Key>();
        }
        return keys(min(), max());
    }


    public Iterable<Key> keys(Key lo, Key hi) {
        if (lo == null) {
            throw new IllegalArgumentException("first argument to keys() is null");
        }
        if (hi == null) {
            throw new IllegalArgumentException("second argument to keys() is null");
        }
        Queue<Key> queue = new Queue<Key>();
        keys(root, queue, lo, hi);
        return queue;
    }


    private void keys(Node x, Queue<Key> queue, Key lo, Key hi) {
        if (x == null) {
            return;
        }
        int cmplo = lo.compareTo(x.key);
        int cmphi = hi.compareTo(x.key);
        if (cmplo < 0) {
            keys(x.left, queue, lo, hi);
        }
        if (cmplo <= 0 && cmphi >= 0) {
            queue.enqueue(x.key);
        }
        if (cmphi > 0) {
            keys(x.right, queue, lo, hi);
        }
    }


    public int size(Key lo, Key hi) {
        if (lo == null) {
            throw new IllegalArgumentException("first argument to size() is null");
        }
        if (hi == null) {
            throw new IllegalArgumentException("second argument to size() is null");
        }

        if (lo.compareTo(hi) > 0) {
            return 0;
        }
        if (contains(hi)) {
            return rank(hi) - rank(lo) + 1;
        } else {
            return rank(hi) - rank(lo);
        }
    }


    private boolean check() {
        if (!isBST()) {
            StdOut.println("Not in symmetric order");
        }
        if (!isSizeConsistent()) {
            StdOut.println("Subtree counts not consistent");
        }
        if (!isRankConsistent()) {
            StdOut.println("Ranks not consistent");
        }
        if (!is23()) {
            StdOut.println("Not a 2-3 tree");
        }
        if (!isBalanced()) {
            StdOut.println("Not balanced");
        }
        return isBST() && isSizeConsistent() && isRankConsistent() && is23() && isBalanced();
    }


    private boolean isBST() {
        return isBST(root, null, null);
    }


    private boolean isBST(Node x, Key min, Key max) {
        if (x == null) {
            return true;
        }
        if (min != null && x.key.compareTo(min) <= 0) {
            return false;
        }
        if (max != null && x.key.compareTo(max) >= 0) {
            return false;
        }
        return isBST(x.left, min, x.key) && isBST(x.right, x.key, max);
    }

    private boolean isSizeConsistent() {
        return isSizeConsistent(root);
    }

    private boolean isSizeConsistent(Node x) {
        if (x == null) {
            return true;
        }
        if (x.size != size(x.left) + size(x.right) + 1) {
            return false;
        }
        return isSizeConsistent(x.left) && isSizeConsistent(x.right);
    }

    private boolean isRankConsistent() {
        for (int i = 0; i < size(); i++) {
            if (i != rank(select(i))) return false;
        }
        for (Key key : keys()) {
            if (key.compareTo(select(rank(key))) != 0) {
                return false;
            }
        }
        return true;
    }


    private boolean is23() {
        return is23(root);
    }

    private boolean is23(Node x) {
        if (x == null) {
            return true;
        }
        if (isRed(x.right)) {
            return false;
        }
        if (x != root && isRed(x) && isRed(x.left)) {
            return false;
        }
        return is23(x.left) && is23(x.right);
    }

    private boolean isBalanced() {
        int black = 0;
        Node x = root;
        while (x != null) {
            if (!isRed(x)) {
                black++;
            }
            x = x.left;
        }
        return isBalanced(root, black);
    }

    private boolean isBalanced(Node x, int black) {
        if (x == null) {
            return black == 0;
        }
        if (!isRed(x)) {
            black--;
        }
        return isBalanced(x.left, black) && isBalanced(x.right, black);
    }


    public static void main(String[] args) {
        RedBlackBST<String, Integer> st = new RedBlackBST<>();
        for (int i = 0; !StdIn.isEmpty(); i++) {
            String key = StdIn.readString();
            st.put(key, i);
        }
        for (String s : st.keys()) {
            StdOut.println(s + " " + st.get(s));
        }
        StdOut.println();
    }
}

性质

所有基于红黑树的符号表实现都能保证操作的运行时间为对数级别(范围查找除外, 它所需的额外时间和返回的键的数量成正比)

平衡查找树红黑二叉查找树

查找

插入

2- 节点中插入新建

3- 节点插入新建

向一个父节点2-的3-节点插入新键

向一个父节点为3-的节点的3-节点插入新键

性质

红黑二叉查找树

替换3- 节点

定义

颜色表示

旋转

向单个2- 节点中插入新建

向树底部的2- 节点插入新键

向一颗双键树(即3- 节点)中插入新键

颜色转换

完整实现

性质

近期文章

近期评论

标签

热门

文章归档

分类目录

功能