CODEWITHSUNDEEP
javadata-structurescollections
Sabir Khan
Sabir Khan

Reputation: 10132

TreeSet Vs Tree

I have few questions related to Collection Frameworks's TreeSet that I am putting here.

  1. Is the only functional difference between TreeSet and ArrayList classes is constraint of unique elements and elements being sorted too in TreeSet?

  2. 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?

I mean, it doesn't seem that set will have anything to do with parent - child relationships.

EDIT - Looks like, I was confused about what I am trying to ask which got clarified after pondering over comments and answers. I guess, my main question should have been "why mathematical set DS ( sorted or unsorted ) is implemented via a Tree?" and that is a duplicate of How to implement Set data structure?

Upvotes: 2

Views: 2113

Answers (4)

Anton Astafiev
Anton Astafiev

Reputation: 126

Internally TreeSet is present as a Tree structure. So this fact influences on operations complexity. Most of operation require O(log n) actions for TRee based structures but array based structures work in constant time for most used read only operation. So HashSet is based on array and allows const time access to its values.

Also they provide different functionality. HashSet just stores elements. It behaves like math set as you sad, in linear manner. But TreeSet provides more operation: take a look at NavigableSet and SortedSer interfaces it implements. Elements of TreeSet are always sorted. But in the same time they require setting sorting rules for them provided by impelemting Comparable interface or using side Comparator object.

Upvotes: 1

Madhusudana Reddy Sunnapu
Madhusudana Reddy Sunnapu

Reputation: 8247

Is the only functional difference between TreeSet and ArrayList classes is constraint of unique elements and elements being sorted too in TreeSet?

That is major difference, apart from internal implementation, and this enables TreeSet to provide functions like subset, tailset, headSet which are not possible with a ArrayList.

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.

Yes, it is hierarchical structure. Internally the implementation is a Red-black binary tree.

Is there really any similarity / relation between Tree Data Structure and Java's TreeSet or name TreeSet just a coincidence?

The internal implementation is a R-B binary tree.

On a side note, since these two are different data structures, time complexity of TreeSet is completely from ArrayList for same set of operations. For ex: add ArrayList is O(1) but for TreeSet it is O(logn), search for arrayList is O(n) and for TreeSet is is O(logn) and so on...

Upvotes: 1

Gary Y Kim
Gary Y Kim

Reputation: 79

TreeSet is real tree, not coincidence. So there's many difference with Arraylist. For example performance ( I mean Big-O ) is totally different.

Upvotes: 1

Henry
Henry

Reputation: 43728

In terms of usage it is just a Set, plus some extra goodies like having a definite sequence. However, it is internally implemented as a tree.

The naming convention here is similar as with HashSet, another Set internally implemented as a hash table.

Upvotes: 0

Related Questions