4 Jenis Pohon dalam Struktur Data Dijelaskan: Properti & Aplikasi

Apa itu Pohon dalam Struktur Data?

Pohon adalah jenis struktur data yang mewakili data hierarkis. Ini memiliki struktur non-linear yang terdiri dari node yang dihubungkan oleh tepi. Di antara jenis struktur data lain yang melakukan operasi dalam struktur data linier, kompleksitasnya meningkat seiring dengan peningkatan ukuran data. Namun, struktur data pohon menyediakan akses yang lebih cepat ke data yang non-linear. Ketersediaan berbagai jenis struktur data dan algoritma yang terkait dengannya, kinerja tugas menjadi cara yang mudah dan efisien.

Beberapa terminologi yang terkait dengan pohon dalam struktur data adalah:

• Node : node adalah entitas dalam struktur data pohon yang berisi kunci atau nilai dan pointer ke node anaknya.
• Node anak : Sebuah node anak adalah keturunan dari setiap node.
• Node daun: Node yang tidak memiliki node anak dan merupakan node paling bawah dalam sebuah pohon. Mereka juga disebut node eksternal.
• Akar : Ini adalah titik paling atas dari sebuah pohon.
• Node internal : Node yang memiliki setidaknya satu node anak.
• Tepi: Tepi mengacu pada koneksi antara dua simpul di pohon.
• Tinggi simpul: Jumlah tepi dari simpul ke daun terdalam.
• Kedalaman simpul : Jumlah tepi dari akar ke simpul.
• Tinggi pohon : Tinggi simpul akar.
• Derajat suatu simpul : Jumlah total cabang ke simpul tersebut.
• Hutan: Kumpulan pohon yang terpisah-pisah.

Jenis pohon

1. Pohon biner

Pohon biner adalah jenis struktur data pohon di mana setiap simpul induk memiliki maksimal dua simpul anak. Seperti namanya, biner berarti dua, oleh karena itu, setiap node dapat memiliki 0, 1, atau 2 node. Struktur data pohon biner ditunjukkan pada Gambar 1. Node 1 di pohon berisi dua pointer, satu untuk setiap node anak. Node 2 lagi memiliki dua pointer masing-masing untuk dua node anak. Sedangkan simpul 3, 5, dan 6 adalah simpul daun dan oleh karena itu, memiliki penunjuk nol di bagian kiri dan kanan.

