TreeSet

Dua chapter sebelumnya memberi kita Set yang cepat (HashSet) dan Set yang terurut penyisipan (LinkedHashSet), tetapi keduanya sama-sama tidak tahu mana elemen terkecil atau terbesar. TreeSet menutup celah tersebut dengan janji yang lebih kuat: isinya selalu terurut menurut urutan alami elemen atau Comparator yang kita tentukan, dan karenanya mendukung pertanyaan-pertanyaan berbau rentang seperti “harga terdekat di bawah 12.000” atau “semua elemen mulai dari 15.000 ke atas”. Kemampuan tersebut diwadahi interface NavigableSet yang dibawa TreeSet. Pada Chapter ini kita bedah pohon di baliknya, melatih navigasi rentang, dan menyiapkan Comparator kustom saat urutan alami tidak sesuai kebutuhan.

Pohon Merah-Hitam di Balik Layar #

TreeSet membungkus sebuah TreeMap yang menyusun elemen sebagai red-black tree — pohon pencarian biner yang menjaga keseimbangan sehingga tingginya selalu O(log n). Setiap penyisipan menurunkan elemen dari akar: lebih kecil ke kiri, lebih besar ke kanan, sampai menemukan tempatnya. Menyimpan [15000, 5000, 25000, 10000, 40000] akan menempatkan 5000 di cabang kiri 15000 dan 40000 di cabang kanan — dan ketika pohon berjalan in-order (kiri, akar, kanan), elemen keluar dalam keadaan terurut tanpa penyortiran terpisah.

Keseimbangan inilah sumber profil kinerja TreeSet: add, contains, dan remove masing-masing O(log n) — lebih lambat daripada O(1) rata-rata HashSet, tetapi tetap cepat untuk jutaan elemen. Sebagai gantinya, keputusan urutan bisa diambil kapan saja tanpa menyortir ulang.

Navigasi dengan NavigableSet #

Interface NavigableSet melengkapi TreeSet dengan method ujung dan method tetangga terdekat. Program berikut menyimpan lima level harga dan menjajal seluruh method navigasi utama:

import java.util.*;

public class HargaNavigasi {
    public static void main(String[] args) {
        TreeSet<Integer> harga = new TreeSet<>(List.of(15000, 5000, 25000, 10000, 40000));
        System.out.println("Isi terurut      : " + harga);

        // Ujung nilai.
        System.out.println("first()          : " + harga.first());
        System.out.println("last()           : " + harga.last());

        // Navigasi ke tetangga terdekat.
        System.out.println("floor(12000)     : " + harga.floor(12000));
        System.out.println("ceiling(12000)   : " + harga.ceiling(12000));
        System.out.println("lower(25000)     : " + harga.lower(25000));
        System.out.println("higher(25000)    : " + harga.higher(25000));

        // Potongan rentang (view, bukan salinan).
        System.out.println("headSet(15000)   : " + harga.headSet(15000));
        System.out.println("tailSet(15000)   : " + harga.tailSet(15000));
    }
}

Output yang Dihasilkan:

Isi terurut      : [5000, 10000, 15000, 25000, 40000]
first()          : 5000
last()           : 40000
floor(12000)     : 10000
ceiling(12000)   : 15000
lower(25000)     : 15000
higher(25000)    : 40000
headSet(15000)   : [5000, 10000]
tailSet(15000)   : [15000, 25000, 40000]

Mari kita bedah baris-baris pentingnya:

1. Baris 6 (new TreeSet<>(List.of(...))): konstruktor menerima koleksi apa pun; kelima harga tersusun otomatis terurut naik [5000, 10000, 15000, 25000, 40000] meski urutan masuknya acak.
2. Baris 9-10 (first() / last()): membaca elemen terkecil dan terbesar — O(log n) pada pohon, bukan hasil pemindaian penuh.
3. Baris 13-14 (floor(12000) / ceiling(12000)): floor mengembalikan elemen terbesar yang masih ≤ argumen (10000), ceiling mengembalikan elemen terkecil yang masih ≥ argumen (15000). Keduanya mengembalikan null jika tidak ada kandidat — contoh nyata: floor(4000) akan mengembalikan null.
4. Baris 15-16 (lower / higher): versi ketat tanpa kesetaraan — lower(25000) mengembalikan 15000 (tepat di bawah), higher(25000) mengembalikan 40000 (tepat di atas).
5. Baris 19-20 (headSet(15000) / tailSet(15000)): memotong rentang — headSet berisi elemen sebelum batas, tailSet berisi elemen mulai batas ke atas.

Syarat Wajib Elemen Terurut #

Kecepatan pohon bergantung pada satu syarat: setiap pasangan elemen harus bisa dibandingkan. Tanpa Comparator pada konstruktor, TreeSet memanggil compareTo dari interface Comparable — dan elemen yang tidak mengimplementasikan Comparable membuat program gagal saat runtime, bukan saat kompilasi. Berkas berikut sengaja mendemonstrasikan kegagalan tersebut:

import java.util.*;

public class ButuhComparableGagal {
    public static void main(String[] args) {
        TreeSet<Object> rak = new TreeSet<>();
        // Object tidak mengimplementasikan Comparable -> gagal saat runtime.
        rak.add(new Object());
        System.out.println("Baris ini tidak pernah tercetak.");
    }
}

Saat dijalankan, JVM menghentikan program dengan exception:

