Struktur data sejauh ini berbentuk garis: elemen array berbaris, node linked list merantai maju. Padahal banyak data alaminya bercabang — direktori berisi folder yang berisi folder lagi, kategori produk bertingkat, ekspresi matematika yang tersusun dari sub-ekspresi. Tree (pohon) memodelkan hierarki dengan satu node akar dan setiap node bisa punya anak. Bentuk khususnya, Binary Search Tree (BST), menambahkan satu aturan yang membuat pohon sekaligus terurut: nilai di subtree kiri selalu lebih kecil dari akar, nilai di subtree kanan selalu lebih besar. Aturan sederhana tersebut menghasilkan pencarian secepat binary search plus kemampuan menjaga data tetap terurut selagi datang-datan.

Anatomi Pohon dan Aturan BST #

Node pada binary tree menyimpan dua tautan: kiri dan kanan, menggantikan next pada linked list. Istilah yang perlu dikenali: root (akar) adalah node paling atas; leaf (daun) adalah node tanpa anak; depth atau level mengukur jarak dari akar. BST menambahkan invariant: untuk setiap node, seluruh nilai di subtree kiri lebih kecil dan seluruh nilai di subtree kanan lebih besar dari nilai node tersebut. Invariant inilah yang memangkas separuh ruang pencarian pada setiap langkah — mesin yang sama dengan binary search pada array, hanya saja strukturnya tumbuh dinamis.

Implementasi BST Manual #

Kita bangun BST lengkap dengan tiga kemampuan inti: sisip, cari, dan penelusuran. Pencarian dilengkapi penghitung perbandingan supaya efisiensinya terlihat eksak:

java BstManual.java 
import java.util.Arrays;

public class BstManual {

    static class Node {
        int nilai;
        Node kiri;
        Node kanan;

        Node(int nilai) {
            this.nilai = nilai;
        }
    }

    private Node akar;

    // Penghitung perbandingan kunci saat pencarian.
    static long perbandingan;

    public static void main(String[] args) {
        int[] data = {50, 30, 70, 20, 40, 60, 80};
        BstManual bst = new BstManual();
        for (int nilai : data) {
            bst.sisip(nilai);
        }

        System.out.println("Sisip berurutan: " + Arrays.toString(data));
        System.out.println();
        System.out.println("Struktur pohon:");
        cetakStruktur(bst.akar, 0, "akar");

        System.out.println();
        System.out.println("inorder   : " + bacaTraversal(bst.akar, "inorder"));
        System.out.println("preorder  : " + bacaTraversal(bst.akar, "preorder"));
        System.out.println("postorder : " + bacaTraversal(bst.akar, "postorder"));

        System.out.println();
        perbandingan = 0;
        boolean ketemu = bst.cari(40);
        System.out.println("cari(40) -> " + ketemu + ", perbandingan: " + perbandingan);

        perbandingan = 0;
        ketemu = bst.cari(65);
        System.out.println("cari(65) -> " + ketemu + ", perbandingan: " + perbandingan);
    }

    void sisip(int nilai) {
        akar = sisipRekursif(akar, nilai);
    }

    private static Node sisipRekursif(Node node, int nilai) {
        if (node == null) {
            return new Node(nilai);        // titik kosong: tempat node baru
        }
        if (nilai < node.nilai) {
            node.kiri = sisipRekursif(node.kiri, nilai);
        } else if (nilai > node.nilai) {
            node.kanan = sisipRekursif(node.kanan, nilai);
        }
        // nilai sama: diabaikan, BST tidak menyimpan duplikat
        return node;
    }

    boolean cari(int nilai) {
        Node sekarang = akar;
        while (sekarang != null) {
            perbandingan++;
            if (nilai == sekarang.nilai) {
                return true;
            }
            if (nilai < sekarang.nilai) {
                sekarang = sekarang.kiri;
            } else {
                sekarang = sekarang.kanan;
            }
        }
        return false;
    }

    static void cetakStruktur(Node node, int indentasi, String posisi) {
        if (node == null) {
            return;
        }
        System.out.println("  ".repeat(indentasi) + posisi + ": " + node.nilai);
        cetakStruktur(node.kiri, indentasi + 1, "kiri");
        cetakStruktur(node.kanan, indentasi + 1, "kanan");
    }

    static String bacaTraversal(Node node, String jenis) {
        StringBuilder sb = new StringBuilder();
        traversal(node, jenis, sb);
        return sb.toString();
    }

