Pohon Biner dalam Struktur Data: Properti, Jenis, Representasi & Manfaat

Di antara berbagai jenis struktur data adalah pohon biner yang datang dengan lebih banyak kegunaan daripada kebanyakan jenis lainnya. Aplikasi mereka yang paling menonjol termasuk pemrograman peer-to-peer, pencarian, kriptografi, router jaringan dengan bandwidth lebih tinggi daripada yang lain, dan video game 3D. Sekarang kita akan membahas secara rinci apa itu pohon biner dalam ilmu data, apa jenisnya, dan bagaimana mereka diwakili.

Apa itu pohon biner?

Jika Anda telah bekerja pada pohon normal sebelumnya atau bahkan mengetahui tentang dasar-dasarnya, Anda akan tahu bahwa tidak ada batasan dalam hal jumlah anak yang diizinkan untuk dimiliki oleh node yang berbeda di pohon ini. Pohon biner sedikit berbeda dalam pengertian ini. Setiap orang tua atau simpul di pohon biner dapat memiliki maksimal hanya dua anak.

Semua node dalam pohon biner memiliki tiga komponen utama –

• elemen data
• referensi yang tepat
• referensi kiri

Node yang terletak di bagian atas pohon disebut sebagai root node. Node induk adalah node yang memiliki anak. Node anak dan node induk terhubung satu sama lain melalui referensi. Node yang tidak memiliki anak disebut sebagai leaf node.

Jelas terlihat bahwa node dalam pohon biner dapat memiliki satu anak, dua anak, atau tidak ada anak sama sekali. Pohon biner bukanlah struktur data linier seperti antrian, larik, tumpukan, dan daftar tertaut. Mereka adalah struktur data hierarkis.

Lihat: Ide Proyek Ilmu Data untuk Pemula

Properti penting dari node di pohon biner

Pemahaman yang lebih baik tentang properti ini akan membantu Anda memanfaatkan diskusi tentang pohon biner ini. Kedalaman node yang berbeda didefinisikan sebagai jumlah node yang ada di jalan yang menghubungkan root ke node tertentu. Itulah sebabnya kedalaman simpul akar adalah 0. Di sisi lain, ketinggian simpul yang berbeda dalam pohon biner adalah jumlah simpul yang terletak di jalur yang menghubungkan simpul tertentu dengan simpul akar. Itu sebabnya tinggi simpul daun adalah 0.

Seperti yang dapat Anda lihat dengan jelas, kedalaman sebuah simpul diukur dengan memulai dari simpul akar dan kemudian turun untuk mencapai simpul tersebut. Di sisi lain, ketika menghitung ketinggian, kita mulai dari simpul yang bersangkutan dan kemudian menuju ke simpul akar. Kedua kali, kita mulai dari 0. Ada orang yang juga mengukur tinggi dan kedalaman dari 1 dan bukan dari 0, yang tidak salah dan hanya disukai orang yang berbeda.

Sekarang kedalaman maksimum sebuah simpul didefinisikan sebagai kedalaman pohon biner. Demikian pula, tinggi maksimum sebuah simpul didefinisikan sebagai tinggi pohon biner. Jadi tinggi dan kedalaman pohon biner selalu sama.

Pelajari lebih lanjut: Struktur & Algoritma Data dengan Python

Apa itu pohon pencarian biner?

Pohon pencarian biner adalah yang paling umum dari semua jenis pohon biner lainnya. Ini adalah pohon biner khusus yang datang dengan properti yang berbeda dan lebih berguna daripada bentuk lain dari pohon biner. Apa sebenarnya pohon pencarian biner atau BST? Seperti namanya, pohon pencarian biner digunakan untuk mencari data di pohon.

BST hadir dengan properti yang memungkinkannya memfasilitasi pencarian yang efisien. Sebuah BST adalah pohon biner yang memiliki kunci dari node yang lebih kecil dan lebih besar dari node di sub-pohon kanan dan node di sub-pohon kiri masing-masing.

Representasi pohon biner

1. Representasi terkait

