Руководство по Java Core. Коллекции. TreeSet.

Класс TreeSet является реализацией интерфейса Set и реализует красно-чёрное дерево. Элементы в этой структуре данных хранятся в упорядоченном по возрастанию порядке.

Эта структура данных является крайне эффективной, когда нам необходимо получить доступ к элементу при большом количестве элементов.

С конструкторами и методами этого класса вы можете ознакомиться в официальной документации.

Для понимания того, как это работает на практике, рассмотрим пример простого приложения.

Пример:

Класс TreeSetDemo

import java.util.TreeSet;

public class TreeSetDemo {
    public static void main(String[] args) {
        TreeSet treeSet = new TreeSet<>();

        System.out.println("Adding elements into treeSet...");

        treeSet.add("9");
        treeSet.add("8");
        treeSet.add("4");
        treeSet.add("2");
        treeSet.add("1");
        treeSet.add("5");
        treeSet.add("6");
        treeSet.add("3");
        treeSet.add("7");
        treeSet.add("10");

        System.out.println("treeSet content:");
        System.out.println(treeSet);
    }
}

В результате работы этой программы мы получим следующий результат:

/*Some System Messages*/

Adding elements into treeSet...
treeSet content:
[1, 10, 2, 3, 4, 5, 6, 7, 8, 9]

Для демонстрации производительности TreeSet рассмотрим пример ещё одного простого приложения.

Пример:

Класс timeElapsedTreeSet

import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;

public class TreeSetPerformanceTest {
    public static void main(String[] args) {
        List arrayList = new ArrayList<>();
        TreeSet treeSet = new TreeSet<>();

        System.out.println("Filling our structures...");

        for (int i = 0; i < 1_000_000; i++) {
            arrayList.add(i);
            treeSet.add(i);
        }

        System.out.println("Trying to receive element 999,999 in arrayList");

        long start = System.nanoTime();
        arrayList.get(999_999);
        long end = System.nanoTime();

        long timeElapsedArrayList = end - start;

        System.out.println("Time elapsed for ArrayList: " + timeElapsedArrayList);



        System.out.println("Trying to receive element 999,999 in arrayList");

        start = System.nanoTime();
        treeSet.get(999_999);
        end = System.nanoTime();

        long timeElapsedTreeSet = end - start;

        System.out.println("Time elapsed for TreeSet: " + timeElapsedTreeSet);

        System.out.println("TreeSet " + (int)(timeElapsedArrayList/timeElapsedTreeSet) + " times more effective");

    }
}

В результате работы этой программы мы получим, примерно, следующий результат:

/*Some System Messages*/

Filling our structures...
Trying to receive element 999,999 in arrayList
Time elapsed for ArrayList: 12962
Trying to receive element 999,999 in arrayList
Time elapsed for TreeSet: 1271
TreeSet 10 times more effective

Как мы видим, в данном случае TreeSet в 10 раз эффективнее, чем ArrayList.

В этом разделе мы изучили основы класса TreeSet и рассмотрели пример простого приложения с его использованием. Мы также увидели на примере приложения, что TreeSet в разы быстрее, чем ArrayList, когда речь идёт о доступе к элементам структуры данных.