    private static void traversal(Node node, String jenis, StringBuilder sb) {
        if (node == null) {
            return;
        }
        if (jenis.equals("preorder")) {
            sb.append(node.nilai).append(' ');
        }
        traversal(node.kiri, jenis, sb);
        if (jenis.equals("inorder")) {
            sb.append(node.nilai).append(' ');
        }
        traversal(node.kanan, jenis, sb);
        if (jenis.equals("postorder")) {
            sb.append(node.nilai).append(' ');
        }
    }
}

Output yang Dihasilkan:

text 
Sisip berurutan: [50, 30, 70, 20, 40, 60, 80]

Struktur pohon:
akar: 50
  kiri: 30
    kiri: 20
    kanan: 40
  kanan: 70
    kiri: 60
    kanan: 80

inorder   : 20 30 40 50 60 70 80 
preorder  : 50 30 20 40 70 60 80 
postorder : 20 40 30 60 80 70 50 

cari(40) -> true, perbandingan: 3
cari(65) -> false, perbandingan: 3

Perhatikan hasil inorder pada output: 20 30 40 50 60 70 80 — terurut naik walau data disisipkan dalam urutan acak. Mari kita bedah bagian-bagian intinya:

  1. Baris 57-71 (sisipRekursif): rekursi berjalan menuruni pohon mencari titik kosong. Saat node == null, node baru dibuat dan dikembalikan ke pemanggilnya untuk disambungkan — pola “kembalikan subtree yang sudah berubah” membuat satu method menangani akar maupun anak-anak tanpa kasus khusus. Nilai yang sama diabaikan supaya BST bebas duplikat.
  2. Baris 73-87 (cari): versi iteratif memakai satu penunjuk sekarang. Setiap perbandingan dengan node saat ini membuang separuh ruang: cari(40) menempuh jalur 50 → 30 → 40 dengan 3 perbandingan; cari(65) berhenti di subtree kosong dengan 3 perbandingan dan melaporkan tidak ditemukan.
  3. Baris 104-125 (traversal): satu kerangka rekursi dengan tiga titik cetak berbeda. Cetak sebelum rekursi menghasilkan preorder (akar lebih dulu), cetak di antara dua rekursi menghasilkan inorder (kiri-akar-kanan), cetak setelah keduanya menghasilkan postorder (akar paling akhir).

Tiga Cara Penelusuran #

Ketiga traversal pada output memuat angka yang sama dengan urutan berbeda, dan tiap urutan punya kegunaan. Preorder 50 30 20 40 70 60 80 mencatat akar sebelum anaknya — urutan ini cukup untuk membangun ulang pohon yang identik, berguna untuk serialisasi. Inorder menghasilkan data terurut — itulah alasan TreeMap di Java bisa berjalan seperti map sekaligus sorted list. Postorder 20 40 30 60 80 70 50 memproses anak sebelum akar — cocok untuk pekerjaan seperti menghitung ukuran folder setelah seluruh isinya terkumpul. Ketiganya mengunjungi setiap node tepat satu kali sehingga berbiaya O(n).

Kasus Terburuk Pohon Degenerate #

Janji BST adalah O(log n), tetapi janji itu bersyarat: pohon harus rendah. Bayangkan data yang datang sudah terurut — setiap nilai baru selalu lebih besar dari semua yang ada, sehingga rantai hanya tumbuh ke kanan. Program berikut membandingkan dua pohon dengan isi tujuh nilai yang sama persis, hanya berbeda urutan sisip:

java BstDegenerate.java 
public class BstDegenerate {

    static class Node {
        int nilai;
        Node kiri;
        Node kanan;

        Node(int nilai) {
            this.nilai = nilai;
        }
    }

    static long perbandingan;

    public static void main(String[] args) {
        // Pohon A: urutan sisip yang menempatkan nilai tengah lebih dulu.
        Node akarSeimbang = null;
        for (int v : new int[] {4, 2, 6, 1, 3, 5, 7}) {
            akarSeimbang = sisip(akarSeimbang, v);
        }

        // Pohon B: data yang sama namun sudah terurut naik.
        Node akarRantai = null;
        for (int v : new int[] {1, 2, 3, 4, 5, 6, 7}) {
            akarRantai = sisip(akarRantai, v);
        }

        System.out.println("=== Pohon A: sisip 4,2,6,1,3,5,7 ===");
        cetakStruktur(akarSeimbang, 0, "akar");
        System.out.println("Jumlah level: " + jumlahLevel(akarSeimbang));
        perbandingan = 0;
        cari(akarSeimbang, 7);
        System.out.println("cari(7) -> ditemukan, perbandingan: " + perbandingan);

        System.out.println();
        System.out.println("=== Pohon B: sisip 1,2,3,4,5,6,7 (data terurut) ===");
        cetakStruktur(akarRantai, 0, "akar");
        System.out.println("Jumlah level: " + jumlahLevel(akarRantai));
        perbandingan = 0;
        cari(akarRantai, 7);
        System.out.println("cari(7) -> ditemukan, perbandingan: " + perbandingan);
    }

