1

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?

Little_idiot
  • 125
  • 1
  • 8
  • Here is another good explanation of your question, https://stackoverflow.com/questions/14923407/why-red-black-tree-based-implementation-for-java-treemap?rq=1 – Rajib Deka Jan 03 '20 at 08:29

1 Answers1

4

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."

Louis Wasserman
  • 191,574
  • 25
  • 345
  • 413
  • Thanks ! left and right variable used in entry isnt it sounding like next node and prev node . – Pramod S. Nikam Jan 03 '20 at 07:56
  • Correct me if I am wrong, but whatsoever abstract data structure I am using, has to either rely on array or linked list. In that diagram of binary search tree with one Node pointing to another, if I am not mistaken looks like a doubly linked list – Little_idiot Jan 03 '20 at 08:02
  • 4
    @Little_idiot: "whatsoever abstract data structure I am using, has to either rely on array or linked list" This statement is incorrect. It might have to rely on either an array or _references/pointers_, or a combination, but those do not imply that a data structure is a linked list. – Louis Wasserman Jan 03 '20 at 08:06
  • Thanks Deleting my answer! But I cant because of its accepted answer! – Pramod S. Nikam Jan 03 '20 at 08:14