Mengenal BST: Pengertian, Fungsi, dan Cara Kerjanya Biar Gak Bingung!

Table of Contents

Pernahkah Anda membayangkan bagaimana data bisa diorganisir sedemikian rupa sehingga mencari, menambah, atau menghapus informasi di dalamnya bisa dilakukan dengan cepat? Di dunia ilmu komputer, ada banyak cara untuk melakukan ini, dan salah satu yang paling fundamental dan penting adalah menggunakan struktur data yang disebut Pohon Pencarian Biner, atau dalam bahasa Inggris, Binary Search Tree (BST).

BST adalah jenis struktur data pohon (tree data structure) yang diatur secara khusus. Tujuannya adalah untuk menjaga data dalam urutan tertentu sehingga operasi seperti pencarian menjadi sangat efisien. Bayangkan seperti cara Anda mencari kata di kamus atau buku telepon; data diurutkan agar Anda bisa melompat-lompat dan menemukan apa yang dicari dengan cepat, bukan memeriksa satu per satu dari awal.

Memahami Struktur Data Pohon (Tree)¶

Sebelum masuk ke BST, mari kita pahami dulu apa itu struktur data pohon secara umum. Struktur data pohon adalah kumpulan node (simpul) yang dihubungkan oleh edge (garis/cabang). Ada satu node paling atas yang disebut “akar” (root). Setiap node bisa memiliki “anak” (children), dan node yang ada di atasnya disebut “induk” (parent). Node yang tidak memiliki anak disebut “daun” (leaf).

Image just for illustration

Struktur pohon ini bersifat hierarkis, mirip dengan silsilah keluarga atau struktur organisasi perusahaan. Data disimpan di dalam setiap node, dan hubungan antar node menunjukkan bagaimana data-data tersebut saling terkait atau diorganisir.

Mengenal Pohon Biner (Binary Tree)¶

Pohon biner adalah kasus khusus dari struktur data pohon. Definisi paling mendasarnya adalah bahwa setiap node dalam pohon biner memiliki paling banyak dua anak. Anak-anak ini biasanya disebut sebagai “anak kiri” (left child) dan “anak kanan” (right child).

Tidak ada aturan pengurutan khusus dalam pohon biner biasa; anak kiri bisa lebih besar atau lebih kecil dari induknya, begitu juga anak kanan. Yang penting hanya batasan jumlah anaknya saja, yaitu maksimal dua.

Image just for illustration

Pohon biner ini menjadi dasar bagi banyak struktur data lain yang lebih kompleks, termasuk BST. Pembatasan jumlah anak menjadi dua ini yang memungkinkan kita menerapkan aturan pengurutan yang efisien.

Apa Itu Binary Search Tree (BST)?¶

Nah, inilah intinya. Binary Search Tree (BST) adalah jenis pohon biner yang mengikuti aturan pengurutan tertentu pada nilai-nilai yang disimpan di setiap node. Aturan emas BST adalah:

1. Semua nilai di anak kiri (dan seluruh sub-pohon kirinya) harus lebih kecil dari nilai di node induk saat ini.
2. Semua nilai di anak kanan (dan seluruh sub-pohon kanannya) harus lebih besar dari nilai di node induk saat ini.
3. Aturan 1 dan 2 berlaku secara rekursif untuk setiap sub-pohon yang ada.

Image just for illustration

Aturan sederhana ini menciptakan struktur yang sangat efisien untuk operasi pencarian. Karena data terurut, kita bisa dengan cepat memutuskan apakah harus mencari ke sub-pohon kiri atau sub-pohon kanan, membuang separuh data potensial di setiap langkah. Ini mirip dengan cara kerja algoritma binary search pada array yang terurut.

Properti Penting BST¶

Memahami properti BST akan membantu kita melihat mengapa struktur ini begitu berguna:

• Data Terurut: Nilai dalam BST selalu diorganisir sedemikian rupa sehingga penelusuran (traversal) tertentu (seperti in-order traversal) akan menghasilkan data yang terurut dari nilai terkecil ke terbesar.
• Efisiensi Pencarian (Rata-rata): Berkat aturan pengurutan, mencari data dalam BST ideal (yang seimbang) memerlukan waktu logaritmik terhadap jumlah data (O(log n)), jauh lebih cepat daripada mencari di daftar yang tidak terurut (O(n)).
• Sub-pohon Kiri/Kanan: Setiap node dalam BST adalah akar dari sub-pohon kirinya sendiri dan sub-pohon kanannya sendiri. Sub-pohon kiri berisi semua nilai yang lebih kecil dari node tersebut, dan sub-pohon kanan berisi semua nilai yang lebih besar.

Properti ini membuat BST menjadi pilihan yang sangat baik ketika Anda perlu menyimpan data yang dapat dibandingkan (seperti angka, string, atau objek dengan kunci yang dapat dibandingkan) dan sering melakukan operasi pencarian, penambahan, atau penghapusan.

