我有几个与此处放置的 Collection Frameworks TreeSet
相关的问题。
TreeSet
和ArrayList
类之间唯一的功能区别是唯一元素的约束以及在TreeSet
中排序的元素吗?前缀
Tree
的存在会造成将TreeSet
可视化为分层数据结构或线性数据结构的困惑。数学集合是线性数据结构,而计算中的名称“树”表示分层数据结构。Tree
数据结构和Java的TreeSet
之间真的有任何相似/关系吗?或者名称TreeSet
只是巧合?
我的意思是,set 似乎与父子关系没有任何关系。
编辑 - 看起来,我对我想问的问题感到困惑,在思考评论和答案后得到了澄清。我想,我的主要问题应该是“为什么数学集 DS(排序或未排序)是通过树实现的?”这是 How to implement Set data structure? 的重复项
最佳答案
Is the only functional difference between TreeSet and ArrayList classes is constraint of unique elements and elements being sorted too in TreeSet?
除了内部实现之外,这是一个主要区别,这使得 TreeSet 能够提供 ArrayList 无法实现的子集、tailset、headSet 等功能。
Presence of prefix Tree creates a confusion about visualizing a TreeSet as a hierarchical data structure or linear one. Mathematical sets are linear data structures while name Tree in computing indicates a hierarchical one.
是的,它是层次结构。内部实现是红黑二叉树。
Is there really any similarity / relation between Tree Data Structure and Java's TreeSet or name TreeSet just a coincidence?
内部实现是一个R-B二叉树。
顺便说一句,由于这两个是不同的数据结构,对于同一组操作,TreeSet 的时间复杂度完全不同于 ArrayList。例如:添加 ArrayList 是 O(1),但对于 TreeSet 是 O(logn),搜索 arrayList 是 O(n),对于 TreeSet 是 O(logn) 等等...
关于java - 树集与树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35224252/