Search code examples
javatreemaptreeset

What's the basic (not immediate) backing data structure used by JAVA TreeSet?

So TreeSet uses TreeMap as backing data structures (with dummy vaues corresponding to keys) & TreeMap in turn uses Red-Black tree which is a self balancing BST.

Now what does this Red-Black tree use as a backing data structure? Is it an array or linkedlist?

My understanding is that it's a linkedlist because in TreeSet, operations like .first() return the smallest value & not the root & it has O(1) time complexity.

So basically it's a linkedlist alongwith bunch of pointers for least, greatest, root of linkedlist etc. Is my understanding correct?

Solution

  • It is neither an array nor a linked list. It is a tree of Java objects, which is distinct from either.

    Look at, for example, the difference between the diagram of a linked list and a tree. They're fundamentally different.

    The red-black tree you mention is the data structure. It does not have a "backing data structure."