    static Node sisip(Node node, int nilai) {
        if (node == null) {
            return new Node(nilai);
        }
        if (nilai < node.nilai) {
            node.kiri = sisip(node.kiri, nilai);
        } else if (nilai > node.nilai) {
            node.kanan = sisip(node.kanan, nilai);
        }
        return node;
    }

    static boolean cari(Node akar, int nilai) {
        Node sekarang = akar;
        while (sekarang != null) {
            perbandingan++;
            if (nilai == sekarang.nilai) {
                return true;
            }
            if (nilai < sekarang.nilai) {
                sekarang = sekarang.kiri;
            } else {
                sekarang = sekarang.kanan;
            }
        }
        return false;
    }

    static int jumlahLevel(Node node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(jumlahLevel(node.kiri), jumlahLevel(node.kanan));
    }

    static void cetakStruktur(Node node, int indentasi, String posisi) {
        if (node == null) {
            return;
        }
        System.out.println("  ".repeat(indentasi) + posisi + ": " + node.nilai);
        cetakStruktur(node.kiri, indentasi + 1, "kiri");
        cetakStruktur(node.kanan, indentasi + 1, "kanan");
    }
}

Output yang Dihasilkan:

text 
=== Pohon A: sisip 4,2,6,1,3,5,7 ===
akar: 4
  kiri: 2
    kiri: 1
    kanan: 3
  kanan: 6
    kiri: 5
    kanan: 7
Jumlah level: 3
cari(7) -> ditemukan, perbandingan: 3

=== Pohon B: sisip 1,2,3,4,5,6,7 (data terurut) ===
akar: 1
  kanan: 2
    kanan: 3
      kanan: 4
        kanan: 5
          kanan: 6
            kanan: 7
Jumlah level: 7
cari(7) -> ditemukan, perbandingan: 7

Pohon A selesai dalam 3 level dan menemukan nilai 7 dengan 3 perbandingan; pohon B terentang 7 level seperti linked list dan memerlukan 7 perbandingan. Kedua pohon memenuhi invariant BST, tetapi pohon B sudah kehilangan seluruh keunggulan logaritmiknya — pencarian di pohon degenerate adalah O(n). Dari sinilah muncul motivasi self-balancing tree: AVL tree dan Red-Black tree memutar atau mewarnai node setelah sisip agar tinggi pohon selalu O(log n). Kelas TreeMap dan TreeSet di Java memakai Red-Black tree, sehingga put, get, dan operasi rentangnya dijamin O(log n) dalam kasus terburuk sekalipun.

BST mengatur prioritas berdasarkan nilai dan menjaga semuanya terurut. Struktur berikutnya lebih longgar lagi: heap hanya menjamin satu hal — elemen terpenting selalu berada di puncak. Kelonggaran itu dibayar dengan operasi yang sangat cepat, dasar dari PriorityQueue.

Referensi #

Berkas Sumber

Berkas pendukung halaman ini dapat diunduh dan dijalankan langsung sesuai penjelasan di atas.

BstDegenerate.java

Unduh berkas
java 
public class BstDegenerate {

    static class Node {
        int nilai;
        Node kiri;
        Node kanan;

        Node(int nilai) {
            this.nilai = nilai;
        }
    }

    static long perbandingan;

    public static void main(String[] args) {
        // Pohon A: urutan sisip yang menempatkan nilai tengah lebih dulu.
        Node akarSeimbang = null;
        for (int v : new int[] {4, 2, 6, 1, 3, 5, 7}) {
            akarSeimbang = sisip(akarSeimbang, v);
        }

        // Pohon B: data yang sama namun sudah terurut naik.
        Node akarRantai = null;
        for (int v : new int[] {1, 2, 3, 4, 5, 6, 7}) {
            akarRantai = sisip(akarRantai, v);
        }

        System.out.println("=== Pohon A: sisip 4,2,6,1,3,5,7 ===");
        cetakStruktur(akarSeimbang, 0, "akar");
        System.out.println("Jumlah level: " + jumlahLevel(akarSeimbang));
        perbandingan = 0;
        cari(akarSeimbang, 7);
        System.out.println("cari(7) -> ditemukan, perbandingan: " + perbandingan);

        System.out.println();
        System.out.println("=== Pohon B: sisip 1,2,3,4,5,6,7 (data terurut) ===");
        cetakStruktur(akarRantai, 0, "akar");
        System.out.println("Jumlah level: " + jumlahLevel(akarRantai));
        perbandingan = 0;
        cari(akarRantai, 7);
        System.out.println("cari(7) -> ditemukan, perbandingan: " + perbandingan);
    }

