Pohon Biner vs Pohon Pencarian Biner: Perbedaan Antara Pohon Biner dan Pohon Pencarian Biner

pengantar

Sortasi adalah proses menyusun data dalam urutan yang sistematis sehingga dapat dianalisis lebih efektif. Proses mengidentifikasi record tertentu disebut searching. Jika data diurutkan dengan benar dalam urutan tertentu, maka pencarian menjadi tugas yang mudah dan efisien. Artikel ini membahas salah satu struktur data non-linier yang paling penting, yaitu pohon.

Pohon terutama digunakan untuk mewakili data dengan menunjukkan hubungan hierarkis antara elemen. Misalnya, daftar isi, silsilah keluarga. Secara teknis, sebuah pohon dapat didefinisikan sebagai himpunan hingga 'T' dari satu atau lebih node sedemikian rupa sehingga sebuah node ditetapkan sebagai akar dari pohon dan node lainnya dibagi menjadi n>=0 himpunan terputus T1, T2, T3, T4 …. Tn dan disebut sebagai subpohon atau anak dari simpul akar tersebut.

Apa itu Pohon Biner?

Pohon biner adalah struktur data non-linear di mana sebuah node dapat memiliki 0, 1 atau 2 node. Setiap simpul dalam pohon biner disebut sebagai simpul induk atau sebagai simpul anak. Node paling atas dari Binary Tree disebut sebagai root node. Setiap simpul induk dapat memiliki paling banyak 2 simpul anak yaitu simpul anak kiri dan simpul anak kanan.

Sebuah node dalam pohon biner memiliki tiga bidang:

1. Elemen Data – Ini menyimpan nilai data yang akan disimpan oleh node.
2. Pointer to the left child – Ini menyimpan referensi (atau alamat) ke node anak kiri.
3. Pointer ke anak kanan – Ini menyimpan referensi ke node anak kanan.

Dengan cara ini, beberapa node digabungkan bersama untuk membangun Pohon Biner.

Sebuah Pohon Biner dapat direpresentasikan sebagai:

Sumber

Dari gambar di atas, simpul akar 2 memiliki dua anak (atau simpul anak), 7 dan 5. 7 disebut sebagai simpul anak kiri dan 5 disebut sebagai simpul anak kanan. Dengan cara ini, masing-masing node anak bertindak sebagai node induk ke beberapa node lain dan bersama-sama mewakili Pohon Biner.

Lihat: Jenis Pohon Biner

Terminologi yang digunakan dalam Binary Tree

Node : Representasi dasar dari titik terminasi di pohon.

Root Node : Node paling atas dari Binary Tree.

Parent Node : Jika sebuah node terhubung ke node lain melalui edge, itu dikenal sebagai parent node. Dalam pohon biner, simpul induk dapat memiliki maksimal 2 simpul anak.

Child Node : Jika sebuah node memiliki pendahulunya, itu dikenal sebagai child node.

Leaf Node : Sebuah node yang tidak memiliki child node disebut sebagai leaf node.

Kedalaman sebuah simpul : Ini adalah jarak dari simpul akar ke simpul tertentu yang kedalamannya akan diukur.

Tinggi pohon : Merupakan jarak terjauh dari simpul akar ke simpul daun.

Ini adalah beberapa terminologi dasar dari Pohon Biner. Dengan pemahaman dasar tentang Pohon Biner ini, mari kita beralih ke kemajuan Pohon Biner yang dikenal sebagai Pohon Pencarian Biner.

Baca Juga: Algoritma Pencarian Biner: Fungsi, Manfaat, Kompleksitas Waktu & Ruang

Apa itu Pohon Pencarian Biner

Seperti namanya, Binary Search Tree atau BST adalah pohon yang digunakan dalam menyortir, mengambil dan mencari data. Ini juga merupakan jenis struktur data non-linear di mana node diatur dalam urutan tertentu. Oleh karena itu, ia juga disebut sebagai " Pohon Biner Terurut ". Ini memiliki sifat-sifat berikut:

• Subpohon kiri dari sebuah simpul memiliki simpul yang hanya lebih kecil dari kunci simpul tersebut.
• Subpohon kanan dari sebuah simpul memiliki simpul yang hanya lebih besar dari kunci simpul tersebut.
• Setiap node memiliki kunci yang berbeda dan duplikat tidak diperbolehkan di Binary Search Tree.
• Subpohon kiri dan kanan juga harus berupa pohon pencarian biner.

