5 Jenis Pohon Biner dalam Struktur Data Dijelaskan

Pohon biner adalah struktur data pohon non-linear yang berisi setiap node dengan maksimal 2 anak. Nama biner menyarankan angka 2, jadi setiap pohon biner dapat memiliki anak kiri dan kanan.

Pointer menggambarkan pohon biner ke simpul paling atas, biasanya dikenal sebagai akar pohon. Setiap node dalam pohon biner berisi data, penunjuk ke anak kiri, dan penunjuk ke anak kanan. Pointer digunakan untuk mengimplementasikan pohon biner. Penunjuk akar menunjukkan simpul pertama di pohon. Untuk membuat pohon biner, Anda harus membuat node terlebih dahulu.

Setelah mengenalapa itu pohon biner dalam struktur data , Anda juga perlu mengetahui operasi dasar yang dilakukan pada pohon biner.Anda dapat melakukan fungsi seperti menyisipkan elemen, menghapus elemen, mencari elemen, dan melintasi pohon biner.

Setiappohon biner dalam struktur data digunakan dalam dua cara berbeda dalam komputasi.Pertama, mereka digunakan untuk mengakses node tergantung pada label atau nilai tertentu yang terhubung dengan setiap node. Kedua, mereka digunakan sebagai representasi data dengan struktur bercabang yang relevan.

Sebelum membahas berbagaijenis pohon biner , mari kita kenali terlebih dahulu terminologi yang digunakan dalam pohon biner.

Node: Ini menyimpan nilai data dalam pohon biner.

Root: Node paling atas di pohon biner apa pun disebut akar pohon.

Ukuran: Ini menunjukkan jumlah node dalam pohon biner.

Node induk: Sebuah node dalam pohon biner dengan anak.

Simpul anak: Ini adalah simpul yang berasal dari simpul induk yang menjauh dari akar pohon biner.

Node internal: Ini adalah node dengan setidaknya satu anak di pohon biner.

Leaf node: Ini adalah node tanpa anak.Ini juga merupakan node eksternal.

Kedalaman pohon simpul: Dihitung dalam konteks simpul tertentu.Ini disebut sebagai jumlah sisi dari node tertentu ke root.

Panjang jalur internal pohon: Ini mengacu pada jumlah level setiap node internal dalam pohon biner.

Panjang jalur eksternal pohon: Didefinisikan sebagai jumlah level setiap node eksternal dalam pohon biner.

Ketinggian simpul di pohon: Ini adalah jumlah tepi dari simpul tertentu ke simpul daun terdalam dari pohon biner.Ketinggian akar akan selalu lebih tinggi dari simpul lain di pohon biner.

Sekarang mari kita lihat detail 5jenis pohon biner.

Jenis Pohon Biner

1. Pohon Biner Penuh

Pohon biner dalam struktur data ini juga dikenal dengan nama -Proper binary tree dan Strict binary tree.Ini adalah salah satujenis pohon biner yang paling mendasar dalam struktur data.Pohon biner penuh didefinisikan sebagai pohon biner di mana setiap node harus memiliki dua atau tidak ada anak sama sekali.

Ini juga dicirikan sebagai pohon biner di mana setiap simpul terdiri dari dua anak kecuali simpul daun. Simpul di mana alamat simpul akar disimpan disebut simpul anak-anak dari akar. Simpul yang tidak memiliki anak disebut simpul daun.

Anda perlu melakukan perjalanan ke semua node untuk memeriksa apakah sebuah pohon adalah pohon biner. Kode akan mengembalikan "False" jika ada node yang memiliki satu anak. Ini akan mengembalikan "Benar" jika semua node memiliki 0 atau 2 anak.

Berikut adalah properti dari full binary tree:

• Jumlah simpul daun sama dengan jumlah simpul dalam + 1. Misalnya, jika jumlah simpul dalam adalah 4, maka jumlah simpul daun sama dengan 5.
• Jumlah maksimum node dan jumlah node dalam pohon biner adalah sama. Ini direpresentasikan sebagai 2j+1 -1.
• Jumlah minimum node dalam pohon biner penuh adalah 2h-1.
• Tinggi minimum pohon biner penuh adalah log 2 (n+1) – 1.
• Tinggi maksimum pohon biner penuh adalah h = (n+1)/2.

2. Pohon Biner Sempurna

Pohon biner sempurna adalah salah satujenis pohon biner di mana setiap node harus memiliki 0 atau 2 anak, dan setiap level node daun harus sama.Dengan kata lain,pohon biner sempurna dalam struktur data didefinisikan sebagai pohon yang semua simpul interiornya memiliki dua cabang dan simpul tanpa cabang (simpul daun) berada pada level yang sama.

