Search code examples
javatreesetred-black-tree

What structure is underlying Java TreeSet?

Java TreeSet is a red-black tree self balancing structure.

But what is the structure to store the data? Array or linked list?

Solution

  • TreeSet is backed by a TreeMap (in similar way HashSet is backed by HashMap). If you look at TreeSet constructor:

    public TreeSet() {
    this(new TreeMap<E,Object>());
}

    TreeMap internally stores data using nodes represented with TreeMap.Entry class:

    static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;
...

    There is no additional array or list there.