算法复习 (二) 查找-平衡查找树

平衡查找树

第一节 概述

1.1 什么是平衡树

平衡树属于计算机科学领域的一种数据结构，是改进的二叉查找树。一般的二叉查找树查询时取决于目标结点的深度，所以当结点的深度普遍较大时，查询操作复杂度会上升，平衡树就是为了实现高效的查询而产生的。

平衡是指树的所有叶子结点趋于平衡。

平衡树通常通过旋转操作来使树趋于平衡。

1.2 常见平衡树

• AVL树：最早的平衡二叉查找树，命名来自于其发明者 G. M. Adelson-Velsky 和 Evgenii Landis 。
  • 在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。
  • 查找、插入和删除在平均和最坏情况下的时间复杂度都是 O(logn) 。
  • 增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。
  • 节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。
• 树堆（Treap）：是有一个随机附加域满足堆的性质的二叉搜索树，其结构相当于以随机数据插入的二叉搜索树。其基本操作的期望时间复杂度为 O(logn) 。相对于其他的平衡二叉搜索树，Treap的特点是实现简单，且能基本实现随机平衡的结构。
• 伸展树（Splay tree）：能在均摊 O(logn) 的时间内完成基于伸展（Splay）操作的插入、查找、修改和删除操作。由丹尼尔·斯立特（Daniel Sleator）和罗伯特·塔扬在1985年发明的。
  • 在伸展树上的一般操作都基于伸展操作：假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法，在每次查找之后对树进行调整，把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。
  • 伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。 它的优势在于不需要记录用于平衡树的冗余信息。
• 加权平衡树（Weight balanced tree）：加权平衡树的每个结点储存这个结点下子树的大小，可以用来实现顺序统计树操作。优势在于占用空间相对较小。
• 2-3树：其内部节点（存在子节点的节点）要么有2个孩子和1个数据元素，要么有3个孩子和2个数据元素，叶子节点没有孩子，并且有1个或2个数据元素。2–3树和AA树是等距同构的，换句话说，对于每个2–3树，都至少有1个AA树和它的元素排列是相同的。
• 红黑树（Red–black tree）：在1972年由鲁道夫·贝尔发明，被称为”对称二叉B树“，它现代的名字源于 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文。红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中高效：它可以在 O(logn) 时间内完成查找，插入和删除。
• AA树：AA树是红黑树的一种变种，是 Arne Andersson 教授在1993年年在他的论文”Balanced search trees made simple”中介绍，设计的目的是减少红黑树考虑的不同情况，区别于红黑树的是，AA树的红节点只能作为右叶子。换句话说，没有红节点可以是一个左子儿。这导致代替2-3-4树，从而大大简化了维护2-3树的模拟。
• 替罪羊树：其平衡基于部分重建，在非平衡的二叉搜索树中，每次操作以后检查操作路径，找到最高的满足左右子树大小大于平衡因子（alpha）乘以自身大小的结点，重建整个子树。这样就得到了替罪羊树，而被重建的子树的原来的根就被称为替罪羊节点。

1.3 应用场景

用于表示有序的线性数据结构，如优先队列、关联数组、键(key)-值(value)的映射等。

自平衡的二叉查找树与哈希表的相比，各有优缺。平衡树在按序遍历所有键值时是量级最优的，哈希表不能。自平衡二叉查找树在查找一个键值时，最坏情况下时间复杂度优于哈希表， O(logn) 对比 O(n) ；但平均时间复杂度逊于hash表， O(logn) 对比 O(1) 。

平衡树的排序方法，虽然在平均时间复杂度上也是 O(logn) ，但由于cache性能、树的调整操作等，性能上不如快速排序、堆排序、归并排序等同为 O(logn) 复杂度的排序。

第二节 AVL树

2.1 概述

在计算机科学中，AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是 O(logn) 。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。

节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2 或 2 的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。

2.2 操作

AVL树的基本操作一般涉及运作同在不平衡的二叉查找树所运作的同样的算法。但是要进行预先或随后做一次或多次所谓的”AVL旋转”。

以下图表以四列表示四种情况，每行表示在该种情况下要进行的操作。在左左和右右的情况下，只需要进行一次旋转操作；在左右和右左的情况下，需要进行两次旋转操作。

2.3 算法描述

假设平衡因子是左子树的高度减去右子树的高度所得到的值，又假设由于在二叉排序树上插入节点而失去平衡的最小子树根节点的指针为a（即a是离插入点最近，且平衡因子绝对值超过1的祖先节点），则失去平衡后进行的规律可归纳为下列四种情况：

1. 单向右旋平衡处理LL：由于在 *a 的左子树根节点的左子树上插入节点，*a 的平衡因子由1增至2，致使以 *a 为根的子树失去平衡，则需进行一次右旋转操作；
2. 单向左旋平衡处理RR：由于在 *a 的右子树根节点的右子树上插入节点， *a 的平衡因子由-1变为-2，致使以 *a 为根的子树失去平衡，则需进行一次左旋转操作；
3. 双向旋转（先左后右）平衡处理LR：由于在 *a 的左子树根节点的右子树上插入节点， *a 的平衡因子由1增至2，致使以 *a 为根的子树失去平衡，则需进行两次旋转（先左旋后右旋）操作。
4. 双向旋转（先右后左）平衡处理RL：由于在 *a 的右子树根节点的左子树上插入节点， *a 的平衡因子由-1变为-2，致使以 *a 为根的子树失去平衡，则需进行两次旋转（先右旋后左旋）操作。

在平衡的二叉排序树BBST (Balancing Binary Search Tree)上插入一个新的数据元素e的递归算法可描述如下：

1. 若BBST为空树，则插入一个数据元素为e的新节点作为BBST的根节点，树的深度增1；
2. 若e的关键字和BBST的根节点的关键字相等，则不进行；
3. 若e的关键字小于BBST的根节点的关键字，而且在BBST的左子树中不存在和e有相同关键字的节点，则将e插入在BBST的左子树上，并且当插入之后的左子树深度增加（+1）时，分别就下列不同情况处理之：
   1. BBST的根节点的平衡因子为-1（右子树的深度大于左子树的深度，则将根节点的平衡因子更改为0，BBST的深度不变；
   2. BBST的根节点的平衡因子为0（左、右子树的深度相等）：则将根节点的平衡因子更改为1，BBST的深度增1；
   3. BBST的根节点的平衡因子为1（左子树的深度大于右子树的深度）：则若BBST的左子树根节点的平衡因子为1：则需进行单向右旋平衡处理，并且在右旋处理之后，将根节点和其右子树根节点的平衡因子更改为0，树的深度不变；
4. 若e的关键字大于BBST的根节点的关键字，而且在BBST的右子树中不存在和e有相同关键字的节点，则将e插入在BBST的右子树上，并且当插入之后的右子树深度增加（+1）时，分别就不同情况处理之。

2.4 实现

实现代码如下：

public class AVLTreeST<Key extends Comparable<Key>, Value> {

    /**
     * The root node.
     */
    private Node root;

    /**
     * This class represents an inner node of the AVL tree.
     */
    private class Node {
        private final Key key;   // the key
        private Value val;       // the associated value
        private int height;      // height of the subtree
        private int size;        // number of nodes in subtree
        private Node left;       // left subtree
        private Node right;      // right subtree

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

