Java红黑树的数据结构与算法解析

红黑树简介

红黑树是一种平衡二叉搜索树，其中的每个节点上都有一个黑色或红色的标记，并且满足以下性质：

1. 根节点是黑色的；
2. 叶子节点是黑色的空节点（NULL）；
3. 如果一个节点是红色的，则其子节点必须是黑色的；
4. 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点；
5. 新插入的节点默认是红色的。

具体来说，只有在删除或者某些特殊的插入操作之后，才会涉及到红黑树的平衡调整。

红黑树可以用于实现有序的映射表数据结构。Java 中的 TreeMap 就是基于红黑树实现的。

红黑树的基本操作

红黑树支持的操作包括：

• add(e): 插入元素 e；
• remove(e): 删除元素 e；
• find(e): 查找元素 e；
• floor(e): 返回小于等于 e 的最大元素；
• ceiling(e): 返回大于等于 e 的最小元素；
• lower(e): 返回小于 e 的最大元素；
• higher(e): 返回大于 e 的最小元素；
• first(): 返回树中最小元素；
• last(): 返回树中最大元素。

这些操作都可以在 $O(\log(n))$ 的时间内完成。

红黑树实现示例

以下是基于 Java 实现的红黑树示例代码：

public class RedBlackTree<K extends Comparable<K>, V> {
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private class Node {
        public K key;
        public V value;
        public Node left, right;
        public boolean color;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            left = null;
            right = null;
            color = RED;
        }
    }

    private Node root;
    private int size;

    public RedBlackTree() {
        root = null;
        size = 0;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    private boolean isRed(Node node) {
        if (node == null)
            return BLACK;
        return node.color;
    }

    private Node leftRotate(Node node) {
        Node x = node.right;
        node.right = x.left;
        x.left = node;

        x.color = node.color;
        node.color = RED;

        return x;
    }

    private Node rightRotate(Node node) {
        Node x = node.left;
        node.left = x.right;
        x.right = node;

        x.color = node.color;
        node.color = RED;

        return x;
    }

    private void flipColors(Node node) {
        node.color = RED;
        node.left.color = BLACK;
        node.right.color = BLACK;
    }

    public void add(K key, V value) {
        root = add(root, key, value);
        root.color = BLACK;
    }

    private Node add(Node node, K key, V value) {
        if (node == null) {
            size++;
            return new Node(key, value);
        }

        if (key.compareTo(node.key) < 0)
            node.left = add(node.left, key, value);
        else if (key.compareTo(node.key) > 0)
            node.right = add(node.right, key, value);
        else
            node.value = value;

        if (isRed(node.right) && !isRed(node.left))
            node = leftRotate(node);

        if (isRed(node.left) && isRed(node.left.left))
            node = rightRotate(node);

        if (isRed(node.left) && isRed(node.right))
            flipColors(node);

        return node;
    }

    private Node getNode(Node node, K key) {
        if (node == null)
            return null;

        if (key.equals(node.key))
            return node;
        else if (key.compareTo(node.key) < 0)
            return getNode(node.left, key);
        else
            return getNode(node.right, key);
    }

    public boolean contains(K key) {
        return getNode(root, key) != null;
    }

    public V get(K key) {
        Node node = getNode(root, key);
        return node == null ? null : node.value;
    }

    public void set(K key, V newValue) {
        Node node = getNode(root, key);
        if (node == null)
            throw new IllegalArgumentException(key + " doesn't exist in the BST.");

        node.value = newValue;
    }

    public Node minimum(Node node) {
        if (node.left == null)
            return node;
        return minimum(node.left);
    }

    public V remove(K key) {
        Node node = getNode(root, key);
        if (node != null) {
            root = remove(root, key);
            return node.value;
        }
        return null;
    }

    private Node remove(Node node, K key) {
        if (node == null)
            return null;

        if (key.compareTo(node.key) < 0) {
            node.left = remove(node.left, key);
            return node;
        } else if (key.compareTo(node.key) > 0) {
            node.right = remove(node.right, key);
            return node;
        } else {
            //key.compareTo(node.key) == 0
            if (node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }

            if (node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }

            Node successor = minimum(node.right);
            successor.right = remove(node.right, successor.key);
            successor.left = node.left;

            node.left = node.right = null;

            return successor;
        }
    }
}

红黑树应用示例

以下是一个使用红黑树实现有序集合的示例代码：

public class TreeSet<E extends Comparable<E>> implements Set<E> {
    private RedBlackTree<E, Object> tree;

    public TreeSet() {
        tree = new RedBlackTree<>();
    }

    public int size() {
        return tree.getSize();
    }

    public boolean isEmpty() {
        return tree.isEmpty();
    }

    public boolean contains(Object o) {
        return tree.contains((E)o);
    }

    public boolean add(E e) {
        Object obj = tree.add(e, null);
        return obj == null;
    }

    public boolean remove(Object o) {
        Object obj = tree.remove((E)o);
        return obj != null;
    }

    public void clear() {
        tree = new RedBlackTree<>();
    }

    public Iterator<E> iterator() {
        return new TreeSetIterator(tree);
    }

    private class TreeSetIterator implements Iterator<E> {
        private Iterator<RedBlackTree.Node> iterator;

        public TreeSetIterator(RedBlackTree<E, Object> tree) {
            iterator = new RedBlackTreeIterator(tree);
        }

        public boolean hasNext() {
            return iterator.hasNext();
        }

        public E next() {
            RedBlackTree.Node node = iterator.next();
            return (E)node.key;
        }

        public void remove() {
            iterator.remove();
        }
    }

    private class RedBlackTreeIterator implements Iterator<RedBlackTree.Node> {
        private Stack<RedBlackTree.Node> stack;

        public RedBlackTreeIterator(RedBlackTree<E, Object> tree) {
            stack = new Stack<>();

            RedBlackTree.Node cur = tree.getRoot();
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
        }

        public boolean hasNext() {
            return !stack.isEmpty();
        }

        public RedBlackTree.Node next() {
            RedBlackTree.Node cur = stack.pop();

            if (cur.right != null) {
                RedBlackTree.Node right = cur.right;
                while (right != null) {
                    stack.push(right);
                    right = right.left;
                }
            }

            return cur;
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
}

该示例代码实现了一个基于红黑树实现的有序集合。其中，set 的基本操作都可以在 $O(\log(n))$ 的时间内完成。