【数据结构】TreeMap及TreeSet

欢迎浏览高耳机的博客

希望我们彼此都有更好的收获

感谢三连支持！

一、概念 

TreeMap和TreeSet都是Java中基于红黑树（Red-Black tree）实现的有序集合类。它们分别实现了SortedMap和SortedSet接口，因此提供了按照键（对于TreeMap）或元素（对于TreeSet）的自然顺序或者通过比较器进行排序的功能。

通常将用于搜索的数据称为关键字（Key），对应的数据称为值（Value）。这种键值对结构被称为Key-Value模型，其中包括两种主要类型：

1. 纯Key：仅包含一个搜索关键字，与对应的值无关，只用于查找关键字。例如，像英文词典中快速查找单词是否存在。

2. Key-Value模型：涉及对存储的数值进行操作，需要同时处理关键字和对应的值。例如，统计文件中每个单词出现的次数，这种模型会存储每个单词及其出现次数的键值对。

在数据结构中，Map存储Key-Value的键值对，而Set只存储Key。因此，在选择适合自己操作的数据模型时，需要考虑具体需求和操作类型。

二、TreeSet常用方法和应用时事项

1. Set是继承自Collection的一个接口类
2. Set中只存储了key，并且要求key一定要唯一
3. TreeSet的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的
4. Set最大的功能就是对集合中的元素进行去重
5. 实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。
6. Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入
7. TreeSet中不能插入null的key，HashSet可以。 

三、TreeMap常用方法和应用时事项 

1. Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap
2. Map中存放键值对的Key是唯一的，value是可以重复的
3. 在TreeMap中插入键值对时，key不能为空，否则就会抛NullPointerException异常，value可以为空。但是HashMap的key和value都可以为空。
4. Map中的Key可以全部分离出来，存储到Set中来进行访问(因为Key不能重复)。
5. Map中的value可以全部分离出来，存储在Collection的任何一个子集合中(value可能有重复)。
6. Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入。 

四、OJ实例 

https://leetcode.cn/problems/single-number/description/

使用TreeSet实现如下：

 public int singleNumber(int[] nums) {
        Set<Integer> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (!set.add(nums[i])) { // add方法返回false表示元素已经存在，不需要添加
                set.remove(nums[i]); // 如果已存在，从set中移除该元素
            }
        }
        
        // 最后set中剩下的就是唯一的元素
        if (!set.isEmpty()) {
            Iterator<Integer> iterator = set.iterator();
            return iterator.next(); // 返回set中的唯一元素
        }
        
        return -1; // 如果set为空，则返回-1表示未找到唯一的元素
    }

使用TreeMap实现如下：

 public int singleNumber(int[] nums) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        
        // 使用TreeMap来统计每个元素的出现次数
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        
        // 遍历TreeMap找到出现次数为1的元素
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        
        return -1; // 如果没有找到出现次数为1的元素，返回-1
    }

---

希望这篇博客能为你理解java编程思想提供一些帮助。

如有不足之处请多多指出。

我是高耳机。