    /**
     * Initializes an empty symbol table.
     */
    public AVLTreeST() {
    }

    /**
     * Checks if the symbol table is empty.
     * 
     * @return {@code true} if the symbol table is empty.
     */
    public boolean isEmpty() {
        return root == null;
    }

    /**
     * Returns the number key-value pairs in the symbol table.
     * 
     * @return the number key-value pairs in the symbol table
     */
    public int size() {
        return size(root);
    }

    /**
     * Returns the number of nodes in the subtree.
     * 
     * @param x the subtree
     * 
     * @return the number of nodes in the subtree
     */
    private int size(Node x) {
        if (x == null) return 0;
        return x.size;
    }

    /**
     * Returns the height of the internal AVL tree. It is assumed that the
     * height of an empty tree is -1 and the height of a tree with just one node
     * is 0.
     * 
     * @return the height of the internal AVL tree
     */
    public int height() {
        return height(root);
    }

    /**
     * Returns the height of the subtree.
     * 
     * @param x the subtree
     * 
     * @return the height of the subtree.
     */
    private int height(Node x) {
        if (x == null) return -1;
        return x.height;
    }

    /**
     * Returns the value associated with the given key.
     * 
     * @param key the key
     * @return the value associated with the given key if the key is in the
     *         symbol table and {@code null} if the key is not in the
     *         symbol table
     * @throws IllegalArgumentException if {@code key} is {@code null}
     */
    public Value get(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to get() is null");
        Node x = get(root, key);
        if (x == null) return null;
        return x.val;
    }

    /**
     * Returns value associated with the given key in the subtree or
     * {@code null} if no such key.
     * 
     * @param x the subtree
     * @param key the key
     * @return value associated with the given key in the subtree or
     *         {@code null} if no such key
     */
    private Node get(Node x, Key key) {
        if (x == null) return null;
        int cmp = key.compareTo(x.key);
        if (cmp < 0) return get(x.left, key);
        else if (cmp > 0) return get(x.right, key);
        else return x;
    }

    /**
     * Checks if the symbol table contains the given key.
     * 
     * @param key the key
     * @return {@code true} if the symbol table contains {@code key}
     *         and {@code false} otherwise
     * @throws IllegalArgumentException if {@code key} is {@code null}
     */
    public boolean contains(Key key) {
        return get(key) != null;
    }

    /**
     * Inserts the specified key-value pair into the symbol table, overwriting
     * the old value with the new value if the symbol table already contains the
     * specified key. Deletes the specified key (and its associated value) from
     * this symbol table if the specified value is {@code null}.
     * 
     * @param key the key
     * @param val the value
     * @throws IllegalArgumentException if {@code key} is {@code 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);
        assert check();
    }

    /**
     * Inserts the key-value pair in the subtree. It overrides the old value
     * with the new value if the symbol table already contains the specified key
     * and deletes the specified key (and its associated value) from this symbol
     * table if the specified value is {@code null}.
     * 
     * @param x the subtree
     * @param key the key
     * @param val the value
     * @return the subtree
     */
    private Node put(Node x, Key key, Value val) {
        if (x == null) return new Node(key, val, 0, 1);
        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;
            return x;
        }
        x.size = 1 + size(x.left) + size(x.right);
        x.height = 1 + Math.max(height(x.left), height(x.right));
        return balance(x);
    }

    /**
     * Restores the AVL tree property of the subtree.
     * 
     * @param x the subtree
     * @return the subtree with restored AVL property
     */
    private Node balance(Node x) {
        if (balanceFactor(x) < -1) {
            if (balanceFactor(x.right) > 0) {
                x.right = rotateRight(x.right);
            }
            x = rotateLeft(x);
        }
        else if (balanceFactor(x) > 1) {
            if (balanceFactor(x.left) < 0) {
                x.left = rotateLeft(x.left);
            }
            x = rotateRight(x);
        }
        return x;
    }

    /**
     * Returns the balance factor of the subtree. The balance factor is defined
     * as the difference in height of the left subtree and right subtree, in
     * this order. Therefore, a subtree with a balance factor of -1, 0 or 1 has
     * the AVL property since the heights of the two child subtrees differ by at
     * most one.
     * 
     * @param x the subtree
     * @return the balance factor of the subtree
     */
    private int balanceFactor(Node x) {
        return height(x.left) - height(x.right);
    }

    /**
     * Rotates the given subtree to the right.
     * 
     * @param x the subtree
     * @return the right rotated subtree
     */
    private Node rotateRight(Node x) {
        Node y = x.left;
        x.left = y.right;
        y.right = x;
        y.size = x.size;
        x.size = 1 + size(x.left) + size(x.right);
        x.height = 1 + Math.max(height(x.left), height(x.right));
        y.height = 1 + Math.max(height(y.left), height(y.right));
        return y;
    }

    /**
     * Rotates the given subtree to the left.
     * 
     * @param x the subtree
     * @return the left rotated subtree
     */
    private Node rotateLeft(Node x) {
        Node y = x.right;
        x.right = y.left;
        y.left = x;
        y.size = x.size;
        x.size = 1 + size(x.left) + size(x.right);
        x.height = 1 + Math.max(height(x.left), height(x.right));
        y.height = 1 + Math.max(height(y.left), height(y.right));
        return y;
    }

    /**
     * Removes the specified key and its associated value from the symbol table
     * (if the key is in the symbol table).
     * 
     * @param key the key
     * @throws IllegalArgumentException if {@code key} is {@code null}
     */
    public void delete(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to delete() is null");
        if (!contains(key)) return;
        root = delete(root, key);
        assert check();
    }

