TreeMap的内部数据结构是怎样的？

八股文_Java集合面试题 0 2

参考回答

TreeMap 的内部数据结构是 红黑树（Red-Black Tree）。
红黑树是一种自平衡的二叉搜索树，它在插入、删除时通过调整树的结构（如旋转、变色）来保持平衡，从而确保操作的时间复杂度是 O(log n)。

详细讲解与拓展

1. 红黑树的特点

红黑树是一种特殊的二叉搜索树（BST），在普通 BST 的基础上增加了一些额外的平衡规则，使得它的高度保持接近对数级别，从而提高操作效率。

红黑树有以下特点：

每个节点是红色或黑色。
根节点是黑色。
每个叶子节点（空节点）是黑色的 NIL 节点。
红色节点不能连续出现：
- 即每个红色节点的子节点必须是黑色（树中不存在两个连续的红色节点）。
从任一节点到其叶子节点的每条路径上必须具有相同数量的黑色节点（黑高一致性）。

通过这些规则，红黑树实现了良好的平衡性，使得在最坏情况下，红黑树的高度最多是 log(n) 的 2 倍，从而避免了普通二叉搜索树在极端情况下退化为链表。

2. TreeMap 的底层实现

核心结构：红黑树

在 TreeMap 中，所有的键值对（key-value）以 红黑树节点 的形式存储。
每个节点维护了以下信息：
- key：键，用于树的排序。
- value：值，与键对应。
- left：指向左子树的指针。
- right：指向右子树的指针。
- parent：指向父节点的指针。
- color：节点颜色（红或黑）。

节点的定义（Java 代码片段） 在 TreeMap 的源码中，每个节点的实现如下：

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

   // 获取键和值的方法
   public K getKey() { return key; }
   public V getValue() { return value; }
   public V setValue(V value) {
       V oldValue = this.value;
       this.value = value;
       return oldValue;
   }
}

3. TreeMap 的操作实现

TreeMap 中的基本操作（如插入、删除、查找）都依赖于红黑树的特性。

3.1 插入

定位插入位置：
- 根据键的自然顺序（或自定义比较器），通过二叉搜索找到插入的位置。
- 如果键已存在，则直接更新对应的值。
插入新节点：
- 插入的新节点默认是红色。
- 插入后可能会破坏红黑树的平衡（例如连续两个红色节点），此时需要通过调整操作（变色、旋转）恢复平衡。

3.2 删除

定位节点：
- 根据键值找到需要删除的节点。
删除节点：
- 删除时可能会导致红黑树的平衡被破坏。
- 如果删除的是红色节点，则不会影响平衡；如果删除的是黑色节点，则需要通过变色和旋转来恢复平衡。

3.3 查找

根据键的自然顺序（或比较器），从根节点开始，沿着树结构递归查找对应的键。
时间复杂度是 O(log n)。

4. 红黑树的调整操作

红黑树的平衡性由以下两种操作维护：

旋转：
- 包括左旋和右旋，用于调整节点的层次结构。
- 例如，插入后，如果树中出现连续的红色节点，可以通过旋转将红色节点调整到合适的位置。
变色：
- 改变节点的颜色（红色变黑色，或者黑色变红色），用于满足红黑树的特性。

5. 示例：TreeMap 的插入和排序

代码示例：

import java.util.TreeMap;

public class TreeMapExample {
    public static void main(String[] args) {
        // 创建 TreeMap，按照键的自然顺序排序
        TreeMap<Integer, String> treeMap = new TreeMap<>();

        // 插入键值对
        treeMap.put(3, "C");
        treeMap.put(1, "A");
        treeMap.put(2, "B");
        treeMap.put(5, "E");
        treeMap.put(4, "D");

        // 遍历输出，键会自动按照升序排序
        for (var entry : treeMap.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
    }
}

输出：

1 -> A
2 -> B
3 -> C
4 -> D
5 -> E

6. TreeMap 的特点和应用场景

6.1 TreeMap 的特点

有序性：
- 键会按照 自然顺序（或自定义比较器）进行排序。
- 遍历时，元素总是以有序的方式输出。
时间复杂度：
- 插入、删除、查找操作的时间复杂度是 O(log n)，效率高于链表。
线程安全性：
- TreeMap 本身不是线程安全的。如果需要在多线程环境中使用，可以使用 Collections.synchronizedSortedMap() 或 ConcurrentSkipListMap。

6.2 TreeMap 的应用场景

需要有序 Map：

例如实现一个按时间排序的任务调度器。

范围查询：

提供诸如 subMap()、headMap()、tailMap() 等方法，方便对键进行范围查询。
示例：

“`java
TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(1, "A");
treeMap.put(3, "C");
treeMap.put(5, "E");
System.out.println(treeMap.subMap(2, 5)); // 输出：{3=C}
“`

总结

TreeMap 的底层数据结构是 红黑树，它是一种自平衡的二叉搜索树。
红黑树通过旋转和变色来保持平衡，保证了操作的时间复杂度为 O(log n)。
TreeMap 适合需要 有序性 或 范围查询 的场景，缺点是比 HashMap 更占用内存，操作性能也略低。