图解TreeSet数据结构设计与应用案例

时间：2024-12-17 11:26:30

在这里插入图片描述

TreeSet 是 Java 中一个基于红黑树实现的有序集合，它继承自 AbstractSet 并实现了 NavigableSet 接口。TreeSet 中的元素按照自然顺序或通过提供的 Comparator 进行排序，确保元素处于排序状态。它支持快速的插入、删除、查找和范围查询操作，具有对数时间复杂度。TreeSet 是非线程安全的，适用于需要有序集合的场景，如需要排序的数据集、范围查询和有序迭代。

肖哥弹架构 跟大家“弹弹” 高并发锁， 关注公号回复 'mvcc' 获得手写数据库事务代码

欢迎 点赞，关注，评论。

关注公号Solomon肖哥弹架构获取更多精彩内容

历史热点文章

  • 解锁大语言模型参数：零基础掌握大型语言模型参数奥秘与实践指南
  • 高性能连接池之HikariCP框架分析：高性能逐条分解(架构师篇)
  • 缓存雪崩/穿透/击穿/失效原理图/14种缓存数据特征+10种数据一致性方案
  • Java 8函数式编程全攻略：43种函数式业务代码实战案例解析(收藏版)
  • 一个项目代码讲清楚DO/PO/BO/AO/E/DTO/DAO/ POJO/VO
  • 17个Mybatis Plugs注解：Mybatis Plugs插件架构设计与注解案例(必须收藏)

1、 TreeSet

TreeSet 是 Java 集合框架中的一个有序集合类，实现了 Set 接口。以下是 TreeSet 的设计：

设计思考：
  1. 需求场景：
    • 在许多编程任务中，需要存储不重复的元素，并且这些元素需要保持一定的顺序，例如，自然排序或自定义排序顺序。
    • 例如，在处理需要排序的配置选项、用户权限、需要按顺序处理的任务列表等场景时，元素的排序顺序是非常重要的。
  2. 现有技术局限性：
    • HashSet 提供了非常快的查找、添加和删除操作，但它不保证元素的任何特定顺序。
    • ArrayList 和 LinkedList 可以保持插入顺序，但查找操作需要线性时间。
  3. 技术融合：
    • TreeSet 结合了 HashSet 的快速查找特性和 ArrayList/LinkedList 的元素顺序保持功能，但通过使用红黑树（一种自平衡的二叉搜索树）实现，提供了有序的元素集合。
  4. 设计理念：
    • TreeSet 提供了一个不允许重复元素的数据结构，同时保证了元素处于排序状态，可以进行有效的范围查询和排序操作。
  5. 实现方式：
    • TreeSet 内部使用 TreeMap 的实例来存储元素，其中元素作为键，值是一个固定的虚拟对象（如 PRESENT），从而保证了元素的唯一性。
2、 数据结构

在这里插入图片描述

图说明：
  • TreeSet:
    • 表示 TreeSet 类的实例，它实现了 Set 接口，并保证元素处于排序状态。
  • TreeMap:
    • TreeSet 基于 TreeMap 实现，其中元素作为键存储，而不关心值。
  • 红黑树:
    • TreeMap 的底层数据结构是一个红黑树，它是一个自平衡的二叉搜索树。
  • 根节点:
    • 红黑树的根节点，是树的入口。
  • 左子节点和右子节点:
    • 表示红黑树节点的子节点。
  • 元素A, 元素B, 元素C:
    • 实际存储在 TreeSet 中的数据。
3、 执行流程

在这里插入图片描述

图说明：
  1. 添加元素：
    • 计算元素的自然排序：根据元素的自然顺序或提供的 Comparator 计算排序。
    • 构建红黑树：TreeSet 基于红黑树数据结构，确保元素处于排序状态。
    • 确定插入位置：在红黑树中找到元素的插入位置。
    • 插入元素到红黑树：将元素插入到红黑树中。
  2. 删除元素：
    • 计算元素的自然排序：根据元素的自然顺序或提供的 Comparator 计算排序。
    • 查找红黑树：在红黑树中查找要删除的元素。
    • 删除元素从红黑树：从红黑树中删除元素。
  3. 遍历 TreeSet：
    • 获取红黑树根节点：获取红黑树的根节点，开始遍历。
    • 遍历红黑树节点：遍历红黑树的每个节点。
    • 读取元素：从红黑树的节点中读取元素。
4、优点：
  1. 有序性：
    • 元素会根据其自然顺序或构造时提供的 Comparator 进行排序。
  2. 快速查找：
    • 提供了对数时间复杂度的查找性能。
  3. 元素唯一性：
    • 自动处理元素的唯一性，避免了重复元素的问题。
  4. 范围查询：
    • 可以方便地进行范围查询和获取子集。
5、缺点：
  1. 性能开销：
    • 相比于 HashSet，TreeSet 在添加、删除和查找操作上有更高的性能开销。
  2. 内存消耗：
    • 相比于 HashSet，TreeSet 可能需要更多的内存来存储红黑树结构。
  3. 数据实时性：
    • 由于排序操作的开销，TreeSet 在数据更新时可能不如 HashSet 快。
6、使用场景：
  • 需要保持元素排序顺序的场景，如排序的配置列表、按顺序执行的任务调度等。

7、类设计

在这里插入图片描述

8、应用案例

TreeSet 通常用于需要保持元素有序的集合。这是一个简单的图书管理系统，用于存储图书的ISBN号，并保持它们有序：

import java.util.TreeSet;

// 图书类，用于表示图书的ISBN号
class Book {
    private String isbn;

    public Book(String isbn) {
        this.isbn = isbn;
    }

    public String getIsbn() {
        return isbn;
    }

    @Override
    public String toString() {
        return "ISBN: " + isbn;
    }
}

// 图书管理系统类
class BookManager {
    private TreeSet<String> isbnSet;

    public BookManager() {
        isbnSet = new TreeSet<>();
    }

    // 添加图书到系统
    public void addBook(String isbn) {
        isbnSet.add(isbn);
    }

    // 获取所有图书的ISBN号
    public TreeSet<String> getIsbnSet() {
        return isbnSet;
    }

    public static void main(String[] args) {
        BookManager bookManager = new BookManager();

        // 添加图书到系统
        bookManager.addBook("978-3-16-148410-0");
        bookManager.addBook("978-1-4028-9462-6");
        bookManager.addBook("978-0-596-52068-7");

        // 获取并打印所有图书的ISBN号
        TreeSet<String> isbnSet = bookManager.getIsbnSet();
        for (String isbn : isbnSet) {
            System.out.println(isbn);
        }
    }
}

相关文章