    /**
     * Removes the specified key and its associated value from the given
     * subtree.
     * 
     * @param x the subtree
     * @param key the key
     * @return the updated subtree
     */
    private Node delete(Node x, Key key) {
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            x.left = delete(x.left, key);
        }
        else if (cmp > 0) {
            x.right = delete(x.right, key);
        }
        else {
            if (x.left == null) {
                return x.right;
            }
            else if (x.right == null) {
                return x.left;
            }
            else {
                Node y = x;
                x = min(y.right);
                x.right = deleteMin(y.right);
                x.left = y.left;
            }
        }
        x.size = 1 + size(x.left) + size(x.right);
        x.height = 1 + Math.max(height(x.left), height(x.right));
        return balance(x);
    }

    /**
     * Removes the smallest key and associated value from the symbol table.
     * 
     * @throws NoSuchElementException if the symbol table is empty
     */
    public void deleteMin() {
        if (isEmpty()) throw new NoSuchElementException("called deleteMin() with empty symbol table");
        root = deleteMin(root);
        assert check();
    }

    /**
     * Removes the smallest key and associated value from the given subtree.
     * 
     * @param x the subtree
     * @return the updated subtree
     */
    private Node deleteMin(Node x) {
        if (x.left == null) return x.right;
        x.left = deleteMin(x.left);
        x.size = 1 + size(x.left) + size(x.right);
        x.height = 1 + Math.max(height(x.left), height(x.right));
        return balance(x);
    }

    /**
     * Removes the largest key and associated value from the symbol table.
     * 
     * @throws NoSuchElementException if the symbol table is empty
     */
    public void deleteMax() {
        if (isEmpty()) throw new NoSuchElementException("called deleteMax() with empty symbol table");
        root = deleteMax(root);
        assert check();
    }

    /**
     * Removes the largest key and associated value from the given subtree.
     * 
     * @param x the subtree
     * @return the updated subtree
     */
    private Node deleteMax(Node x) {
        if (x.right == null) return x.left;
        x.right = deleteMax(x.right);
        x.size = 1 + size(x.left) + size(x.right);
        x.height = 1 + Math.max(height(x.left), height(x.right));
        return balance(x);
    }

    /**
     * Returns the smallest key in the symbol table.
     * 
     * @return the smallest key in the symbol table
     * @throws NoSuchElementException if the symbol table is empty
     */
    public Key min() {
        if (isEmpty()) throw new NoSuchElementException("called min() with empty symbol table");
        return min(root).key;
    }

    /**
     * Returns the node with the smallest key in the subtree.
     * 
     * @param x the subtree
     * @return the node with the smallest key in the subtree
     */
    private Node min(Node x) {
        if (x.left == null) return x;
        return min(x.left);
    }

    /**
     * Returns the largest key in the symbol table.
     * 
     * @return the largest key in the symbol table
     * @throws NoSuchElementException if the symbol table is empty
     */
    public Key max() {
        if (isEmpty()) throw new NoSuchElementException("called max() with empty symbol table");
        return max(root).key;
    }

    /**
     * Returns the node with the largest key in the subtree.
     * 
     * @param x the subtree
     * @return the node with the largest key in the subtree
     */
    private Node max(Node x) {
        if (x.right == null) return x;
        return max(x.right);
    }

    /**
     * Returns the largest key in the symbol table less than or equal to
     * {@code key}.
     * 
     * @param key the key
     * @return the largest key in the symbol table less than or equal to
     *         {@code key}
     * @throws NoSuchElementException if the symbol table is empty
     * @throws IllegalArgumentException if {@code key} is {@code null}
     */
    public Key floor(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to floor() is null");
        if (isEmpty()) throw new NoSuchElementException("called floor() with empty symbol table");
        Node x = floor(root, key);
        if (x == null) return null;
        else return x.key;
    }

    /**
     * Returns the node in the subtree with the largest key less than or equal
     * to the given key.
     * 
     * @param x the subtree
     * @param key the key
     * @return the node in the subtree with the largest key less than or equal
     *         to the given 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 y = floor(x.right, key);
        if (y != null) return y;
        else return x;
    }

    /**
     * Returns the smallest key in the symbol table greater than or equal to
     * {@code key}.
     * 
     * @param key the key
     * @return the smallest key in the symbol table greater than or equal to
     *         {@code key}
     * @throws NoSuchElementException if the symbol table is empty
     * @throws IllegalArgumentException if {@code key} is {@code null}
     */
    public Key ceiling(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to ceiling() is null");
        if (isEmpty()) throw new NoSuchElementException("called ceiling() with empty symbol table");
        Node x = ceiling(root, key);
        if (x == null) return null;
        else return x.key;
    }

    /**
     * Returns the node in the subtree with the smallest key greater than or
     * equal to the given key.
     * 
     * @param x the subtree
     * @param key the key
     * @return the node in the subtree with the smallest key greater than or
     *         equal to the given 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 y = ceiling(x.left, key);
        if (y != null) return y;
        else return x;
    }

    /**
     * Returns the kth smallest key in the symbol table.
     * 
     * @param k the order statistic
     * @return the kth smallest key in the symbol table
     * @throws IllegalArgumentException unless {@code k} is between 0 and
     *             {@code size() -1 }
     */
    public Key select(int k) {
        if (k < 0 || k >= size()) throw new IllegalArgumentException("k is not in range 0-" + (size() - 1));
        Node x = select(root, k);
        return x.key;
    }

    /**
     * Returns the node with key the kth smallest key in the subtree.
     * 
     * @param x the subtree
     * @param k the kth smallest key in the subtree
     * @return the node with key the kth smallest key in the subtree
     */
    private Node select(Node x, int k) {
        if (x == null) return null;
        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;
    }

    /**
     * Returns the number of keys in the symbol table strictly less than
     * {@code key}.
     * 
     * @param key the key
     * @return the number of keys in the symbol table strictly less than
     *         {@code key}
     * @throws IllegalArgumentException if {@code key} is {@code null}
     */
    public int rank(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to rank() is null");
        return rank(key, root);
    }

    /**
     * Returns the number of keys in the subtree less than key.
     * 
     * @param key the key
     * @param x the subtree
     * @return the number of keys in the subtree less than key
     */
    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);
    }

    /**
     * Returns all keys in the symbol table.
     * 
     * @return all keys in the symbol table
     */
    public Iterable<Key> keys() {
        return keysInOrder();
    }

    /**
     * Returns all keys in the symbol table following an in-order traversal.
     * 
     * @return all keys in the symbol table following an in-order traversal
     */
    public Iterable<Key> keysInOrder() {
        Queue<Key> queue = new Queue<Key>();
        keysInOrder(root, queue);
        return queue;
    }

    /**
     * Adds the keys in the subtree to queue following an in-order traversal.
     * 
     * @param x the subtree
     * @param queue the queue
     */
    private void keysInOrder(Node x, Queue<Key> queue) {
        if (x == null) return;
        keysInOrder(x.left, queue);
        queue.enqueue(x.key);
        keysInOrder(x.right, queue);
    }

    /**
     * Returns all keys in the symbol table following a level-order traversal.
     * 
     * @return all keys in the symbol table following a level-order traversal.
     */
    public Iterable<Key> keysLevelOrder() {
        Queue<Key> queue = new Queue<Key>();
        if (!isEmpty()) {
            Queue<Node> queue2 = new Queue<Node>();
            queue2.enqueue(root);
            while (!queue2.isEmpty()) {
                Node x = queue2.dequeue();
                queue.enqueue(x.key);
                if (x.left != null) {
                    queue2.enqueue(x.left);
                }
                if (x.right != null) {
                    queue2.enqueue(x.right);
                }
            }
        }
        return queue;
    }

    /**
     * Returns all keys in the symbol table in the given range.
     * 
     * @param lo the lowest key
     * @param hi the highest key
     * @return all keys in the symbol table between {@code lo} (inclusive)
     *         and {@code hi} (exclusive)
     * @throws IllegalArgumentException if either {@code lo} or {@code hi}
     *             is {@code null}
     */
    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;
    }

    /**
     * Adds the keys between {@code lo} and {@code hi} in the subtree
     * to the {@code queue}.
     * 
     * @param x the subtree
     * @param queue the queue
     * @param lo the lowest key
     * @param hi the highest key
     */
    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);
    }

    /**
     * Returns the number of keys in the symbol table in the given range.
     * 
     * @param lo minimum endpoint
     * @param hi maximum endpoint
     * @return the number of keys in the symbol table between {@code lo}
     *         (inclusive) and {@code hi} (exclusive)
     * @throws IllegalArgumentException if either {@code lo} or {@code hi}
     *             is {@code null}
     */
    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);
    }

    /**
     * Checks if the AVL tree invariants are fine.
     * 
     * @return {@code true} if the AVL tree invariants are fine
     */
    private boolean check() {
        if (!isBST()) StdOut.println("Symmetric order not consistent");
        if (!isAVL()) StdOut.println("AVL property not consistent");
        if (!isSizeConsistent()) StdOut.println("Subtree counts not consistent");
        if (!isRankConsistent()) StdOut.println("Ranks not consistent");
        return isBST() && isAVL() && isSizeConsistent() && isRankConsistent();
    }

    /**
     * Checks if AVL property is consistent.
     * 
     * @return {@code true} if AVL property is consistent.
     */
    private boolean isAVL() {
        return isAVL(root);
    }

    /**
     * Checks if AVL property is consistent in the subtree.
     * 
     * @param x the subtree
     * @return {@code true} if AVL property is consistent in the subtree
     */
    private boolean isAVL(Node x) {
        if (x == null) return true;
        int bf = balanceFactor(x);
        if (bf > 1 || bf < -1) return false;
        return isAVL(x.left) && isAVL(x.right);
    }

    /**
     * Checks if the symmetric order is consistent.
     * 
     * @return {@code true} if the symmetric order is consistent
     */
    private boolean isBST() {
        return isBST(root, null, null);
    }

    /**
     * Checks if the tree rooted at x is a BST with all keys strictly between
     * min and max (if min or max is null, treat as empty constraint) Credit:
     * Bob Dondero's elegant solution
     * 
     * @param x the subtree
     * @param min the minimum key in subtree
     * @param max the maximum key in subtree
     * @return {@code true} if if the symmetric order is consistent
     */
    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);
    }

    /**
     * Checks if size is consistent.
     * 
     * @return {@code true} if size is consistent
     */
    private boolean isSizeConsistent() {
        return isSizeConsistent(root);
    }

    /**
     * Checks if the size of the subtree is consistent.
     * 
     * @return {@code true} if the size of the subtree is consistent
     */
    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);
    }

    /**
     * Checks if rank is consistent.
     * 
     * @return {@code true} if rank is consistent
     */
    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;
    }

    /**
     * Unit tests the {@code AVLTreeST} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) {
        AVLTreeST<String, Integer> st = new AVLTreeST<String, Integer>();
        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();
    }
}

/******************************************************************************
 *  Copyright 2002-2020, Robert Sedgewick and Kevin Wayne.
 *
 *  This file is part of algs4.jar, which accompanies the textbook
 *
 *      Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne,
 *      Addison-Wesley Professional, 2011, ISBN 0-321-57351-X.
 *      http://algs4.cs.princeton.edu
 *
 *
 *  algs4.jar is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  algs4.jar is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with algs4.jar.  If not, see http://www.gnu.org/licenses.
 ******************************************************************************/