Bagaimana Cara Kerja BST?¶

Mari kita lihat lebih detail bagaimana operasi dasar dilakukan pada BST. Ini adalah inti dari kegunaan struktur data ini.

Mencari Data (Search)¶

Mencari nilai tertentu di BST adalah proses yang sangat intuitif dan cepat.

1. Mulai dari node akar (root).
2. Bandingkan nilai yang Anda cari dengan nilai di node saat ini.
3. Jika nilai yang dicari sama dengan nilai node saat ini, data ditemukan! Proses selesai.
4. Jika nilai yang dicari lebih kecil dari nilai node saat ini, pindah ke anak kiri. Jika anak kiri tidak ada (null), berarti data tidak ditemukan dalam pohon.
5. Jika nilai yang dicari lebih besar dari nilai node saat ini, pindah ke anak kanan. Jika anak kanan tidak ada (null), berarti data tidak ditemukan dalam pohon.
6. Ulangi langkah 2-5 pada node yang baru sampai data ditemukan atau mencapai node null.

Image just for illustration

Proses ini mirip dengan binary search pada array terurut. Di setiap langkah, kita mengabaikan separuh dari pohon yang tidak mungkin mengandung nilai yang dicari, sehingga mempercepat pencarian secara signifikan (pada pohon yang seimbang).

Menambah Data (Insertion)¶

Menambah node baru ke dalam BST juga mengikuti aturan pengurutan. Tujuannya adalah menemukan lokasi yang tepat di mana node baru harus menjadi “daun” (leaf) baru tanpa melanggar aturan BST.

1. Mulai dari node akar.
2. Bandingkan nilai yang akan ditambahkan dengan nilai di node saat ini.
3. Jika nilai yang akan ditambahkan lebih kecil, pindah ke anak kiri.
4. Jika nilai yang akan ditambahkan lebih besar, pindah ke anak kanan. (Beberapa implementasi tidak mengizinkan nilai duplikat; jika diizinkan, biasanya nilai yang sama ditempatkan di sebelah kanan atau ada cara penanganan khusus).
5. Ulangi langkah 2-4 sampai Anda mencapai node null. Ini berarti Anda telah menemukan lokasi yang tepat untuk node baru.
6. Buat node baru dengan nilai yang akan ditambahkan dan letakkan sebagai anak kiri atau kanan dari node parent terakhir yang Anda kunjungi (tergantung perbandingan terakhir).

Image just for illustration

Sama seperti pencarian, proses ini juga efisien (O(log n) rata-rata) karena kita hanya perlu menelusuri jalur tunggal dari akar ke lokasi penyisipan.

Menghapus Data (Deletion)¶

Menghapus node dari BST adalah operasi yang paling kompleks karena ada beberapa kasus yang perlu ditangani untuk memastikan aturan BST tetap berlaku setelah penghapusan.

Ada tiga kasus utama saat menghapus node:

1. Node yang Dihapus Adalah Daun (Tidak Punya Anak): Kasus paling mudah. Cukup hapus node tersebut dan setel pointer dari induknya ke null.

2. Node yang Dihapus Memiliki Satu Anak: Hapus node tersebut dan ganti posisinya dengan satu-satunya anaknya. Sambungkan anak tersebut langsung ke induk dari node yang dihapus.

3. Node yang Dihapus Memiliki Dua Anak: Ini kasus paling rumit. Anda tidak bisa begitu saja menghapus node tersebut karena ada dua sub-pohon yang harus tetap terhubung ke struktur. Solusinya adalah mengganti nilai node yang akan dihapus dengan nilai dari node lain yang memastikan aturan BST tidak terganggu. Dua pilihan umum untuk pengganti ini adalah:

   • In-order Successor: Node terkecil di sub-pohon kanan dari node yang akan dihapus. Node ini pasti tidak memiliki anak kiri (kalau punya, itu akan menjadi successor yang lebih kecil).
   • In-order Predecessor: Node terbesar di sub-pohon kiri dari node yang akan dihapus. Node ini pasti tidak memiliki anak kanan.

   Cara kerjanya (menggunakan in-order successor): Temukan in-order successor dari node yang akan dihapus. Salin nilai successor tersebut ke node yang akan dihapus. Kemudian, hapus node successor dari lokasi aslinya. Karena successor pasti tidak memiliki anak kiri, penghapusan successor ini akan masuk ke Kasus 1 atau Kasus 2 (jika successor punya anak kanan). Dengan demikian, struktur BST tetap terjaga.

Image just for illustration

Operasi penghapusan juga rata-rata membutuhkan waktu O(log n), karena menemukan node yang akan dihapus dan mencari successor/predecessor memerlukan penelusuran jalur di pohon.

