TreeSet Vs树

Question

我在这里提出了几个与集合框架的TreeSet相关的问题。

1. TreeSet和ArrayList类之间唯一的功能区别是在TreeSet中对唯一元素和元素进行排序的约束。
2. 前缀Tree的存在给将TreeSet可视化为分层数据结构或线性数据结构造成了混乱。数学集是线性数据结构，而名称Tree在计算中表示为分层数据结构。 Tree数据结构与Java的TreeSet或名称TreeSet之间真的有任何相似/关系只是巧合吗？

我的意思是，这似乎与父子关系没有任何关系。

编辑--看起来，我对我想问的是什么感到困惑，在思考了评论和答案之后，哪个问题被澄清了。我想，我的主要问题应该是“为什么数学集DS (排序或未排序)是通过树实现的？”这是How to implement Set data structure?的复制品

Answer 1

TreeSet和ArrayList类之间唯一的功能区别是在TreeSet中对唯一元素和元素进行排序的约束吗？

除了内部实现之外，这是一个很大的区别，这使得TreeSet能够提供子集、尾集、headSet等功能，这些功能在ArrayList中是不可能的。

前缀树的存在给将TreeSet可视化为分层数据结构或线性数据结构造成了混乱。数学集是线性的数据结构，而名称树在计算中表示的是层次结构。

是的，这是等级结构。在内部，实现是一个红黑二叉树.

树数据结构与Java的TreeSet或名称TreeSet之间真的有任何相似/关系只是巧合吗？

内部实现是一个R二叉树.

另外，由于这两种数据结构不同，对于同一组操作，TreeSet的时间复杂度完全来自ArrayList。例如:添加ArrayList是O(1)，而对于TreeSet是O(logn)，搜索arrayList是O(n)，搜索TreeSet是O(logn)等等。

Answer 2

TreeSet是真正的树，不是巧合。所以和Arraylist有很多不同。例如，性能(我的意思是Big)完全不同。

Answer 3

在使用上，它只是一个Set，加上一些额外的好处，如有一个明确的序列。但是，它是作为树在内部实现的。

这里的命名约定与HashSet类似，后者是在内部实现为哈希表的另一个Set。