第三节 2-3查找树

完美树结构：一棵有N个节点的树，我们希望它的树高为 lgN ，这样可以保证所有查找都在 lgN 次比较内结束，但可惜在动态插入中保证树的完美平衡代价太高了。

二叉树中的节点可以称作2-结点：含有一个键和两个链接。现在我们引入3-结点：含有两个键和三个链接。每条链接都对应着其中保存的键所分割产生的一个区间。

2-3查找树能以较小的代价实现树的完美平衡。

一棵完美平衡的2-3查找树中的所有空链接到根结点的距离都应该是相同的。

3.1 查找

将二叉查找树的查找算法一般化我们就能够直接得到 2-3 树的查找算法。要判断一个键是否在树中，我们先将它和根结点中的键比较。如果它和其中任意一个相等，查找命中；否则我们就根据比较的结果找到指向相应区间的链接，并在其指向的子树中递归地继续查找。如果这是个空链接，查找未命中。具体查找过程如图 3.3.2 所示。

　

3.2 向2-结点中插入新键

要在2-3树中插入一个新结点，我们可以和二叉查找树一样先进行一次未命中的查找，然后把新结点挂在树的底部。但这样的话树无法保持完美平衡性。我们使用2-3树的主要原因就在于它能够在插入后继续保持平衡。如果未命中的查找结束于一个2-结点，事情就好办了：我们只要把这个2-结点替换为一个3-结点，将要插入的键保存在其中即可。如果未命中的查找结束于一个3-结点，事情就要麻烦一些。

3.3 向一棵只含有一个3-结点的树中插入新键

在考虑一般情况之前，先假设我们需要向一棵只含有一个3-结点的树中插入一个新键。这棵树中有两个键，所以在它唯一的结点中已经没有可插入新键的空间了。为了将新键插入，我们先临时将新键存入该结点中，使之成为一个4-结点。它很自然地扩展了以前的结点并含有3个键和4条链接。创建一个4-结点很方便，因为很容易将它转换为一棵由3个2-结点组成的2-3树，其中一个结点（根）含有中键，一个结点含有3个键中的最小者（和根结点的左链接相连），一个结点含有3个键中的最大者（和根结点的右链接相连）。这棵树既是一棵含有3个结点的二叉查找树，同时也是一棵完美平衡的2-3树，因为其中所有的空链接到根结点的距离都相等。插入前树的高度为0，插入后树的高度为1。

3.4 向一个父结点为2-结点的3-结点中插入新键

作为第二轮热身，假设未命中的查找结束于一个3-结点，而它的父结点是一个2-结点。在这种情况下我们需要在维持树的完美平衡的前提下为新键腾出空间。我们先像刚才一样构造一个临时的4-结点并将其分解，但此时我们不会为中键创建一个新结点，而是将其移动至原来的父结点中。你可以将这次转换看成将指向原3-结点的一条链接替换为新父结点中的原中键左右两边的两条链接，并分别指向两个新的2-结点。根据我们的假设，父结点中是有空间的：父结点是一个2-结点（一个键两条链接），插入之后变为了一个3-结点（两个键3条链接）。另外，这次转换也并不影响（完美平衡的）2-3树的主要性质。树仍然是有序的，因为中键被移动到父结点中去了；树仍然是完美平衡的，插入后所有的空链接到根结点的距离仍然相同。请确认你完全理解了这次转换——它是2-3 树的动态变化的核心，其过程如图 3.3.5 所示。

3.5 向一个父结点为3-结点的3-结点中插入新键

现在假设未命中的查找结束于一个父结点为3-结点的结点。我们再次和刚才一样构造一个临时的4-结点并分解它，然后将它的中键插入它的父结点中。但父结点也是一个3-结点，因此我们再用这个中键构造一个新的临时4-结点，然后在这个结点上进行相同的变换，即分解这个父结点并将它的中键插入到它的父结点中去。推广到一般情况，我们就这样一直向上不断分解临时的4-结点并将中键插入更高层的父结点，直至遇到一个2-结点并将它替换为一个不需要继续分解的3-结点，或者是到达3-结点的根。该过程如图 3.3.6 所示。

3.6 分解根结点

如果从插入结点到根结点的路径上全都是3-结点，我们的根结点最终变成一个临时的4-结点。此时我们可以按照向一棵只有一个3-结点的树中插入新键的方法处理这个问题。我们将临时的4-结点分解为3个2-结点，使得树高加1，如图 3.3.7 所示。请注意，这次最后的变换仍然保持了树的完美平衡性，因为它变换的是根结点。

3.7 局部变换