Keunggulan Menggunakan BST¶

Mengapa orang menggunakan BST? Beberapa keunggulannya antara lain:

• Performa Operasi Cepat (Rata-rata): Seperti yang sudah dibahas, pencarian, penyisipan, dan penghapusan memiliki kompleksitas waktu O(log n) pada pohon yang seimbang. Ini sangat efisien untuk jumlah data yang besar.
• Penyimpanan Data Terurut: Struktur BST secara inheren menyimpan data dalam urutan terurut. Ini memudahkan operasi seperti menemukan nilai minimum (node paling kiri) atau maksimum (node paling kanan), atau melakukan traversal yang menghasilkan data terurut (in-order traversal).
• Fleksibel: Ukuran BST bisa berubah secara dinamis (mengembang atau menyusut) saat node ditambahkan atau dihapus, tidak seperti array statis.

Keunggulan performa O(log n) ini yang membuat BST dan variannya menjadi pilihan utama dalam banyak aplikasi yang membutuhkan pencarian data cepat pada koleksi yang sering berubah.

Kekurangan BST: Masalah Pohon Tidak Seimbang (Skewed Tree)¶

Meskipun memiliki keunggulan, BST standar memiliki satu kekurangan kritis: performa O(log n) hanya terjamin jika pohonnya seimbang atau mendekati seimbang.

Apa yang terjadi jika pohon tidak seimbang? Bayangkan Anda memasukkan data ke dalam BST secara berurutan, misalnya angka 1, 2, 3, 4, 5, 6. Setiap angka baru akan selalu lebih besar dari akar dan semua node yang sudah ada, sehingga selalu menjadi anak kanan. Hasilnya adalah pohon yang hanya memiliki anak kanan, terlihat seperti daftar tertaut (linked list) miring ke kanan.

Image just for illustration

Dalam pohon yang tidak seimbang ini, mencari node terjauh (misalnya 6) akan memerlukan penelusuran semua node dari akar (1 -> 2 -> 3 -> 4 -> 5 -> 6). Ini sama buruknya dengan mencari di daftar yang tidak terurut, alias performanya merosot menjadi O(n)!

Situasi “pohon miring” (skewed tree) ini adalah kelemahan utama BST standar. Jika data dimasukkan atau dihapus dengan pola tertentu yang menciptakan ketidakseimbangan ekstrem, semua keuntungan performa O(log n) bisa hilang.

Solusi Kekurangan: Pohon Pencarian Biner yang Seimbang (Balanced BST)¶

Untuk mengatasi masalah ketidakseimbangan pada BST standar, dikembangkanlah varian-varian BST yang secara otomatis “menyeimbangkan” dirinya sendiri setiap kali ada penambahan atau penghapusan node. Pohon-pohon ini dikenal sebagai Balanced Binary Search Tree (BST yang Seimbang).

Contoh BST yang seimbang yang paling terkenal adalah:

• AVL Trees: Pohon ini menjaga keseimbangan dengan memastikan perbedaan tinggi (jumlah level) antara sub-pohon kiri dan kanan untuk setiap node tidak pernah lebih dari 1. Jika perbedaan melebihi itu, pohon akan melakukan “rotasi” untuk menyeimbangkan kembali.
• Red-Black Trees: Pohon ini menggunakan “warna” (merah atau hitam) pada node dan mengikuti aturan ketat terkait warna dan jumlah node hitam pada setiap jalur untuk memastikan pohon tetap relatif seimbang.

Image just for illustration

Balanced BSTs menjamin bahwa performa pencarian, penambahan, dan penghapusan akan tetap O(log n) bahkan dalam kasus terburuk sekalipun, karena pohon tidak akan pernah menjadi terlalu miring. Implementasi struktur data “Set” dan “Map” di banyak standard library bahasa pemrograman (seperti std::set dan std::map di C++, atau TreeMap di Java) seringkali menggunakan Balanced BSTs (terutama Red-Black Trees) di baliknya.

Penggunaan BST dalam Praktik¶

Meskipun BST standar jarang digunakan sendiri dalam aplikasi mission-critical karena masalah ketidakseimbangan, konsepnya sangat fundamental dan Balanced BSTs banyak digunakan. Beberapa contoh aplikasinya meliputi:

• Implementasi Set dan Map/Dictionary: Struktur data ini yang menyimpan koleksi elemen unik (Set) atau pasangan kunci-nilai (Map) sering diimplementasikan menggunakan Balanced BSTs untuk performa O(log n) pada operasi kuncinya.
• Indeks Database: Struktur data pohon, termasuk varian B-tree (yang terkait tetapi berbeda dari BST biner), digunakan secara luas dalam sistem database untuk mengindeks data, memungkinkan pencarian dan pengambilan data yang sangat cepat.
• Compiler: BST atau struktur pohon terkait digunakan dalam compiler untuk membangun “symbol table” yang menyimpan informasi tentang variabel dan fungsi dalam kode program, atau untuk merepresentasikan struktur sintaks kode (Abstract Syntax Tree).
• Geographic Information Systems (GIS): Struktur data berbasis pohon terkadang digunakan untuk menyimpan dan mengorganisir data spasial.