    static Node sisip(Node node, int nilai) {
        if (node == null) {
            return new Node(nilai);
        }
        if (nilai < node.nilai) {
            node.kiri = sisip(node.kiri, nilai);
        } else if (nilai > node.nilai) {
            node.kanan = sisip(node.kanan, nilai);
        }
        return node;
    }

    static boolean cari(Node akar, int nilai) {
        Node sekarang = akar;
        while (sekarang != null) {
            perbandingan++;
            if (nilai == sekarang.nilai) {
                return true;
            }
            if (nilai < sekarang.nilai) {
                sekarang = sekarang.kiri;
            } else {
                sekarang = sekarang.kanan;
            }
        }
        return false;
    }

    static int jumlahLevel(Node node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(jumlahLevel(node.kiri), jumlahLevel(node.kanan));
    }

    static void cetakStruktur(Node node, int indentasi, String posisi) {
        if (node == null) {
            return;
        }
        System.out.println("  ".repeat(indentasi) + posisi + ": " + node.nilai);
        cetakStruktur(node.kiri, indentasi + 1, "kiri");
        cetakStruktur(node.kanan, indentasi + 1, "kanan");
    }
}

BstManual.java

Unduh berkas
java 
import java.util.Arrays;

public class BstManual {

    static class Node {
        int nilai;
        Node kiri;
        Node kanan;

        Node(int nilai) {
            this.nilai = nilai;
        }
    }

    private Node akar;

    // Penghitung perbandingan kunci saat pencarian.
    static long perbandingan;

    public static void main(String[] args) {
        int[] data = {50, 30, 70, 20, 40, 60, 80};
        BstManual bst = new BstManual();
        for (int nilai : data) {
            bst.sisip(nilai);
        }

        System.out.println("Sisip berurutan: " + Arrays.toString(data));
        System.out.println();
        System.out.println("Struktur pohon:");
        cetakStruktur(bst.akar, 0, "akar");

        System.out.println();
        System.out.println("inorder   : " + bacaTraversal(bst.akar, "inorder"));
        System.out.println("preorder  : " + bacaTraversal(bst.akar, "preorder"));
        System.out.println("postorder : " + bacaTraversal(bst.akar, "postorder"));

        System.out.println();
        perbandingan = 0;
        boolean ketemu = bst.cari(40);
        System.out.println("cari(40) -> " + ketemu + ", perbandingan: " + perbandingan);

        perbandingan = 0;
        ketemu = bst.cari(65);
        System.out.println("cari(65) -> " + ketemu + ", perbandingan: " + perbandingan);
    }

    void sisip(int nilai) {
        akar = sisipRekursif(akar, nilai);
    }

    private static Node sisipRekursif(Node node, int nilai) {
        if (node == null) {
            return new Node(nilai);        // titik kosong: tempat node baru
        }
        if (nilai < node.nilai) {
            node.kiri = sisipRekursif(node.kiri, nilai);
        } else if (nilai > node.nilai) {
            node.kanan = sisipRekursif(node.kanan, nilai);
        }
        // nilai sama: diabaikan, BST tidak menyimpan duplikat
        return node;
    }

    boolean cari(int nilai) {
        Node sekarang = akar;
        while (sekarang != null) {
            perbandingan++;
            if (nilai == sekarang.nilai) {
                return true;
            }
            if (nilai < sekarang.nilai) {
                sekarang = sekarang.kiri;
            } else {
                sekarang = sekarang.kanan;
            }
        }
        return false;
    }

    static void cetakStruktur(Node node, int indentasi, String posisi) {
        if (node == null) {
            return;
        }
        System.out.println("  ".repeat(indentasi) + posisi + ": " + node.nilai);
        cetakStruktur(node.kiri, indentasi + 1, "kiri");
        cetakStruktur(node.kanan, indentasi + 1, "kanan");
    }

    static String bacaTraversal(Node node, String jenis) {
        StringBuilder sb = new StringBuilder();
        traversal(node, jenis, sb);
        return sb.toString();
    }

    private static void traversal(Node node, String jenis, StringBuilder sb) {
        if (node == null) {
            return;
        }
        if (jenis.equals("preorder")) {
            sb.append(node.nilai).append(' ');
        }
        traversal(node.kiri, jenis, sb);
        if (jenis.equals("inorder")) {
            sb.append(node.nilai).append(' ');
        }
        traversal(node.kanan, jenis, sb);
        if (jenis.equals("postorder")) {
            sb.append(node.nilai).append(' ');
        }
    }
}