将一个4-结点分解为一棵2-3树可能有6种情况，都总结在了图 3.3.8 中。这个4-结点可能是根结点，可能是一个2-结点的左子结点或者右子结点，也可能是一个3-结点的左子结点、中子结点或者右子结点。23树插入算法的根本在于这些变换都是局部的：除了相关的结点和链接之外不必修改或者检查树的其他部分。每次变换中，变更的链接数量不会超过一个很小的常数。需要特别指出的是，不光是在树的底部，树中的任何地方只要符合相应的模式，变换都可以进行。每个变换都会将4结点中的一个键送入它的父结点中，并重构相应的链接而不必涉及树的其他部分。

3.8 全局性质

这些局部变换不会影响树的全局有序性和平衡性：任意空链接到根结点的路径长度都是相等的。作为参考，图 3.3.9 所示的是当一个4-结点是一个 3-结点的中子结点时的完整变换情况。如果在变换之前根结点到所有空链接的路径长度为h，那么变换之后该长度仍然为h。所有的变换都具有这个性质，即使是将一个4-结点分解为两个2-结点并将其父结点由2-结点变为3-结点，或是由3-结点变为一个临时的4-结点时也是如此。当根结点被分解为3个2-结点时，所有空链接到根结点的路径长度才会加1。

和标准的二叉查找树由上向下生长不同，2-3树的生长是由下向上的。 如果你花点时间仔细研究一下图 3.3.10，就能很好地理解2-3树的构造方式。它给出了我们的标准索引测试用例中产生的一系列2-3树，以及一系列由同一组键按照升序依次插入到树中时所产生的所有2-3树。还记得在二叉查找树中，按照升序插入10 个键会得到高度为9的一棵最差查找树吗？如果使用2-3树，树的高度是2。

3.9 性能分析

2-3树的分析和二叉查找树的分析大不相同，因为我们主要感兴趣的是最坏情况下的性能，而非一般情况（这种情况下我们会用随机键模型分析预期的性能）。在符号表的实现中，一般我们无法控制用例会按照什么顺序向表中插入键，因此对最坏情况的分析是唯一能够提供性能保证的办法。

• 命题 F：在一棵大小为的2-3树中，查找和插入操作访问的结点必然不超过 lgN 个。
• 证明：一棵含有N个结点的2-3树的高度在 log3(N)=[lgN / lg3]（如果树中全是3-结点）和 [lgN]（如果树中全是2-结点）之间。

因此我们可以确定2-3树在最坏情况下仍有较好的性能。每个操作中处理每个结点的时间都不会超过一个很小的常数，且这两个操作都只会访问一条路径上的结点，所以任何查找或者插入的成本都肯定不会超过对数级别。通过对比图 3.3.11 中的2-3树和图 3.2.8 中由相同的键构造的二叉查找树，你也可以看到，完美平衡的 2-3树要平展得多。例如，含有 10 亿个结点的一棵2-3树的高度仅在19到30之间。我们最多只需访问30个结点就能够在10亿个键中进行任意查找和插入操作，这是相当惊人的。

但是，我们和真正的实现还有一段距离。尽管我们可以用不同的数据类型表示2-结点和3-结点并写出变换所需的代码，但用这种直白的表示方法实现大多数的操作并不方便，因为需要处理的情况实在太多。我们需要维护两种不同类型的结点，将被查找的键和结点中的每个键进行比较，将链接和其他信息从一种结点复制到另一种结点，将结点从一种数据类型转换到另一种数据类型，等等。实现这些不仅需要大量的代码，而且它们所产生的额外开销可能会使算法比标准的二叉查找树更慢。平衡一棵树的初衷是为了消除最坏情况，但我们希望这种保障所需的代码能够越少越好。幸运的是你将看到，我们只需要一点点代价就能用一种统一的方式完成所有变换。

---

第四节 红黑查找树

4.1 替换3-结点

红黑二叉查找树背后的基本思想是用标准的二叉查找树（完全由2-结点构成）和一些额外的信息（替换3-结点）来表示2-3树。我们将树中的链接分为两种类型：红链接将两个2-结点连接起来构成一个3-结点，黑链接则是2-3树中的普通链接。确切地说，我们将3-结点表示为由一条左斜的红色链接相连的两个2-结点，如图 3.3.12 所示。这种表示法的一个优点是，我们无需修改就可以直接使用标准二叉查找树的 get() 方法。对于任意的2-3树，只要对结点进行转换，我们都可以立即派生出一棵对应的二叉查找树。我们将用这种方式表示2-3树的二叉查找树称为红黑二叉查找树（以下简称为红黑树）。

红黑树实现2-3查找树的原因：

• 无需修改就可以直接使用标准二叉查找树的 get() 方法。
• 只要对结点进行转换，我们都可以立即派生出一棵对应的二叉查找树。

4.2 一种等价的定义

红黑树的另一种定义是含有红黑链接并满足下列条件的二叉查找树：

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

满足这样定义的红黑树和相应的 2-3 树是一一对应的。

4.3 一一对应

如果我们将一棵红黑树中的红链接画平，那么所有的空链接到根结点的距离都将是相同的（如图 3.3.13 所示）。如果我们将由红链接相连的结点合并，得到的就是一棵2-3树。相反，如果将一棵2-3树中的3-结点画作由红色左链接相连的两个2-结点，那么不会存在能够和两条红链接相连的结点，且树必然是完美黑色平衡的，因为黑链接即2-3树中的普通链接，根据定义这些链接必然是完美平衡的。无论我们选择用何种方式去定义它们，红黑树都既是二叉查找树，也是2-3树，如图 3.3.14 所示。因此，如果我们能够在保持一一对应关系的基础上实现2-3树的插入算法，那么我们就能够将两个算法的优点结合起来：二叉查找树中简洁高效的查找方法和2-3树中高效的平衡插入算法。

4.4 颜色表示

方便起见，因为每个结点都只会有一条指向自己的链接（从它的父结点指向它），我们将链接的颜色保存在表示结点的Node数据类型的布尔变量 color 中。如果指向它的链接是红色的，那么该变量为true，黑色则为false。我们约定空链接为黑色。为了代码的清晰我们定义了两个常量 RED 和 BLACK 来设置和测试这个变量。我们使用私有方法 isRed() 来测试一个结点和它的父结点之间的链接的颜色。颜色表示的代码实现如图 3.3.15 所示。

4.5 旋转

在我们实现的某些操作中可能会出现红色右链接或者两条连续的红链接，但在操作完成前这些情况都会被小心地旋转并修复。旋转操作会改变红链接的指向。首先，假设我们有一条红色的右链接需要被转化为左链接（请见图3.3.16）。这个操作叫做左旋转，它对应的方法接受一条指向红黑树中的某个结点的链接作为参数。假设被指向的结点的右链接是红色的，这个方法会对树进行必要的调整并返回一个指向包含同一组键的子树且其左链接为红色的根结点的链接。我们只是将用两个键中的较小者作为根结点变为将较大者作为根结点。实现将一个红色左链接转换为一个红色右链接的一个右旋转的代码完全相同，只需要将 left 和 right 互换即可（如图 3.3.17 所示）。

如上图代码所示，实际只是将 E 的右链接指向 S 改为 SE间 （原S左链接指向内容），将 S 左链接改为指向 E ，修改颜色和子树节点计数N。返回旋转后根节点链接，后续父节点操作在此过程无需考虑，这只是旋转单个3-节点的流程。

