How Java TreeSet are implemented

Question

I was wondering how a TreeSet is implemented in Java. In fact, I was wondering, is a TreeSet using, under the hood, a balancing tree, or is it using an array ?

In other word, when I am adding an element to my treeSet, I know it will be ordered, but will it will be:

• add in an array, which mean that when my array is full, it will need to create a new array and copy all element from the old one to the new one.

• add at a random spot in the memory and linked to the element before it and after it ? If so, is it balancing the element, so the "top" of the tree is alway at the middle of the element, or is it just adding "leaf" where it fit, resulting in a "linear" tree ?

It has been a while since I study data structure, so just let's me know if my question make no sens or is not well explained.

Thank you

Answer 1

Java's TreeSet uses a TreeMap, which is backed by a red-black tree. So, mostly the second option, but red-black trees are self-balancing so you won't run into the pathological "linear" case even if you insert elements in ascending/descending order.