Java 【数据结构】 TreeSet&TreeMap（二叉搜索树详解）【神装】

在Java中，TreeSet 和 TreeMap 是基于红黑树（一种自平衡的二叉搜索树）实现的集合类，提供了高效的存储和查找数据的能力。本文将深入探讨这两种数据结构的特性、使用场景及其底层实现原理，并给出相应的代码示例。

一、TreeSet

TreeSet 是一个基于 NavigableSet 接口实现的集合，内部使用红黑树来存储元素。与 HashSet 不同的是，TreeSet 是有序的，这意味着集合中的元素会按照自然顺序或按照构造时提供的比较器进行排序。

特性:

1. 元素自动排序：存入 TreeSet 的元素会根据自然顺序或者自定义的比较器顺序排列。
2. 不允许重复：集合中不允许有重复的元素，如果尝试添加已存在的元素，则会返回 false。
3. 操作复杂度：添加、删除和查询操作的时间复杂度为 O(log n)。

示例代码:

import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        TreeSet<Integer> treeSet = new TreeSet<>();

        // 添加元素
        treeSet.add(5);
        treeSet.add(3);
        treeSet.add(7);
        treeSet.add(1);
        treeSet.add(9);

        // 打印 TreeSet
        System.out.println("TreeSet 元素（自然顺序）: " + treeSet);

        // 查找元素
        System.out.println("小于 5 的最大元素: " + treeSet.floor(5));
        System.out.println("大于 5 的最小元素: " + treeSet.higher(5));

        // 删除元素
        treeSet.remove(7);
        System.out.println("删除 7 后的 TreeSet: " + treeSet);
    }
}

二、TreeMap

TreeMap 是基于 NavigableMap 接口实现的映射类，同样使用红黑树作为底层数据结构。其特点是按键的自然顺序或依据指定的比较器对键进行排序。

特性:

1. 有序映射：TreeMap 中的键是有序的。
2. 不允许空键：TreeMap 不允许将 null 元素作为键，但可以存储 null 值。
3. 查找效率高：操作的时间复杂度也是 O(log n)。

示例代码:

import java.util.TreeMap;

public class TreeMapExample {
    public static void main(String[] args) {
        TreeMap<String, Integer> treeMap = new TreeMap<>();

        // 添加键值对
        treeMap.put("Alice", 30);
        treeMap.put("Bob", 25);
        treeMap.put("Charlie", 35);

        // 打印 TreeMap
        System.out.println("TreeMap 元素（键的自然顺序）: " + treeMap);

        // 查找元素
        System.out.println("Bob 的年龄: " + treeMap.get("Bob"));

        // 删除元素
        treeMap.remove("Alice");
        System.out.println("删除 Alice 后的 TreeMap: " + treeMap);

        // 遍历 TreeMap
        System.out.println("遍历 TreeMap:");
        for (String key : treeMap.keySet()) {
            System.out.println(key + ": " + treeMap.get(key));
        }
    }
}

三、总结

TreeSet 和 TreeMap 是强大且灵活的数据结构，适合于需要保持元素或键排序的场景。主要应用包括范围查询、排序输出、队列处理等。在实际开发中，合理使用这两种数据结构，可以极大提高程序的效率与可读性。在选择使用时，要考虑元素的特性、应用场景以及对性能的要求。