同上。

4.6 在旋转后重置父结点的链接

无论左旋转还是右旋转，旋转操作都会返回一条链接。我们总是会用 rotateRight() 或 rotateLeft() 的返回值重置父结点（或是根结点）中相应的链接。返回的链接可能是左链接也可能是右链接，但是我们总会将它赋予父结点中的链接。这个链接可能是红色也可能是黑色—— rotateLeft() 和 rotateRight() 都通过将 x.color 设为 h.color 保留它原来的颜色。这可能会产生两条连续的红链接，但我们的算法会继续用旋转操作修正这种情况。例如，代码 h = rotateLeft(h); 将旋转结点h的红色右链接，使得h指向了旋转后的子树的根结点（组成该子树中的所有键和旋转前相同，只是根结点发生了变化）。这种简洁的代码是我们使用递归实现二叉查找树的各种方法的主要原因。你会看到，它使得旋转操作成为了普通插入操作的一个简单补充。

在插入新的键时我们可以使用旋转操作帮助我们保证2-3树和红黑树之间的一一对应关系，因为旋转操作可以保持红黑树的两个重要性质：有序性和完美平衡性。也就是说，我们在红黑树中进行旋转时无需为树的有序性或者完美平衡性担心。下面我们来看看应该如何使用旋转操作来保持红黑树的另外两个重要性质：不存在两条连续的红链接和不存在红色的右链接。我们先用一些简单的情况热热身。

4.7 向单个2-结点中插入新键

一棵只含有一个键的红黑树只含有一个2-结点。插入另一个键之后，我们马上就需要将它们旋转。如果新键小于老键，我们只需要新增一个红色的结点即可，新的红黑树和单个3-结点完全等价。如果新键大于老键，那么新增的红色结点将会产生一条红色的右链接。我们需要使用 root = rotateLeft(root); 来将其旋转为红色左链接并修正根结点的链接，插入操作才算完成。两种情况的结果均为一棵和单个3- 结点等价的红黑树，其中含有两个键，一条红链接，树的黑链接高度为1， 如图 3.3.18 所示。

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

用和二叉查找树相同的方式向一棵红黑树中插入一个新键会在树的底部新增一个结点（为了保证有序性），但总是用红链接将新结点和它的父结点相连。如果它的父结点是一个2-结点，那么刚才讨论的两种处理方法仍然适用。如果指向新结点的是父结点的左链接，那么父结点就直接成为了一个3-结点；如果指向新结点的是父结点的右链接，这就是一个错误的3-结点，但一次左旋转就能够修正它，如图 3.3.19 所示。

4.9 向一棵双键树（即一个3-结点）中插入新键

这种情况又可分为三种子情况：新键小于树中的两个键，在两者之间，或是大于树中的两个键。每种情况中都会产生一个同时连接到两条红链接的结点，而我们的目标就是修正这一点。

• 三者中最简单的情况是新键大于原树中的两个键，因此它被连接到3-结点的右链接。此时树是平衡的，根结点为中间大小的键，它有两条红链接分别和较小和较大的结点相连。如果我们将两条链接的颜色都由红变黑，那么我们就得到了一棵由三个结点组成、高为2的平衡树。它正好能够对应一棵2-3树，如图 3.3.20（左）。其他两种情况最终也会转化为这种情况。
• 如果新键小于原树中的两个键，它会被连接到最左边的空链接，这样就产生了两条连续的红链接，如图 3.3.20（中）。此时我们只需要将上层的红链接右旋转即可得到第一种情况（中值键为根结点并和其他两个结点用红链接相连），再将两条链接的颜色都由红变黑。
• 如果新键介于原树中的两个键之间，这又会产生两条连续的红链接，一条红色左链接接一条红色右链接，如图 3.3.20（右）。此时我们只需要将下层的红链接左旋转即可得到第二种情况（两条连续的红色左链接），再将上层的红链接右旋转，再将两条链接的颜色都由红变黑。

总的来说，我们通过 0 次、1 次和 2 次旋转以及颜色的变化得到了期望的结果。在 2-3 树中，请确认你完全理解了这些转换，它们是红黑树的动态变化的关键。

4.10 颜色转换分解4-结点

如图 3.3.21 所示，我们专门用一个方法 flipColors() 来转换一个结点的两个红色子结点的颜色。除了将子结点的颜色由红变黑之外，我们同时还要将父结点的颜色由黑变红。这项操作最重要的性质在于它和旋转操作一样是局部变换，不会影响整棵树的黑色平衡性。根据这一点，我们马上能够在下面完整地实现红黑树。

注意颜色转换会使“根结点”变成红结点。

4.11 根结点总是黑色

在 3.3.2.9 所述的情况中，颜色转换会使根结点变为红色。这也可能出现在很大的红黑树中。严格地说，红色的根结点说明根结点是一个3结点的一部分，但实际情况并不是这样。因此我们在每次插入后都会将根结点设为黑色。注意，每当根结点由红变黑时树的黑链接高度就会加1。

4.12 向树底部的3-结点插入新键

现在假设我们需要在树的底部的一个3-结点下加入一个新结点。前面讨论过的三种情况都会出现，如图 3.3.22 所示。

• 指向新结点的链接可能是3-结点的右链接，此时我们只需要转换颜色即可；
• 或是左链接，此时我们需要进行右旋转然后再转换颜色；
• 或是中链接，此时我们需要先左旋转下层链接然后右旋转上层链接，最后再转换颜色。

颜色转换会使到中结点的链接变红，相当于将它送入了父结点。这意味着在父结点中继续插入一个新键，我们也会继续用相同的办法解决这个问题。

4.13 将红链接在树中向上传递

2-3 树中的插入算法需要我们分解 3-结点，将中间键插入父结点，如此这般直到遇到一个2-结点或是根结点。我们所考虑过的所有情况都正是为了达成这个目标：每次必要的旋转之后我们都会进行颜色转换，这使得中结点变红。

在父结点看来，处理这样一个红色结点的方式和处理一个新插入的红色结点完全相同，即继续把红链接转移到中结点上去。图 3.3.23 中总结的三种情况显示了在红黑树中实现2-3树的插入算法的关键操作所需的步骤：要在一个3-结点下插入新键，先创建一个临时的4-结点，将其分解并将红链接由中间键传递给它的父结点。重复这个过程，我们就能将红链接在树中向上传递，直至遇到一个2-结点或者根结点。

总之，只要谨慎地使用左旋转、右旋转和颜色转换这三种简单的操作，我们就能够保证插入操作后红黑树和2-3树的一一对应关系。在沿着插入点到根结点的路径向上移动时在所经过的每个结点中顺序完成以下操作，我们就能完成插入操作：

• 如果右子结点是红色的而左子结点是黑色的，进行左旋转；

• 如果左子结点是红色的且它的左子结点也是红色的，进行右旋转；

• 如果左右子结点均为红色，进行颜色转换。

你应该花点时间确认以上步骤处理了前文描述的所有情况。请注意，第一个操作表示将一个2-结点变为一个3-结点和插入的新结点与树底部的3-结点通过它的中链接相连的两种情况。

---

第五节 实现

