Apa itu Pohon Pencarian Biner?

Pohon Pencarian Biner adalah salah satu dari berbagai struktur data yang membantu kami mengatur dan mengurutkan data. Ini adalah cara yang efisien untuk menyimpan data dalam hierarki dan sangat fleksibel.

Dalam artikel ini, kita akan melihat lebih dekat cara kerjanya—bersama dengan properti dan aplikasinya.

Apa itu Pohon Pencarian Biner?

Pohon Pencarian Biner adalah struktur data yang terdiri dari simpul—mirip dengan Daftar Tertaut. Ada dua jenis node: parent dan child. Simpul akar adalah titik awal dari struktur yang bercabang menjadi dua simpul anak, yang disebut simpul kiri dan simpul kanan.

Setiap node hanya dapat direferensikan oleh induknya, dan kita dapat melintasi node pohon tergantung pada arahnya. Pohon Pencarian Biner memiliki tiga properti utama:

1. Node kiri lebih kecil dari induknya.
2. Simpul kanan lebih besar dari induknya.
3. Subpohon kiri dan kanan harus berupa Pohon Pencarian Biner.

Pohon Pencarian Biner Sempurna tercapai ketika semua level terisi, dan setiap simpul memiliki simpul anak kiri dan kanan.

Terkait: Perpustakaan Ilmu Data untuk Python Setiap Ilmuwan Data Harus Menggunakan

Operasi Dasar Pohon Pencarian Biner

Sekarang Anda memiliki gagasan yang lebih baik tentang apa itu Pohon Pencarian Biner, kita dapat melihat operasi dasarnya di bawah ini.

1. Operasi Pencarian

Pencarian memungkinkan kita untuk menemukan nilai tertentu yang ada di pohon. Kita dapat menggunakan dua jenis pencarian: pencarian luas-pertama (BFS) dan pencarian mendalam-pertama (DFS). Breadth-first search adalah algoritma pencarian yang dimulai dari simpul akar dan melintasi secara horizontal, sisi ke sisi, sampai tujuannya ditemukan. Setiap node dikunjungi sekali selama pencarian ini.

Pencarian mendalam-pertama, di sisi lain, melintasi pohon secara vertikal — mulai dari simpul akar dan bekerja ke bawah satu cabang. Jika tujuan ditemukan, operasi berakhir. Tetapi jika tidak, itu dan mencari node lain.

2. Operasi Sisipkan

Operasi insert menggunakan operasi pencarian untuk menentukan lokasi dimana node baru harus disisipkan. Proses dimulai dari node root, dan pencarian dimulai sampai tujuan tercapai. Ada tiga kasus yang perlu dipertimbangkan dengan penyisipan.

• Kasus 1: Ketika tidak ada node. Node yang akan disisipkan akan menjadi root node.

• Kasus 2: Tidak ada anak. Dalam hal ini, simpul tersebut akan dibandingkan dengan simpul akar. Jika lebih besar, itu akan menjadi anak yang tepat; jika tidak, itu akan menjadi anak kiri.

• Kasus 3: Ketika root dan anak-anaknya ada. Node baru akan dibandingkan dengan setiap node di jalurnya untuk menentukan node mana yang dikunjungi selanjutnya. Jika simpul lebih besar dari simpul akar, ia akan melintasi sub-pohon kanan atau kiri. Demikian pula, perbandingan dilakukan pada setiap tingkat untuk menentukan apakah akan ke kanan atau ke kiri sampai tiba di tujuannya.

3. Hapus Operasi

Operasi hapus digunakan untuk menghapus node tertentu di dalam pohon. Penghapusan dianggap rumit karena setelah menghapus simpul, pohon harus diatur ulang sesuai dengan itu. Ada tiga kasus utama yang perlu dipertimbangkan:

• Kasus 1: Menghapus simpul daun. Simpul daun adalah simpul tanpa anak. Ini adalah yang paling mudah untuk dihapus karena tidak mempengaruhi node lain; kita cukup melintasi pohon sampai kita mencapainya dan menghapusnya.