Pohon biner dalam representasi tertaut disimpan dalam memori sebagai daftar tertaut. Daftar ini memiliki simpul yang tidak disimpan di lokasi memori yang berdekatan atau berdekatan dan dihubungkan satu sama lain melalui hubungan induk-anak yang terkait dengan pohon.

Dalam representasi ini, setiap node memiliki tiga bagian yang berbeda –

• pointer yang menunjuk ke node kanan,
• pointer yang menunjuk ke arah node kiri,
• elemen data.

Ini adalah representasi yang lebih umum. Semua pohon biner terdiri dari penunjuk akar yang menunjuk ke arah simpul akar. Ketika Anda melihat simpul akar menunjuk ke nol atau 0, Anda harus tahu bahwa Anda berurusan dengan pohon biner kosong. Pointer kanan dan kiri menyimpan alamat anak kanan dan kiri pohon.

2. Representasi berurutan

Meskipun lebih sederhana daripada representasi tertaut, ketidakefisienannya membuatnya menjadi representasi pohon biner yang kurang disukai dari keduanya. Inefisiensi terletak pada jumlah ruang yang dibutuhkan untuk penyimpanan elemen pohon yang berbeda. Representasi sekuensial menggunakan array untuk penyimpanan elemen pohon.

Jumlah node pohon biner telah menentukan ukuran array yang digunakan. Node akar dari pohon biner terletak pada indeks pertama array. Indeks di mana node tertentu disimpan akan menentukan indeks di mana anak-anak kanan dan kiri dari node akan disimpan. Pohon kosong memiliki null atau 0 sebagai indeks pertamanya.

Jenis pohon biner

1. Pohon biner penuh: Pohon biner penuh adalah pohon biner yang simpulnya memiliki dua anak atau tidak sama sekali. Dengan kata lain, pohon biner menjadi pohon biner penuh ketika selain daun, semua simpul lainnya memiliki dua anak.
2. Pohon biner lengkap: Pohon biner lengkap adalah pohon yang semua levelnya terisi penuh. Satu-satunya pengecualian untuk ini adalah level terakhir mereka, yang kuncinya sebagian besar berada di sebelah kiri. Tumpukan biner sering diambil sebagai contoh pohon biner lengkap.
3. Pohon biner sempurna: Pohon biner sempurna adalah pohon biner yang daunnya ada pada tingkat yang sama dan simpul internalnya membawa dua anak. Contoh umum dari pohon biner sempurna adalah pohon keluarga leluhur.
4. Pohon biner degenerasi patologis: Pohon degenerasi adalah pohon biner yang simpul internalnya memiliki satu anak. Tingkat kinerja mereka mirip dengan daftar tertaut. Pelajari lebih lanjut tentang jenis pohon biner.

Baca: Enam Struktur Data Yang Paling Umum Digunakan di R

Manfaat pohon biner

1. Cara ideal untuk menggunakan cara hierarkis menyimpan data
2. Mencerminkan hubungan struktural yang ada dalam kumpulan data yang diberikan
3. Buat penyisipan dan penghapusan lebih cepat daripada daftar dan larik tertaut
4. Cara yang fleksibel untuk menyimpan dan memindahkan data
5. Digunakan untuk menyimpan node sebanyak mungkin
6. Lebih cepat dari daftar tertaut dan lebih lambat dari array saat mengakses elemen

Kesimpulan

Di blog ini, kita telah membahas apa itu pohon biner dalam struktur data serta membicarakan jenisnya, representasinya, dan manfaatnya. Dua kegunaan utama pohon adalah untuk mencari dan menyimpan data, dan karenanya merupakan bagian integral dari studi Ilmu Data dan bidang terkaitnya.

Jika Anda penasaran untuk belajar tentang pohon biner dalam struktur data, ilmu data, lihat Program PG Eksekutif IIIT-B & upGrad dalam Ilmu Data yang dibuat untuk para profesional yang bekerja dan menawarkan 10+ studi kasus & proyek, lokakarya praktis, bimbingan dengan pakar industri, 1-on-1 dengan mentor industri, 400+ jam pembelajaran dan bantuan pekerjaan dengan perusahaan-perusahaan top.