Mari kita memvisualisasikan konsep ini untuk mendapatkan pemahaman yang jelas tentang Pohon Pencarian Biner.

Sumber

Pada gambar di atas, kita melihat bahwa nilai simpul akar adalah 8. Dengan pengamatan lebih lanjut, terlihat bahwa semua nilai pada subpohon kiri lebih kecil dari nilai simpul akar dan semua nilai pada subpohon kanan memiliki nilai yang lebih besar dari simpul akar. Selanjutnya, dicatat bahwa setiap nilai dalam Pohon Pencarian Biner adalah unik dan tidak ada duplikat. Dengan demikian, sifat-sifat Pohon Pencarian Biner yang disebutkan di atas diverifikasi.

Dalam contoh lain, kita melihat bahwa meskipun subpohon kiri dan kanan adalah pohon pencarian biner dengan nilai unik di seluruh pohon. Nilai pada simpul daun di subpohon kiri adalah 12 yang lebih besar dari nilai simpul akar yaitu 12. Dengan demikian, ini tidak memenuhi properti BST dan karenanya, ini bukan Pohon Pencarian Biner.

Operasi pencarian di BST –

Pertimbangkan Pohon Pencarian Biner dengan nilai yang diberikan di bawah ini. Mari kita pahami bagaimana operasi pencarian dilakukan untuk mendapatkan 9 dari Pohon Pencarian Biner.

Sumber

Untuk melakukan pencarian biner, pertama-tama kita akan mengatur semua bilangan bulat dalam array yang diurutkan. Ini disebut sebagai ruang pencarian. Ruang pencarian ini harus terdiri dari dua penunjuk, yang disebut penunjuk awal dan penunjuk akhir. Array dari Pohon Pencarian Biner yang diberikan di atas direpresentasikan sebagai:

Langkah pertama adalah menghitung nilai tengah array dan membandingkannya dengan nilai yang akan dicari, 9 dalam kasus kita. Hal ini dilakukan dengan menghitung n/2, di mana n adalah jumlah total elemen dalam array (BST) dan itu adalah 6. Jadi, elemen ke-3 adalah elemen tengah yaitu 5.

Sekarang elemen tengah dibandingkan dengan 9 dan karena tidak sama (lebih besar), operasi pencarian akan dilakukan pada larik kanan. Dengan cara ini, operasi pencarian dikurangi menjadi setengahnya, seperti yang ditunjukkan di bawah ini:

Pada langkah berikutnya, elemen tengah dihitung dan ditemukan menjadi 9, yang cocok dengan elemen kita yang akan dicari.

Pohon Biner vs Pohon Pencarian Biner –

Sekarang setelah kita memiliki pemahaman dasar tentang Pohon Biner dan Pohon Pencarian Biner, mari kita rangkum beberapa perbedaan di antara keduanya.

Kesimpulan

Jadi, kami menyimpulkan bahwa meskipun Pohon Biner dan Pohon Pencarian Biner memiliki struktur hierarki yang sama dengan kumpulan node, mereka memiliki beberapa perbedaan dalam aplikasinya. Pohon Biner adalah struktur dasar dengan aturan sederhana bahwa tidak ada orang tua yang harus memiliki lebih dari 2 anak sedangkan Pohon Pencarian Biner adalah varian dari pohon biner yang mengikuti urutan tertentu di mana node harus diatur.

Jika Anda penasaran untuk mempelajari tentang Binary tree vs Binary search tree, lihat PG Diploma IIIT-B & upGrad dalam Ilmu Data yang dibuat untuk para profesional yang bekerja dan menawarkan 10+ studi kasus & proyek, lokakarya praktis, bimbingan dengan industri pakar, tatap muka dengan mentor industri, 400+ jam pembelajaran dan bantuan pekerjaan dengan perusahaan-perusahaan top.

Pelajari kursus ilmu data online dari Universitas top dunia. Dapatkan Program PG Eksekutif, Program Sertifikat Tingkat Lanjut, atau Program Magister untuk mempercepat karier Anda.