• Kasus 2: Menghapus node dengan satu anak. Menghapus orang tua dengan satu simpul akan mengakibatkan anak mengambil posisinya, dan semua simpul berikutnya akan naik satu tingkat. Tidak akan ada perubahan dalam struktur sub-pohon.

• Kasus 3: Menghapus node dengan dua anak. Ketika kita harus menghapus sebuah node dengan dua anak, pertama-tama kita harus menemukan node berikutnya yang dapat mengambil posisinya. Dua node dapat menggantikan node yang dihapus, penerus inorder atau pendahulunya. Penerus inorder adalah anak paling kiri dari subpohon kanan, dan pendahulunya adalah anak paling kanan dari subpohon kiri. Kami menyalin konten penerus/pendahulu ke node dan menghapus penerus/pendahulu dalam urutan.

Terkait: Cara Membangun Struktur Data Dengan Kelas JavaScript ES6

Cara Melintasi Pohon Pencarian Biner

Traversal adalah proses di mana kita menavigasi Pohon Pencarian Biner. Hal ini dilakukan untuk menemukan item tertentu atau untuk mencetak garis besar pohon. Kami selalu mulai dari simpul akar dan harus mengikuti ujungnya untuk sampai ke simpul lain. Setiap node harus dianggap sebagai sub-pohon, dan proses ini diulang sampai semua node dikunjungi.

• Lintasan Berurutan: Melintasi secara berurutan akan menghasilkan peta dalam urutan menaik. Dengan metode ini, kita mulai dari subtree kiri dan melanjutkan ke root dan subtree kanan.

• Lintasan Pra-Pesanan: Dalam metode ini, simpul akar dikunjungi terlebih dahulu, diikuti oleh subpohon kiri dan subpohon kanan.

• Lintasan Pasca-Pesanan: Traversal ini melibatkan mengunjungi node root terakhir. Kita mulai dari subpohon kiri, kemudian subpohon kanan, dan kemudian simpul akar.

Aplikasi Dunia Nyata

Jadi, bagaimana kita menggunakan algoritma pohon pencarian biner? Seperti yang dapat diduga, mereka sangat efisien dalam mencari dan menyortir. Kekuatan terbesar dari pohon biner adalah strukturnya yang terorganisir. Hal ini memungkinkan pencarian dilakukan pada kecepatan yang luar biasa dengan memotong jumlah data yang kita perlukan untuk menganalisis setengahnya per lintasan.

Pohon Pencarian Biner memungkinkan kami untuk secara efisien memelihara kumpulan data yang berubah secara dinamis dalam bentuk yang terorganisir. Untuk aplikasi yang datanya sering dimasukkan dan dihapus, ini sangat membantu. Mesin video game menggunakan algoritme berdasarkan pohon yang dikenal sebagai partisi ruang biner untuk membantu merender objek secara teratur. Microsoft Excel dan sebagian besar perangkat lunak spreadsheet menggunakan pohon biner sebagai struktur data dasarnya.

Anda mungkin terkejut mengetahui bahwa kode Morse menggunakan pohon pencarian biner untuk mengkodekan data. Alasan menonjol lainnya Pohon Pencarian Biner sangat berguna adalah banyak variasinya. Fleksibilitas mereka telah menyebabkan banyak varian diciptakan untuk menyelesaikan segala macam masalah. Bila digunakan dengan benar, Pohon Pencarian Biner adalah aset yang bagus.

Pohon Pencarian Biner: Titik Awal yang Sempurna

Salah satu cara utama untuk mengukur keahlian seorang insinyur adalah melalui pengetahuan dan penerapan struktur data mereka. Struktur data sangat membantu dan dapat membantu menciptakan sistem yang lebih efisien. Pohon Pencarian Biner adalah pengantar yang bagus untuk struktur data untuk setiap pengembang yang memulai.

15 Metode Array JavaScript yang Harus Anda Kuasai Hari Ini

Ingin memahami array JavaScript tetapi tidak dapat memahaminya? Lihat contoh larik JavaScript kami untuk panduan.

Baca Selanjutnya

Tentang Penulis