5 Jenis Pohon Biner Dijelaskan [Dengan Ilustrasi]

Dalam ilmu komputer, berbagai struktur data membantu dalam mengatur data dalam berbagai bentuk. Di antara mereka, pohon banyak digunakan struktur data abstrak yang mensimulasikan struktur pohon hierarkis. Sebuah pohon biasanya memiliki nilai akar dan subpohon yang dibentuk oleh simpul anak dari simpul induknya. Pohon adalah struktur data non-linier.

Struktur data pohon umum tidak memiliki batasan jumlah node anak yang dapat ditampungnya. Namun, ini tidak terjadi dengan pohon biner. Artikel ini akan mempelajari tentang struktur data pohon tertentu – pohon biner dan jenis pohon biner .

Apa itu Struktur Data Pohon Biner?

Pohon biner adalah struktur data non-linier tipe pohon dengan maksimal dua anak untuk setiap orang tua. Setiap node dalam pohon biner memiliki referensi kiri dan kanan bersama dengan elemen data. Node di bagian atas hierarki pohon disebut root node. Node yang menampung sub-node lain adalah node induk.

Sebuah simpul induk memiliki dua simpul anak: anak kiri dan anak kanan. Hashing, merutekan data untuk lalu lintas jaringan, kompresi data, menyiapkan tumpukan biner, dan pohon pencarian biner adalah beberapa aplikasi yang menggunakan pohon biner.

Terminologi yang terkait dengan Pohon Biner dan Jenis Pohon Biner

• Node: Ini mewakili titik terminasi di pohon.
• Root: Node paling atas pohon.
• Induk: Setiap node (terlepas dari root) di pohon yang memiliki setidaknya satu sub-node sendiri disebut node induk.
• Anak: Sebuah simpul yang langsung berasal dari simpul induk ketika bergerak menjauh dari akar adalah simpul anak.
• Leaf Node: Ini adalah node eksternal. Mereka adalah node yang tidak memiliki anak.
• Internal Node: Seperti namanya, ini adalah inner node dengan setidaknya satu anak.
• Kedalaman Pohon: Jumlah tepi dari simpul pohon ke akar adalah.
• Tinggi Pohon: Ini adalah jumlah tepi dari simpul ke daun terdalam. Tinggi pohon juga dianggap sebagai tinggi akar.

Karena Anda sekarang sudah familiar dengan terminologi yang terkait dengan pohon biner dan jenis pohon biner, sekarang saatnya untuk memahami komponen pohon biner . Lihat kursus ilmu data kami untuk mempelajari secara mendalam tentang struktur dan komponen biner.

Komponen Pohon Biner

Ada tiga komponen pohon biner . Setiap simpul pohon biner memiliki tiga komponen yang terkait dengannya. Ini menjadi konsep penting bagi programmer untuk memahami tiga komponen pohon biner ini:

1. elemen data
2. Pointer ke subpohon kiri
3. Pointer ke subpohon kanan

Sumber

Ketiga komponen pohon biner ini mewakili sebuah simpul. Data berada di tengah. Pointer kiri menunjuk ke node anak, membentuk sub-pohon kiri. Pointer kanan menunjuk ke simpul anak di sebelah kanannya, membuat subpohon kanan.

Baca: Pertanyaan Tebakan Teratas & Metode Informatif untuk Ilmu Data

Jenis Pohon Biner

Ada berbagai jenis pohon biner , dan masing-masing jenis pohon biner ini memiliki karakteristik yang unik. Berikut adalah masing-masing jenis pohon biner secara rinci:

1. Pohon Biner Penuh

Ini adalah jenis pohon biner khusus yang memiliki nol anak atau dua anak. Ini berarti bahwa semua simpul dalam pohon biner itu harus memiliki dua simpul anak dari simpul induknya atau simpul induk itu sendiri adalah simpul daun atau simpul eksternal.

Dengan kata lain, pohon biner penuh adalah pohon biner unik di mana setiap simpul kecuali simpul eksternal memiliki dua anak. Ketika memegang satu anak, pohon biner seperti itu tidak akan menjadi pohon biner penuh. Di sini, jumlah simpul daun sama dengan jumlah simpul internal ditambah satu. Persamaannya seperti L=I+1, di mana L adalah jumlah simpul daun, dan I adalah jumlah simpul internal.

Berikut adalah struktur pohon biner penuh:

2. Pohon Biner Lengkap

Pohon biner lengkap adalah jenis pohon biner spesifik lainnya di mana semua level pohon diisi seluruhnya dengan node, kecuali level terendah dari pohon. Juga, di tingkat terakhir atau terendah dari pohon biner ini, setiap simpul mungkin harus berada di sisi kiri. Berikut adalah struktur pohon biner lengkap:

3. Pohon Biner Sempurna

Pohon biner dikatakan 'sempurna' jika semua simpul internal memiliki dua anak, dan setiap simpul eksternal atau daun berada pada level atau kedalaman yang sama di dalam sebuah pohon. Pohon biner sempurna yang memiliki tinggi 'h' memiliki 2h – 1 simpul. Berikut adalah struktur pohon biner sempurna:

4. Pohon Biner Seimbang

Pohon biner dikatakan 'seimbang' jika tinggi pohon adalah O(logN), di mana 'N' adalah jumlah simpul. Dalam pohon biner seimbang, ketinggian subpohon kiri dan kanan setiap simpul harus bervariasi paling banyak satu. Pohon AVL dan Pohon Merah-Hitam adalah beberapa contoh umum dari struktur data yang dapat menghasilkan pohon pencarian biner yang seimbang. Berikut adalah contoh pohon biner seimbang:

5. Pohon Biner Degenerasi

Pohon biner dikatakan sebagai pohon biner degenerasi atau pohon biner patologis jika setiap simpul internal hanya memiliki satu anak. Pohon seperti itu mirip dengan kinerja daftar tertaut. Berikut adalah contoh pohon biner yang mengalami degenerasi:

Manfaat Pohon Biner

• Operasi pencarian di pohon biner lebih cepat dibandingkan dengan pohon lain
• Hanya dua traversal yang cukup untuk menyediakan elemen dalam urutan yang diurutkan
• Sangat mudah untuk mengambil elemen maksimum dan minimum
• Graf traversal juga menggunakan pohon biner
• Mengonversi ekspresi postfix dan prefix yang berbeda dimungkinkan menggunakan pohon biner

Baca Juga: Pohon Keputusan dalam Pembelajaran Mesin: Fungsi, Klasifikasi, Kelebihan & Kekurangan

Kesimpulan

Pohon biner adalah salah satu pohon yang paling banyak digunakan dalam struktur data. Setiap jenis pohon biner memiliki fitur uniknya sendiri. Struktur data ini memiliki persyaratan khusus dalam ilmu komputer terapan. Kami berharap artikel tentang jenis pohon biner ini bermanfaat. upGrad menawarkan berbagai kursus dalam ilmu data, pembelajaran mesin, data besar, dan banyak lagi.

Jika Anda penasaran untuk belajar tentang 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.