Exception in thread "main" java.lang.ClassCastException: class java.lang.Object
cannot be cast to class java.lang.Comparable

Compiler javac menerima TreeSet<Object> tanpa keluhan karena pemeriksaan tipe generik tidak menuntut Comparable; barulah add pertama membandingkan elemen dan menemukan Object tidak bisa di-cast ke Comparable. Tipe pembungkus (Integer, String, LocalDate) dan mayoritas class pustaka sudah mengimplementasikan Comparable; untuk class buatan sendiri, kita bisa mengimplementasikan Comparable atau — lebih luwes — menyerahkan Comparator eksternal sebagaimana dicontohkan di bawah. Pembahasan mendalam tentang kedua interface tersebut tersedia pada Chapter Comparable dan Comparator.

Comparator Kustom untuk Urutan Sendiri #

Kadang urutan alami tidak sesuai kebutuhan. Misalnya sebuah lomba menginginkan daftar peserta terurut berdasarkan panjang nama baru kemudian alfabetis. Comparator yang dirakit dengan comparingInt(...).thenComparing(...) diteruskan ke konstruktor TreeSet:

import java.util.*;

public class UrutanKustom {
    public static void main(String[] args) {
        // Comparator: panjang nama dulu, lalu urutan alfabetis.
        Comparator<String> panjangLaluAbjad =
                Comparator.comparingInt(String::length)
                          .thenComparing(Comparator.naturalOrder());

        TreeSet<String> peserta = new TreeSet<>(panjangLaluAbjad);
        peserta.addAll(List.of("Siti", "Budi", "Dewi", "Anton", "Rani"));
        System.out.println("Isi terurut : " + peserta);

        // Navigasi mengikuti urutan comparator, bukan urutan alfabetis murni.
        System.out.println("first()     : " + peserta.first());
        System.out.println("last()      : " + peserta.last());
        System.out.println("ceiling(\"Alex\") : " + peserta.ceiling("Alex"));
    }
}

Output yang Dihasilkan:

Isi terurut : [Budi, Dewi, Rani, Siti, Anton]
first()     : Budi
last()      : Anton
ceiling("Alex") : Budi

Poin bedahnya:

1. Baris 6-8 (Comparator.comparingInt(String::length).thenComparing(...)): perbandingan utama memakai panjang nama; bila sama panjang, perbandingan kedua memakai urutan alami string.
2. Baris 11 (new TreeSet<>(panjangLaluAbjad)): satu Comparator mengubah total definisi urutan set ini; nama empat huruf (Budi, Dewi, Rani, Siti) mendahului nama lima huruf (Anton) meski secara alfabetis Anton lebih dulu.
3. Baris 14-17 (first, last, ceiling): seluruh navigasi mengikuti comparator tersebut — ceiling("Alex") mengembalikan Budi karena Alex (4 huruf) “kurang dari” seluruh peserta pada urutan panjang-lalu-abjad.

Dengan TreeSet, urutan dan navigasi rentang menjadi layanan bawaan struktur data. Namun ada satu keluarga kebutuhan yang belum tersentuh: antrean — struktur yang kepala dan ekornya hidup berdasarkan waktu kedatangan. Chapter berikutnya membuka cabang Queue dari hierarki Collection.

Referensi #

• Java API Specification: java.util.TreeSet
• Java API Specification: java.util.NavigableSet
• Dev.java: The Java Collections Framework

import java.util.*;

public class ButuhComparableGagal {
    public static void main(String[] args) {
        TreeSet<Object> rak = new TreeSet<>();
        // Object tidak mengimplementasikan Comparable -> gagal saat runtime.
        rak.add(new Object());
        System.out.println("Baris ini tidak pernah tercetak.");
    }
}

import java.util.*;

public class HargaNavigasi {
    public static void main(String[] args) {
        TreeSet<Integer> harga = new TreeSet<>(List.of(15000, 5000, 25000, 10000, 40000));
        System.out.println("Isi terurut      : " + harga);

        // Ujung nilai.
        System.out.println("first()          : " + harga.first());
        System.out.println("last()           : " + harga.last());

        // Navigasi ke tetangga terdekat.
        System.out.println("floor(12000)     : " + harga.floor(12000));
        System.out.println("ceiling(12000)   : " + harga.ceiling(12000));
        System.out.println("lower(25000)     : " + harga.lower(25000));
        System.out.println("higher(25000)    : " + harga.higher(25000));

        // Potongan rentang (view, bukan salinan).
        System.out.println("headSet(15000)   : " + harga.headSet(15000));
        System.out.println("tailSet(15000)   : " + harga.tailSet(15000));
    }
}

import java.util.*;

public class UrutanKustom {
    public static void main(String[] args) {
        // Comparator: panjang nama dulu, lalu urutan alfabetis.
        Comparator<String> panjangLaluAbjad =
                Comparator.comparingInt(String::length)
                          .thenComparing(Comparator.naturalOrder());

        TreeSet<String> peserta = new TreeSet<>(panjangLaluAbjad);
        peserta.addAll(List.of("Siti", "Budi", "Dewi", "Anton", "Rani"));
        System.out.println("Isi terurut : " + peserta);

        // Navigasi mengikuti urutan comparator, bukan urutan alfabetis murni.
        System.out.println("first()     : " + peserta.first());
        System.out.println("last()      : " + peserta.last());
        System.out.println("ceiling(\"Alex\") : " + peserta.ceiling("Alex"));
    }
}