一起学习集合框架之 TreeSet

举报
宇宙之一粟 发表于 2022/08/31 14:42:52 2022/08/31
【摘要】 什么是 TreeSetTreeSet 是一个具有唯一元素的二叉树的集合,又被翻译为 树集。Java 中的 TreeSet 类是 Java 集合框架的一部分,从 Java 6 开始,它实现了 NavigableSet 接口(这个接口增加了几个查找元素以及反向遍历的便利方法),从而扩展了 SortedSet 集合。TreeSet 类与散列类十分相似,不过,它比普通的集合有所改进,树集是一个有序集...

什么是 TreeSet


TreeSet 是一个具有唯一元素的二叉树的集合,又被翻译为 树集。Java 中的 TreeSet 类是 Java 集合框架的一部分,从 Java 6 开始,它实现了 NavigableSet 接口(这个接口增加了几个查找元素以及反向遍历的便利方法),从而扩展了 SortedSet 集合。


TreeSet 类与散列类十分相似,不过,它比普通的集合有所改进,树集是一个有序集合(sorted collection),该数据结构的元素按自然顺序排序。


  • SortedSet 接口提供了保持元素排序的功能。

  • Navigableset 接口提供了可以通过 SortedSet 检索的功能。例如,找到该元素大于或小于给定元素,找到排序集中的第一个和最后一个元素。


接口 API


我们来看看 TreeSet 的接口:

TreeSet()

public TreeSet() {
		this(new TreeMap<>());
}


TreeSet(Comparator<? super E> comparator)

public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}


TreeSet(Collection<? extends E> c)


    public TreeSet(Collection<? extends E> c) {
        this();
        addAll(c);
    }


TreeSet(SortedSet<E> s)

    public TreeSet(SortedSet<E> s) {
        this(s.comparator());
        addAll(s);
    }


其他方法

其他方法,可以读者自行研究,如下:

因为实现了 SortedSet 接口,因此具有:

  • Comparator<? super E> comparator()

  • E first()

  • E last()


又实现了 NavigableSet<E> 接口:

  • E higher(E value)E lower(E value) :返回大于 value 的最小元素和小于 value 的最大元素,如果没有则返回 null

  • E celling(E value)E floor(E value) :返回大于等于 value 的最小元素或小于等于 value 的最大元素,如果没有 则返回 null

  • E pollFirst()E pullLast():删除并返回这个集合中的最大元素或最小元素,这个集合为空时返回 null

  • Iterator<E> descendingIterator():返回一个按照递减顺序遍历集合中元素的迭代器


简单的 TreeSet 例子


我们可以以任意顺序将元素插入到集合中,在对集合进行遍历时,会返回排序好的值。例如:


import java.util.TreeSet;

public class TreeSetExample {

	public static void main(String[] args) {
		// 定义一个 String 类型的树集
		TreeSet<String> treeset = new TreeSet<String>();
		
		// 添加元素
		treeset.add("Learning TreeSet");
		treeset.add("Hello, world!");
		treeset.add("ABC");
		treeset.add("Yuzhou1su");
		treeset.add("宇宙之一粟");
		
		for (String ts : treeset) {
			System.out.println(ts);
		}

	}

}

运行结果:

ABC
Hello, world!
Learning TreeSet
Yuzhou1su
宇宙之一粟


正如 TreeSet 类名一般,排序是通过树数据结构完成的(实现的是红黑树),如果要使用树集,必须能够比较元素,即这些元素必须实现 Comparable 接口,或者构造集必须提供一个 Comparator。


自定义比较器的 TreeSet

树集中默认是升序,让我们来自定义一个降序的比较器:

package com.yuzhou1su.TreeSetExample;

import java.util.TreeSet;
import java.util.Comparator;
import java.util.SortedSet;

public class TreeSetDescendingOrderExample {
	

	public static void main(String[] args) {
		
		SortedSet<Integer> nums = new TreeSet<>(Comparator.reverseOrder());
		
		nums.add(1);
		nums.add(99);
		nums.add(20);
		nums.add(2022);
		nums.add(2035);
		
		System.out.println("Descending order:" + nums);
	}

}


运算结果:

Descending order:[2035, 2022, 99, 20, 1]



下面来看一下 TreeSet 如何创建、往其中插入元素、如何搜索和字符串化操作。如何集合为空,则 TreeSet 只允许一个空值。TreeSet 的添加、删除和查找包含的函数的算法复杂度为 log(n)


插入节点


func (treeset *TreeSet) InsertTreeNode(treeNodes ...TreeNode) {
}


参考链接:

  • 《Java 核心技术 卷 1 》j(原书第 11 版):9.3.4 树集,Page 388-389

  • https://pkg.go.dev/gitee.com/mirrors/gods.git/sets/treeset

  • https://github.com/emirpasic/gods/blob/master/sets/treeset/treeset.go

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。