ALGORITMA DAN STRUKTUR DATA TREE PADA BIDANG IT

 Pengertian Tree

Kumpulan node yang saling terhubung satu sama lain dalam suatu  kesatuan yang membentuk layakya struktur sebuah pohon. Struktur pohon adalah suatu  cara merepresentasikan suatu struktur hirarki (one-to-many) secara grafis yang mirip sebuah pohon, walaupun pohon tersebut  hanya tampak sebagai kumpulan node-node  dari atas ke bawah. Suatu struktur data yang tidak linier yang menggambarkan  hubungan yang hirarkis (one-to-many) dan tidak linier antara elemen-elemennya.

Contoh penggunaan Struktur Tree:

• Silsilah keluarga
• Hasil pertandingan bentuk turnamen
• Struktur organisasi perusahaan

Definisi Gambar :

• Level : Semua node yang memiliki jarak yang sama dari root
• Parent : Node yang berada di atas node lain secara langsung
• Node : sebuah element dalam tree. Berisi informasi
• Root : Node teratas yang tidak punya parent. Memiliki derajat masuk 0.
• Child : cabang langsung dari sebuah node.
• Sibling : sebuah node lain yang memiliki parent yang sama.
• Leaf : sebuah node yang tidak memiliki child. Memiliki derajat keluar 0.
• Depth : jumlah yang berada dalam tree.
• Complete tree : semua parent memiliki child yang penuh.
• balanced : semua subtree memiliki depth yang sama

Jenis Jenis Tree

1. Binary Tree

Tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subpohon dan kedua subpohon harus terpisah.

Kelebihan struktur Binary Tree :

• Mudah dalam penyusunan algoritma sorting
• Searching data relatif cepat
• Fleksibel dalam penambahan dan penghapusan data

Pembentukan Binary Tree :

• dapat dilakukan dengan dua cara : rekursif dan non rekursif
• perlu memperhatikan kapan suatu node akan dipasang sebagai node kiri dan kapan sebagai node kanan
• misal ditentukan, node yang berisi info yang nilainya”lebih besar” dari parent akan ditempatkan disebelah kanan dan yang “lebih kecil disebelah kiri”.

Algoritma Binary Tree :

1. buat node baru
2. cek apakah root = null,
   jika ya, maka root=new melompat ke langkah 9;
   jika tidak, maka lakukan langkah berikut:
3. mencari posisi yang tepat untuk new, tentukan p = root, q = root
4. kerjakan langkah 5 & 6 selama q<> null dan new ->info<> p->info
5. tentuakan p= q
6. cek apakah new -> info < p -> info
   jika ya, (teruskan ke cabang kiri), tentukan q= p->kiri;
   jika tidak, (teruskan ke kanan), tentukan q = p -> kanan;
7. cek apakah new->info = p->info
   jika ya, (tidak perlu disisipkan), tampilkan pesan duplikasi, lompat ke langkah 9.
   jika tidak, (sisipkan), kerjakan langkah 8
8. cek apakah new->info < p->info
   jika ya, (sebagai cabang kiri), p->kiri = new
   jika tidak, (sebagai cabang kanan), p->kanan = new
9. selesai

1. KUNJUNGAN PADA POHON BINER

Sebuah pohon biner memiliki operasi  traversal  yaitu suatu kunjungan pada suatu simpul tepat satu kali. Dengan melakukan kunjungan lengkap kita akan memperoleh urutan informasi secara linier yang tersinpan di dalam pohon biner.

Terdapat tiga jenis kunjungan pada pohon biner, yaitu :

1. PREORDER

Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :

–  Cetak isi simpul yang dikunjungi.

–  Kunjungi cabang kiri.

–  Kunjungi cabang kanan.

2. INORDER

Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :

–  Kunjungi cabang kiri.

–  Cetak isi simpul yang dikunjungi.

–  Kunjungi cabang kanan.

3. POSTORDER

Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :

–  Kunjungi cabang kiri.

–  Kunjungi cabang kanan.

–  Cetak isi simpul yang dikunjungi