因为保持树的平衡性所需的操作是由下向上在每个所经过的结点中进行的，将它们植入我们已有的实现中十分简单：只需要在递归调用之后完成这些操作即可，如算法 3.4 所示。上一段中列出的三种操作都可以通过一个检测两个结点的颜色的if语句完成。尽管实现所需的代码量很小，但如果没有我们学习过的两种抽象数据结构（2-3 树和红黑树）作为铺垫，这段实现仍然会非常难以理解。在检查了三到五个结点的颜色之后（也许还需要进行一两次旋转以及颜色转换），我们就可以得到一棵近乎完美平衡的二叉查找树。

public class RedBlackBST<Key extends Comparable<Key>, Value> {
    private Node root;
   
    private class Node // 含有color变量的Node对象（请见3.3.2.4节）

    private boolean isRed(Node h)    // 请见3.3.2.4节   
    private Node rotateLeft(Node h)  // 请见图3.3.16   
    private Node rotateRight(Node h) // 请见图3.3.17   
    private void flipColors(Node h)  // 请见图3.3.21

    private int size()               // 请见算法3.3

    public void put(Key key, Value val){  
       // 查找key，找到则更新其值，否则为它新建一个结点      
       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, 1, RED);

        //比较新键和父结点大小
        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;//相等，直接替换value
        
        //判断当前区域红黑树状态
        //根据红黑树插入操作的三种情况调用对应基本API
        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.N = size(h.left) + size(h.right) + 1;      
        return h;  
    } 
}

除了递归调用后的三条 if 语句，红黑树中 put() 的递归实现和二叉查找树中 put() 的实现完全相同。它们在查找路径上保证了红黑树和2-3树的一一对应关系，使得树的平衡性接近完美。第一条 if 语句会将任意含有红色右链接的3-结点（或临时的4-结点）向左旋转；第二条 if 语句会将临时的4-结点中两条连续红链接中的上层链接向右旋转；第三条 if 语句会进行颜色转换并将红链接在树中向上传递（详情请见正文）。

图 3.3.24 给出了使用我们的标准索引测试用例进行测试的轨迹和用同一组键按照升序构造一棵红黑树的测试轨迹。仅从红黑树的三种标准操作的角度分析这些例子对我们理解问题很有帮助，之前我们也是这样做的。另一个基本练习是检查它们和2-3树的一一对应关系（可以对比图 3.3.10 中由同一组键构造的2-3树）。在两种情况中你都能通过思考将 P 插入红黑树所需的转换来检验你对算法的理解程度（请见练习 3.3.12）。

---

第六节 删除操作

算法3.4中的 put() 方法是本书中最复杂的实现之一，而红黑树的 deleteMin() 、deleteMax() 和 delete() 的实现更麻烦，我们将它们的完整实现留做练习，但这里仍然需要学习它们的基本原理。要描述删除算法，首先我们要回到2-3树。和插入操作一样，我们也可以定义一系列局部变换来在删除一个结点的同时保持树的完美平衡性。这个过程比插入一个结点更加复杂，因为我们不仅要在为了删除一个结点而构造临时4-结点时沿着查找路径向下进行变换，还要在分解遗留的4-结点时沿着查找路径向上进行变换（同插入操作）。

6.1 自顶向下的2-3-4树

作为第一轮热身，我们先学习一个沿查找路径既能向上也能向下进行变换的稍简单的算法：2-3-4树的插入算法。

2-3-4树中允许存在我们以前见过的4-结点。它的插入算法沿查找路径向下进行变换是为了保证当前结点不是4-结点（这样树底才有空间来插入新的键），沿查找路径向上进行变换是为了将之前创建的4-结点配平，如图 3.3.25 所示。向下的变换和我们在2-3树中分解4-结点所进行的变换完全相同。

• 如果根结点是4-结点，我们就将它分解成三个2-结点，使得树高加1。
• 在向下查找的过程中，如果遇到一个父结点为2-结点的4-结点，我们将4-结点分解为两个2-结点并将中间键传递给它的父结点，使得父结点变为一个3-结点；
• 如果遇到一个父结点为3-结点的4-结点，我们将4-结点分解为两个2-结点并将中间键传递给它的父结点，使得父结点变为一个4-结点；

我们不必担心会遇到父结点为4-结点的4-结点，因为插入算法本身就保证了这种情况不会出现。到达树的底部之后，我们也只会遇到2-结点或者3-结点，所以我们可以插入新的键。

要用红黑树实现这个算法，我们需要：

• 将4-结点表示为由三个2-结点组成的一棵平衡的子树，根结点和两个子结点都用红链接相连；
• 在向下的过程中分解所有4-结点并进行颜色转换；
• 和插入操作一样，在向上的过程中用旋转将4-结点配平 。

因为4-结点可以存在，所以可以允许一个结点同时连接到两条链接。——译者注

令人惊讶的是，你只需要移动算法3.4的 put() 方法中的一行代码就能实现2-3-4树中的插入操作：将 colorFlip() 语句（及其 if 语句）移动到递归调用之前（null 测试和比较操作之间）。在多个进程可以同时访问同一棵树的应用中这个算法优于2-3树，因为它操作的总是当前结点的一个或两个链接。我们下面要讲的删除算法和它的插入算法类似，而且也适用于2-3树。

6.2 删除最小键

在第二轮热身中我们要学习2-3树中删除最小键的操作。我们注意到从 树底部的3-结点中删除键是很简单的，但2-结点则不然。从2-结点中删除一个键会留下一个空结点，一般我们会将它替换为一个空链接，但这样会破坏树的完美平衡性。所以我们需要这样做：为了保证我们不会 删除一个2-结点，我们沿着左链接向下进行变换，确保当前结点不是2-结点（可能是3-结点，也可能是临时的4-结点）。首先，根结点可 能有两种情况。如果根是2-结点且它的两个子结点都是2-结点，我们可以直接将这三个结点变成一个4-结点；否则我们需要保证根结点的左子结点不是2-结点，如有必要可以从它右侧的兄弟结点“借”一个键 来。以上情况如图 3.3.26 所示。在沿着左链接向下的过程中，保证以下情况之一成立：

• 如果当前结点的左子结点不是2-结点，完成；
• 如果当前结点的左子结点是2-结点而它的亲兄弟结点不是2-结点，将左子结点的兄弟结点中的一个键移动到左子结点中；
• 如果当前结点的左子结点和它的亲兄弟结点都是2-结点，将左子结点、父结点中的最小键和左子结点最近的兄弟结点合并为一个 4结点，使父结点由3-结点变为2-结点或者由4-结点变为3-结点。

在遍历的过程中执行这个过程，最后能够得到一个含有最小键的3-结点或者4-结点，然后我们就可以直接从中将其删除，将3-结点变为2结点，或者将4-结点变为3-结点。然后我们再回头向上分解所有临时的4-结点。

6.3 删除操作

在查找路径上进行和删除最小键相同的变换同样可以保证在查找过程中任意当前结点均不是2-结点。如果被查找的键在树的底部，我们可以直接删除它。如果不在，我们需要将它和它的后继结点交换，就和二叉查找树一样。因为当前结点必然不是 2-结点，问题已经转化为在一棵根结点不是2-结点的子树中删除最小的键，我们可以在这棵子树中使用前文所述的算法。和以前一样，删除之后我们需要向上回溯并分解余下的4-结点。

