STRUKTUR DATA TREE

By

 TREE

Tree didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yangdisebut root dan node, disebut sub tree/sub pohon atau cabang.



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.

ada 2 tree :

Tree Statik : isi node-nodenya tetap karena bentuk pohonnya sudah ditentukan.

Tree Dinamik : isi nodenya berubah-ubah karena proses penambahan (insert) dan penghapusan (delete)
Implementasi Tree Contoh penggunaan struktur pohon :
  1. Silsilah keluarga
  2. Parse Tree (pada compiler)
  3. Struktur File
  4. Pertandingan
Jenis-Jenis Tree
  1. Binary Tree
adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal duasubtree dan kedua subtree tersebut harus terpisah. Maka tiap node dalam binarytree hanya boleh memiliki paling banyak dua child.Keterangan :Left Child : B, D, H, ...Right Child : C, G, J, ...Jenis Binary Tree :
  1. Full Binary Tree
Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap sub treeharus mempunyai panjang path yang sama.
  1. Complete Binary Tree
Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang pathyang berbeda. Node kecuali leaf memiliki 0 atau 2 child.
  1. Skewed Binary Tree
Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.
simbol batu
simbol batu diperuntukan untuk mempermudah menyeimbangkan tree, maka digunakan simbol-simbol bantu.
▪Minus ( - ) : digunakan apabila subtree kiri lebih panjang dari subtree kanan.
▪1.4.2 Plus ( + ) : digunakan apabila subtree kanan lebih panjang dari subtree kiri.
▪Nol ( 0 ) : digunakan apabila subtree kiri dan subtree kanan mempunyai heightyang sama
cara Menambahkan Node Pada Tree
Karena pohon yang kita buat merupakan sebuah pohon biner, maka untuk menambahkan sebuah node, secara otomatis penambahan tersebut mengikuti aturan penambahan node pada pohon biner:
1. Jika pohon kosong, maka node baru ditempatkan sebagai akar pohon.
2. Jika pohon tidak kosong, maka dimulai dari node akar, dilakukan proses pengecekan berikut:
a. Jika nilai node baru lebih kecil dari nilai node yang sedang dicek, maka lihat ke kiri node tersebut. Jika kiri node tersebut kosong (belum memiliki kiri), maka node baru menjadi kiri node yang sedang dicek. Seandainya kiri node sudah terisi, lakukan kembali pengecekan a dan b terhadap node kiri tersebut. Pengecekan ini dilakukan seterusnya hingga node baru dapat ditempatkan.
b. Jika nilai node baru lebih besar dari nilai node yang sedang dicek, maka lihat ke kanan node tersebut. Jika kanan node tersebut kosong (belum memiliki kanan), maka node baru menjadi kanan node yang sedang dicek. Seandainya kanan node sudah terisi, lakukan kembali pengecekan a dan b terhadap node kanan tersebut. Pengecekan ini dilakukan seterusnya hingga node baru dapat ditempatkan.

2 komentar: