Java TreeMap的红黑树结构解析

红黑树基础概念

红黑树（Red - Black Tree）是一种自平衡的二叉搜索树，它是在计算机科学中用于高效存储和检索数据的数据结构。Java的TreeMap就是基于红黑树实现的。红黑树具有以下几个关键的属性：

节点颜色：每个节点要么是红色，要么是黑色。这是红黑树区别于其他二叉搜索树的一个重要特征，节点颜色用于维持树的平衡性质。
根节点：根节点是黑色的。这一规则确保了树的整体结构的稳定性，因为根节点作为整个树的起始点，如果根节点是红色，可能会在插入或删除操作时破坏树的平衡。
叶子节点：所有叶子节点（NIL节点，在实际实现中通常用null表示）都是黑色的。这些叶子节点不存储实际数据，它们的存在只是为了简化树的操作和维持树的平衡。
红色节点的子节点：如果一个节点是红色的，那么它的两个子节点必须是黑色的。这一规则防止了连续红色节点的出现，避免了树向一侧过度倾斜，从而保证了树的大致平衡。
黑色节点高度：从任意节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。这个属性保证了树的高度在一定范围内，从而保证了搜索、插入和删除操作的时间复杂度。

这些属性共同保证了红黑树在最坏情况下，其高度也不会超过2 * log(n + 1)，其中n是树中节点的数量。这使得红黑树在搜索、插入和删除操作上都具有较好的时间复杂度，平均和最坏情况下的时间复杂度均为O(log n)。

Java TreeMap中的红黑树实现

关键类和成员变量

在Java的TreeMap中，红黑树的节点由内部类Entry表示。以下是Entry类的简化代码：

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;

    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }

    // 省略其他方法
}

在TreeMap类中，有几个关键的成员变量与红黑树相关：

private transient Entry<K,V> root = null;
private transient int size = 0;
private transient int modCount = 0;

root变量指向红黑树的根节点，size记录树中节点的数量，modCount用于记录集合结构的修改次数，用于实现快速失败机制（fail - fast），在迭代过程中如果集合结构发生改变，会抛出ConcurrentModificationException。

插入操作

当向TreeMap中插入一个新的键值对时，会调用put方法。put方法最终会调用putTreeVal方法来完成红黑树的插入操作。以下是putTreeVal方法的主要逻辑：

final TreeNode<K,V> putTreeVal(Comparator<? super K> c, K key, V value) {
    Class<?> kc = null;
    boolean searched = false;
    TreeNode<K,V> parent = null;
    TreeNode<K,V> x = root;
    while (x != null) {
        parent = x;
        int cmp;
        if ((cmp = (c == null)? ((Comparable<? super K>)key).compareTo(x.key) : c.compare(key, x.key)) < 0) {
            x = x.left;
        } else if (cmp > 0) {
            x = x.right;
        } else {
            return x.setValue(value);
        }
    }
    TreeNode<K,V> node = new TreeNode<>(key, value, parent);
    if (parent == null) {
        root = node;
    } else if ((c == null)? ((Comparable<? super K>)key).compareTo(parent.key) < 0 : c.compare(key, parent.key) < 0) {
        parent.left = node;
    } else {
        parent.right = node;
    }
    fixAfterInsertion(node);
    size++;
    return null;
}

搜索插入位置：从根节点开始，通过比较新键与当前节点的键，决定向左子树还是右子树移动，直到找到合适的插入位置（即找到一个叶子节点）。
创建新节点并插入：在找到的插入位置创建一个新的Entry节点，并将其连接到树中。
修复红黑树属性：调用fixAfterInsertion方法来修复插入操作可能破坏的红黑树属性。

fixAfterInsertion方法是插入操作中修复红黑树平衡的关键。其主要逻辑如下：

private void fixAfterInsertion(Entry<K,V> x) {
    x.color = RED;
    while (x != null && x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            // 对称情况
        }
    }
    root.color = BLACK;
}

新节点颜色设置：新插入的节点初始设置为红色，因为这样对树的黑色高度影响最小。
循环调整：如果新节点的父节点是红色，且新节点不是根节点，就需要进行调整。
- 情况一：叔叔节点为红色：将父节点和叔叔节点都设置为黑色，祖父节点设置为红色，然后将当前节点上移到祖父节点，继续循环调整。
- 情况二：叔叔节点为黑色：如果新节点是父节点的右子节点，先对父节点进行左旋操作，然后将当前节点更新为父节点。接着将父节点设置为黑色，祖父节点设置为红色，并对祖父节点进行右旋操作。

旋转操作

旋转操作是红黑树维持平衡的重要手段，分为左旋和右旋。

左旋操作：

private void rotateLeft(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> r = p.right;
        p.right = r.left;
        if (r.left != null) {
            r.left.parent = p;
        }
        r.parent = p.parent;
        if (p.parent == null) {
            root = r;
        } else if (p.parent.left == p) {
            p.parent.left = r;
        } else {
            p.parent.right = r;
        }
        r.left = p;
        p.parent = r;
    }
}

左旋操作将一个节点的右子节点提升为该节点的父节点，并将原父节点变为右子节点的左子节点。这一操作适用于树向右倾斜过度的情况，通过左旋可以使树恢复平衡。

右旋操作：

private void rotateRight(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> l = p.left;
        p.left = l.right;
        if (l.right != null) {
            l.right.parent = p;
        }
        l.parent = p.parent;
        if (p.parent == null) {
            root = l;
        } else if (p.parent.right == p) {
            p.parent.right = l;
        } else {
            p.parent.left = l;
        }
        l.right = p;
        p.parent = l;
    }
}

右旋操作与左旋操作相反，将一个节点的左子节点提升为该节点的父节点，并将原父节点变为左子节点的右子节点。适用于树向左倾斜过度的情况。

删除操作

删除操作在TreeMap中相对复杂。当调用remove方法删除一个键值对时，最终会调用deleteEntry方法。

private void deleteEntry(Entry<K,V> p) {
    modCount++;
    size--;
    if (p.left != null && p.right != null) {
        Entry<K,V> s = successor(p);
        p.key = s.key;
        p.value = s.value;
        p = s;
    }
    Entry<K,V> replacement = (p.left != null? p.left : p.right);
    if (replacement != null) {
        replacement.parent = p.parent;
        if (p.parent == null) {
            root = replacement;
        } else if (p == p.parent.left) {
            p.parent.left = replacement;
        } else {
            p.parent.right = replacement;
        }
        p.left = p.right = p.parent = null;
        if (p.color == BLACK) {
            fixAfterDeletion(replacement);
        }
    } else if (p.parent == null) {
        root = null;
    } else {
        if (p.color == BLACK) {
            fixAfterDeletion(p);
        }
        if (p.parent != null) {
            if (p == p.parent.left) {
                p.parent.left = null;
            } else if (p == p.parent.right) {
                p.parent.right = null;
            }
            p.parent = null;
        }
    }
}

找到替代节点：如果要删除的节点有两个子节点，找到该节点的后继节点（即右子树中最小的节点），将后继节点的值复制到要删除的节点，然后将删除操作转换为删除后继节点。
连接替代节点：如果要删除的节点只有一个子节点或者没有子节点，将其唯一的子节点（或null）连接到其父节点的相应位置。
修复红黑树属性：如果删除的是黑色节点，可能会破坏红黑树的属性，调用fixAfterDeletion方法进行修复。

fixAfterDeletion方法的主要逻辑如下：