本节末尾的练习中有几道是关于这些删除算法的例子和实现的。有兴趣理解或实现删除算法的读者应该掌握这些练习中的细节。对算法研究感兴趣的读者应该认识到这些方法的重要性，因为这是我们见过的第一种能够同时实现高效的查找、插入和删除操作的符号表实现。下面我们将会验证这一点。

---

第七节 红黑树的性质

研究红黑树的性质就是要检查对应的2-3树并对相应的2-3树进行分析的过程。我们的最终结论是所有基于红黑树的符号表实现都能保证操作的运行时间为对数级别（范围查找除外，它所需的额外时间和返回的键的数量成正比）。我们重复并强调这一点是因为它十分重要。

7.1 性能分析

首先，无论键的插入顺序如何，红黑树都几乎是完美平衡的（请见图 3.3.27）。这从它和2-3树的一一对应关系以及 2-3 树的重要性质可以得到。

命题 G。一棵大小为N的红黑树的高度不会超过2lgN。

简略的证明。红黑树的最坏情况是它所对应的 2-3 树中构成最左边 的路径结点全部都是 3- 结点而其余均为 2- 结点。最左边的路径长 度是只包含 2- 结点的路径长度（~lgN）的两倍。要按照某种顺序 构造一棵平均路径长度为2lgN的最差红黑树虽然可能，但并不容 易。如果你喜欢数学，你也许会喜欢在练习 3.3.24 中探究这个问题 的答案。

这个上界是比较保守的。使用随机的键序列和典型应用中常见的键序列 进行的实验都证明，在一棵大小为N的红黑树中一次查找所需的比较 次数约为（1.00lgN - 0.5）。另外，在实际情况下你不太可能遇到比这个数字高得多的平均比较次数，如表 3.3.1 所示。

命题H。一棵大小为N的红黑树中，根结点到任意结点的平均路径长度为~1.00lgN。

例证。和典型的二叉查找树（例如图 3.2.8 中所示的树）相比，一棵典型的红黑树的平衡性是很好的，例如图 3.3.27 所示（甚至是图 3.3.28 中由升序键列构造的红黑树）。表 3.3.1 显示的数据表明FrequencyCounter在运行中构造的红黑树的路径长度（即查找成本）比初等二叉查找树低40%左右，和预期相符。自红黑树的发明以来，无数的实验和实际应用都印证了这种性能改进。

以使用 FrequencyCounter 在处理长度大于等于8的单词时put()操作的成本为例，我们可以看到平均成本降低得更多（如图 3.3.29 所示）。这又一次验证了理论模型所预测的对数级别的运行时间，只不过这次的惊喜比二叉查找树的小，因为性质G已经向我们保证了这一点。节约的总成本低于在查找上节约的40%的成本，因为除了比较我们也统计了旋转和颜色变换的次数。

红黑树的get()方法不会检查结点的颜色，因此平衡性相关的操作不会产生任何负担；因为树是平衡的，所以查找比二叉查找树更快。每个键只会被插入一次，但却可能被查找无数次，因此最后我们只用了很小的代价（和二分查找不同，我们可以保证插入操作是对数级别的）就取得了和最优情况近似的查找时间（因为树是接近完美平衡的，且查找过程中不会进行任何平衡性的操作）。查找的内循环只会进行一次比较并更新一条链接，非常简短，和二分查找的内循环类似（只有比较和索引运算）。这是我们见到的第一个能够保证对数级别的查找和插入操作的实现，它的内循环更紧凑。它通过了各种应用的考验，包括许多库实现。

7.2 有序符号表API

红黑树最吸引人的一点是它的实现中最复杂的代码仅限于 put()（和删除）方法。二叉查找树中的查找最大和最小 键、select()、rank()、floor()、ceiling() 和范围查找方法不做任何变动即可继续使用，因为红黑树也是二叉查找树而这些操作也不会涉及结点的颜色。算法 3.4 和这些方法（以及删除方法）一起完整地实现了我们的有序符号表 API。这些方法都能从红黑树近乎完美的平衡性中受益，因为它们最多所需的时间都和树高成正比。因此命题G和命题E一起保证了所有操作的运行时间是对数级别的。

命题I。在一棵红黑树中，以下操作在最坏情况下所需的时间是对数级别的：查找（get()）、插入（put()）、查找最小键、查找最大键、floor()、ceiling()、rank()、select()、删除最小键（deleteMin()）、删除最大键（deleteMax()）、删除（delete()）和范围查询（range()）。

证明。我们已经讨论过 put()、get() 和 delete() 方法。对于其他方法，代码可以从3.2节中照搬（它们不涉及结点颜色）。命题G和命题E可以保证算法是对数级别的，所有操作在所经过的结点上只会进行常数次数的操作也说明了这一点。

各种符号表实现的性能总结如表 3.3.2 所示。

想想看，这样的保证是一个非凡的成就。在信息世界的汪洋大海中，表的大小可能上千亿，但我们仍能够确保在几十次比较之内就完成这些操作。

7.3 答疑

• 问：为什么不允许存在红色右链接和4-结点？
• 答：它们都是可用的，并且已经应用了几十年了。在练习中你会遇到它们。只允许红色左链接的存在能够减少可能出现的情况，因此实现所需的代码会少得多。

• 问：为什么不在Node类型中使用一个Key类型的数组来表示2-结点、 3-结点和4-结点？
• 答：问得好。这正是我们在B-树（请见第６章）的实现中使用的方案，它的每个结点中可以保存更多的键。因为2-3树中的结点较少，数组所带来的额外开销太高了。

• 问：在分解一个4-结点时，我们有时会在 rotateRight() 中将右结点的颜色设为RED（红）然后立即在 flipColors() 中将它的颜色变为BLACK（黑）。这不是浪费时间吗？
• 答：是的，有时我们还会不必要地反复改变中结点的颜色。从整体来看，多余的几次颜色变换和将所有方法的运行时间的增长数量级从线性级别提升到对数级别不是一个级别的。当然，在有性能要求的应用中，你可以将 rotateRight() 和 flipColors() 的代码在所需要的地方展开来消除那些额外的开销。我们在删除中也会使用这两个方法。在能够保证树的完美平衡的前提下，它们更加容易使用、理解和维护。

---

第八节 补充

8.1 红黑树和AVL树的区别

红黑树本质是2-3树，属于平衡二叉树，其2-结点等价于普通二叉树结点，3-结点本质是非平衡性的缓存。红黑树本质是用空间换时间，通过牺牲平衡性减少了插入/删除时的旋转次数，所以查询会略慢于AVL树，但综合各种情况来看性能会略优于AVL树。

红黑树非严格平衡二叉树，因为其用红黑链+二叉树来实现3-结点的设计，导致无法严格控制所有空链接到根结点距离相等。

AVL树即平衡二叉查找树，要求是一个空树或左右子树高度差不能超过1，子树仍是平衡二叉树。AVL是其中一种平衡二叉树实现

AVL树查询效率会略高于红黑树。

AVL树被应用于Windows进程地址空间管理。

综合：

• 红黑树综合性能略高，AVL查询速度略快。

---

参考博客和文章书籍等：

《算法 第4版》

平衡树-维基百科

因博客主等未标明不可引用，若部分内容涉及侵权请及时告知，我会尽快修改和删除相关内容