Memahami BST adalah langkah penting untuk bisa memahami struktur data berbasis pohon yang lebih canggih dan aplikasi-aplikasinya yang luas.

Perbandingan Singkat dengan Struktur Data Lain¶

Bagaimana BST dibandingkan dengan struktur data lain yang juga menyimpan koleksi data?

• Array / Linked List: Pencarian, penambahan, atau penghapusan data di tengah atau awal/akhir bisa memakan waktu O(n) dalam kasus terburuk atau rata-rata. BST menawarkan O(log n) rata-rata (atau O(log n) jaminan untuk Balanced BST), jauh lebih cepat untuk operasi-operasi ini pada data yang banyak. Namun, akses langsung ke elemen berdasarkan indeks (seperti di array) tidak efisien di BST.
• Hash Table: Hash table menawarkan performa O(1) rata-rata untuk pencarian, penambahan, dan penghapusan. Ini lebih cepat dari BST. Namun, hash table tidak menyimpan data dalam urutan terurut, dan performa kasus terburuknya bisa O(n) jika terjadi banyak collision. BST sangat baik jika Anda membutuhkan data yang terurut dan performa O(log n) yang konsisten (dengan Balanced BST).

Setiap struktur data memiliki kelebihan dan kekurangan, dan pilihan tergantung pada kebutuhan spesifik aplikasi (misalnya, seberapa sering operasi tertentu dilakukan, apakah data perlu terurut, apakah ada batasan memori).

Tips untuk Memahami BST¶

Belajar BST mungkin terasa agak menantang pada awalnya, terutama bagian penghapusan. Berikut beberapa tips untuk mempermudah pemahaman:

• Gambar Diagram: Selalu gambar pohonnya! Gambarkan node-node dan edge-edgenya saat Anda mencoba memahami bagaimana data dimasukkan atau dihapus.
• Lakukan Penelusuran Manual: Ambil urutan angka (misal: 8, 3, 10, 1, 6, 14, 4, 7, 13) dan gambar langkah demi langkah bagaimana BST dibangun saat Anda memasukkan angka-angka tersebut satu per satu.
• Simulasikan Operasi: Setelah pohon terbentuk, coba simulasikan operasi pencarian (misal, cari 7), penambahan (misal, tambah 9), dan penghapusan (coba hapus daun seperti 1, hapus node dengan satu anak seperti 10, dan hapus node dengan dua anak seperti 8). Fokus pada kasus penghapusan dua anak dan temukan successor/predecessor-nya.
• Pahami Aturan Emas: Ingat selalu: kiri < induk < kanan. Aturan ini adalah kunci dari segalanya.

Dengan latihan menggambar dan mensimulasikan secara manual, konsep BST akan menjadi jauh lebih jelas dan intuitif.

Fakta Menarik: Hubungan dengan Binary Search Algorithm¶

Nama “Binary Search Tree” bukan kebetulan mirip dengan algoritma “Binary Search” pada array terurut. Keduanya bekerja berdasarkan prinsip yang sama: membagi ruang pencarian menjadi dua bagian di setiap langkah.

Pada array terurut, kita membandingkan elemen target dengan elemen di tengah array, lalu memutuskan untuk mencari di separuh kiri atau separuh kanan. Pada BST, kita membandingkan elemen target dengan nilai node saat ini, lalu memutuskan untuk mencari di sub-pohon kiri atau sub-pohon kanan. Konsep inti untuk mencapai performa O(log n) pada data terurut adalah sama.

Kesimpulan¶

Binary Search Tree (BST) adalah struktur data pohon fundamental yang mengatur elemen-elemennya dalam urutan tertentu (kiri < induk < kanan). Struktur ini memungkinkan operasi pencarian, penambahan, dan penghapusan data dengan efisien (rata-rata O(log n)).

Meskipun BST standar rentan terhadap masalah ketidakseimbangan yang dapat menurunkan performa menjadi O(n) dalam kasus terburuk, konsepnya menjadi dasar bagi Balanced BSTs (seperti AVL dan Red-Black Trees) yang secara otomatis menjaga keseimbangan dan menjamin performa O(log n) yang konsisten. Memahami BST adalah langkah penting dalam mempelajari struktur data yang lebih canggih dan aplikasi di berbagai bidang komputasi.

Punya pertanyaan tentang BST atau pengalaman menggunakannya? Yuk, diskusi di kolom komentar di bawah!