private void fixAfterDeletion(Entry<K,V> x) {
    while (x != root && colorOf(x) == BLACK) {
        if (x == leftOf(parentOf(x))) {
            Entry<K,V> w = rightOf(parentOf(x));
            if (colorOf(w) == RED) {
                setColor(w, BLACK);
                setColor(parentOf(x), RED);
                rotateLeft(parentOf(x));
                w = rightOf(parentOf(x));
            }
            if (colorOf(leftOf(w)) == BLACK && colorOf(rightOf(w)) == BLACK) {
                setColor(w, RED);
                x = parentOf(x);
            } else {
                if (colorOf(rightOf(w)) == BLACK) {
                    setColor(leftOf(w), BLACK);
                    setColor(w, RED);
                    rotateRight(w);
                    w = rightOf(parentOf(x));
                }
                setColor(w, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(rightOf(w), BLACK);
                rotateLeft(parentOf(x));
                x = root;
            }
        } else {
            // 对称情况
        }
    }
    setColor(x, BLACK);
}

循环调整：当删除的是黑色节点且当前节点不是根节点时，进入循环调整。
- 情况一：兄弟节点为红色：将兄弟节点设置为黑色，父节点设置为红色，对父节点进行左旋操作，然后更新兄弟节点。
- 情况二：兄弟节点的两个子节点都为黑色：将兄弟节点设置为红色，将当前节点上移到父节点，继续循环调整。
- 情况三：兄弟节点的右子节点为黑色，左子节点为红色：将兄弟节点的左子节点设置为黑色，兄弟节点设置为红色，对兄弟节点进行右旋操作，然后更新兄弟节点。
- 情况四：兄弟节点的右子节点为红色：将兄弟节点设置为父节点的颜色，父节点设置为黑色，兄弟节点的右子节点设置为黑色，对父节点进行左旋操作，结束循环。

红黑树在TreeMap中的应用优势

有序性：由于红黑树是二叉搜索树，TreeMap中的键值对按照键的自然顺序（如果没有提供自定义比较器）或者自定义比较器的顺序进行排序。这使得TreeMap非常适合需要有序遍历的场景，例如统计单词出现频率并按字母顺序输出。
高效的操作：红黑树的自平衡特性保证了插入、删除和查找操作的时间复杂度在平均和最坏情况下都是O(log n)。相比普通的二叉搜索树，红黑树在频繁的插入和删除操作下能更好地维持平衡，从而保证操作的高效性。
稳定性：TreeMap在并发环境下虽然不是线程安全的，但在单线程环境或者通过适当的同步机制（如Collections.synchronizedSortedMap）下，能够提供稳定的性能和可预测的行为。

代码示例

以下是一个简单的TreeMap使用示例，展示了红黑树的有序性和基本操作：

import java.util.Map;
import java.util.TreeMap;

public class TreeMapExample {
    public static void main(String[] args) {
        TreeMap<String, Integer> treeMap = new TreeMap<>();
        treeMap.put("apple", 10);
        treeMap.put("banana", 20);
        treeMap.put("cherry", 15);

        // 遍历TreeMap，会按照键的顺序输出
        for (Map.Entry<String, Integer> entry : treeMap.entrySet()) {
            System.out.println(entry.getKey() + " : " + entry.getValue());
        }

        // 删除一个键值对
        treeMap.remove("banana");

        // 再次遍历
        for (Map.Entry<String, Integer> entry : treeMap.entrySet()) {
            System.out.println(entry.getKey() + " : " + entry.getValue());
        }

        // 获取特定键的值
        Integer value = treeMap.get("apple");
        System.out.println("Value of apple: " + value);
    }
}

在上述示例中，我们创建了一个TreeMap，向其中插入了一些键值对，然后遍历输出。接着删除了一个键值对并再次遍历，展示了删除操作的效果。最后获取了特定键的值，体现了TreeMap的查找功能。

通过对Java TreeMap中红黑树结构的深入解析，我们了解了红黑树的基本概念、实现细节以及在TreeMap中的应用优势。这不仅有助于我们更好地使用TreeMap，也为理解其他基于红黑树的数据结构提供了基础。在实际开发中，根据具体需求合理选择数据结构，能够提高程序的性能和效率。例如，在需要有序存储和高效查找、插入、删除操作的场景下，TreeMap是一个很好的选择。同时，深入理解红黑树的原理也有助于我们进行性能优化和解决复杂的数据处理问题。