Gambar 1: Representasi pohon biner ( https://www.javatpoint.com/binary-tree ).

Sifat pohon biner

• Jumlah maksimum node pada setiap level I adalah 2 i .
• Tinggi pohon pada Gambar 1 adalah 3 yang berarti jumlah simpul maksimum (1+2+4+8) =15.

• Pada ketinggian h, jumlah maksimum node yang mungkin adalah (20 + 21 + 22+….2h) = 2h+1 -1.

• Pada ketinggian h, jumlah minimum node yang mungkin sama dengan h+1.

• Jumlah minimum node akan mewakili pohon dengan tinggi maksimum dan sebaliknya.

Bahkan pohon biner dapat dibagi menjadi beberapa jenis pohon berikut:

• Pohon Biner Penuh: Ini adalah jenis pohon biner khusus. Dalam struktur data pohon ini , setiap simpul induk atau simpul internal memiliki dua anak atau tidak ada simpul anak.
• Pohon biner sempurna: Dalam jenis struktur data pohon ini , setiap simpul internal memiliki tepat dua simpul anak dan semua simpul daun berada pada level yang sama.
• Pohon biner lengkap: Ini menyerupai pohon biner penuh dengan beberapa perbedaan.
• Setiap level terisi penuh.
• Node daun condong ke kiri pohon.
• Ini bukan persyaratan untuk simpul daun terakhir untuk memiliki saudara kandung yang tepat, yaitu pohon biner lengkap tidak harus pohon biner penuh.
• Pohon Degenerasi atau Patologis: Pohon -pohon ini memiliki satu anak di kiri atau kanan simpul induk.
• Pohon biner miring: Ini adalah pohon patologis atau degenerasi di mana pohon didominasi oleh simpul kiri atau simpul kanan. Oleh karena itu, ada dua jenis pohon biner miring, yaitu pohon biner miring kiri atau kanan.
• Pohon biner seimbang: Perbedaan antara ketinggian subpohon kiri dan kanan untuk setiap simpul adalah 0 atau 1.

2. Pohon Pencarian Biner

Struktur pohon ini tidak linier dan satu simpul terhubung ke sejumlah simpul. Node dapat dihubungkan ke paling banyak dua node anak. Disebut pohon pencarian biner karena:

• Setiap node memiliki maksimal dua node anak.
• Ini dapat digunakan untuk mencari elemen dalam waktu 0(log(n)) dan karenanya dikenal sebagai pohon pencarian.

Gambar: Contoh pohon pencarian Biner ( https://www.tutorialspoint.com/data_structures_algorithms/binary_search_tree.htm )

Properti pohon pencarian biner adalah:

• Nilai di semua simpul dari subpohon kiri harus lebih kecil dari nilai di simpul akar.
• Nilai di semua simpul dari subpohon kanan harus lebih besar dari nilai di simpul akar.

3. Pohon AVL

Pohon AVL adalah jenis atau varian dari pohon biner. Ini terdiri dari properti dari biner serta pohon pencarian biner. Diciptakan oleh Adelson Velsky Lindas, pohon-pohon ini menyeimbangkan diri yang berarti ketinggian subpohon kiri dan subpohon kanan seimbang. Keseimbangan ini diukur dari segi faktor penyeimbang.

Faktor penyeimbang:

• Ini adalah perbedaan antara subpohon kiri dan subpohon kanan.
• Nilai faktor penyeimbang harus 0, -1, atau 1. Oleh karena itu, setiap simpul pohon AVL harus terdiri dari nilai faktor penyeimbang yaitu 0, -1, atau 1.
• Balance Factor = (Tinggi Subpohon Kiri – Tinggi Subpohon Kanan)
• Sebuah pohon AVL dikatakan sebagai pohon seimbang jika faktor keseimbangan setiap node antara -1 sampai 1.

Nilai node selain -1, hingga 1 di pohon AVL akan mewakili pohon tidak seimbang yang perlu diseimbangkan.

• Jika suatu simpul memiliki faktor keseimbangan 1, berarti subpohon kiri satu tingkat lebih tinggi dari subpohon kanan.
• Jika sebuah simpul memiliki faktor keseimbangan 0, berarti tinggi subpohon kiri dan subpohon kanan sama.
• Jika suatu simpul memiliki faktor keseimbangan -1, berarti subpohon kanan satu tingkat lebih tinggi dari subpohon kiri atau subpohon kiri satu tingkat lebih rendah dari subpohon kanan.

4. B-Pohon

B Tree adalah bentuk yang lebih umum dari pohon pencarian biner. Ia juga dikenal sebagai pohon m way dengan tinggi seimbang, di mana m adalah orde pohon. Setiap simpul pohon dapat memiliki lebih dari satu kunci dan lebih dari dua simpul anak. Dalam kasus pohon biner, simpul daun mungkin tidak berada pada level yang sama. Namun, dalam kasus Pohon B, semua simpul daun harus berada pada level yang sama.

Sifat-sifat pohon-B:

• Kunci disimpan dalam urutan yang meningkat untuk setiap node x.
• Nilai Boolean "x.leaf" ada di setiap node, yang benar jika x adalah daun.
• Node internal harus memiliki paling banyak kunci “n-1”, di mana n adalah urutan pohon. Itu juga harus memiliki penunjuk untuk setiap anak.
• Semua simpul akan memiliki paling banyak n anak dan paling sedikit n/2 anak, kecuali simpul akar.
• Node daun pohon memiliki kedalaman yang sama.
• Node root akan memiliki minimal 1 kunci dan setidaknya dua anak.
• Jika n 1, maka untuk sembarang n-key B-tree dengan tinggi h dan derajat minimum t 2, h logt (n+1)/2.

Aplikasi

• Pohon Pencarian Biner dapat diterapkan untuk mencari elemen dalam kumpulan elemen.
• Heap tree digunakan untuk heap sort.
• Router modern menggunakan jenis pohon yang disebut Tries untuk menyimpan informasi perutean.
• B-Trees dan T-Trees sebagian besar digunakan oleh database populer untuk menyimpan data mereka.
• Pohon sintaks digunakan oleh kompiler untuk memvalidasi sintaks dari setiap program tertulis.

Kesimpulan

Struktur data menyediakan cara yang terorganisir untuk menyimpan data untuk pengelolaan yang mudah dan penanganan yang efektif. Berbagai jenis struktur data ada untuk berbagai jenis data. Berdasarkan jenis data yang perlu disimpan, itu dipilih oleh pengguna.

Pohon adalah jenis struktur data seperti itu di mana jenis data hierarkis dapat disimpan. Data disimpan dalam node yang terkadang menyimpan referensi untuk node lain yang disebut node anak.

Berdasarkan jumlah node anak, pohon dapat diklasifikasikan ke dalam berbagai jenis seperti yang disebutkan dalam artikel. Berdasarkan susunan node dalam jenis pohon, setiap struktur pohon memiliki properti yang terkait. Dengan berbagai jenis operasi yang dapat dilakukan oleh kelas pohon yang berbeda, jenis struktur data ini telah menemukan aplikasi dalam algoritma pengurutan dan penyimpanan data.

Program PG Eksekutif dalam Pengembangan Perangkat Lunak – Spesialisasi dalam Pengembangan Tumpukan Penuh, dikuratori oleh upGrad & IIIT-Bangalore, dapat membantu Anda meningkatkan profil dan mengamankan peluang kerja yang lebih baik sebagai programmer.