Dalam konteks ini, level dari sebuah node adalah jarak atau ketinggian dari root node. Anda dapat menganggap pohon biner sempurna sebagai pohon biner lengkap di mana level terakhir juga terisi penuh.

Pelajarikursus ilmu dataonline dari Universitas top Dunia.Dapatkan Program PG Eksekutif, Program Sertifikat Lanjutan, atau Program Magister untuk mempercepat karier Anda.

3. Pohon Biner Lengkap

Pohon biner lengkap adalah salah satu jenis pohon biner dalam struktur data di mana semua level pohon terisi penuh.Level terakhir pohon biner mungkin terisi penuh atau tidak. Namun, setiap node harus ditempatkan di posisi paling kiri di level terakhir node. Node harus dimasukkan dari kiri.

Mereka adalah salah satujenis penting dari pohon biner karena menawarkan rasio terbaik antara jumlah node dan tinggi pohon.

Berikut adalah properti kunci dari pohon biner lengkap:

• Jumlah maksimum node adalah 2 h+1 – 1.
• Jumlah minimum node adalah 2 jam .
• Tinggi minimum adalah log 2 (n+1) – 1.

4. Pohon Biner Seimbang

Dalam pohon biner Seimbang, tinggi pohon adalah log 2 dari jumlah total simpul. Misalkan tinggi pohon adalah h dan jumlah total simpul pohon adalah n. Persamaan untuk menghitung tinggi adalah h = log(n). Selisih maksimum tinggi antara subpohon kanan dan subpohon kiri harus “1”.

Perbedaannya dapat memiliki nilai lain seperti 0 dan -1. Jenis pohon biner ini juga disebut pohon AVL.Salah satu contoh terkenal dari pohon biner seimbang adalah pohon Merah-Hitam.

Anda dapat menerapkan kode berikut untuk menjalankan pohon biner yang seimbang.

Node kelas pribadi {

nilai int pribadi;

Node pribadi tersisa;

Node pribadi benar;

}

public boolean isBalanced(Node n) {

if (balancedtreeHeight(n) > -1)

kembali benar;

kembali salah;

}

public int balancedtreeHeight(Node n) {

jika (n == nol)

kembali 0;

int h1 = balancedtreeTinggi(n.kanan);

int h2 = balancedtreeTinggi(n.kiri);

jika (h1 == -1 || h2 == -1)

kembali -1;

jika (Matematika.abs(h1 – h2) > 1)

kembali -1;

jika (h1 > h2)

kembali h1 + 1;

kembali h2 + 1;

}

Periksa AS - Program Ilmu Data kami

5. Merosot Pohon Biner

Pohon biner yang merosot adalah salah satujenis pohon pencarian biner yang jarang digunakan .Ini adalah pohon biner di mana setiap simpul hanya memiliki satu anak, yaitu anak kiri atau kanan. Tidak ada simpul yang harus memiliki anak kiri dan kanan.

Baca Artikel Populer AS - Ilmu Data kami

Kesimpulan

Sangat penting untuk memahamiapa itu pohon biner dalam struktur data jika Anda ingin menggunakannya untuk berbagai aplikasi.Menerapkan berbagai fungsi pada pohon biner dapat membantu Anda mengatur dan menyimpan data secara efisien.

Mempelajari berbagai jenis pohon biner membantu Anda melakukan operasi dengan lebih efektif dalam kompleksitas waktu. Dasar-dasar ilmu data, termasukstruktur data pohon biner, membantu Anda memulai perjalanan ilmu data dengan mudah.Selanjutnya, Anda dapat mengerjakan proyek sains data tingkat lanjut untuk meningkatkan keterampilan dan portofolio Anda.

Mulailah Dengan Perjalanan Machine Learning Anda di upGrad

Jika Anda ingin belajar Ilmu Data, Anda dapat mengejar gelar Master of Science dalam program Ilmu Data upGrad. Kursus 24 bulan ini mengajarkan keterampilan seperti Python, Menerapkan Model ML, pemrosesan BD menggunakan Spark, Analisis & Statistik Prediktif, dan Model ML yang Diawasi dan Tidak Diawasi. Kursus ini cocok untuk manajer yang ambisius, lulusan MBA, insinyur, dan profesional di berbagai bidang.

Menyelesaikan kursus ini akan membantu Anda bekerja sebagai Insinyur Data, Analis Data Besar, Insinyur Pembelajaran Mesin, dan Ilmuwan Data.