A.
Definisi Tree
Tree diartikan
sebagai satu kumpulan dari elemen salah satunya disebut dengan akar atau root,
dan sisa elemen lainnya terpecah menjadi sejumlah himpunan yang paling tidak
berhubungan satu sama lain, yang disebut dengan sub pohon, atau disebut juga
cabang. Jika kita melihat pada subpohon, maka subpohon ini juga mempunyai akar
dan sub-subpohonnya masing-masing, tree bisa juga disebut sebagai sebuah
struktur data yang secara bentuk menyerupai sebuah pohon, yang terdiri dari
serangkaian node (simpul) yang saling berhubungan. Node-node tersebut
dihubungkan oleh sebuah penghubung yang dinamakan vektor. Setiap node dapat
memiliki 1 atau lebih node anak. Sebuah node yang memiliki node anak disebut
node induk (parent). Sebuah node anak hanya memiliki satu node induk. Sesuai
konvensi ilmu komputer, tree bertumbuh ke bawah, tidak seperti pohon di dunia
nyata yang tumbuh ke atas. Dengan demikian node anak akan digambarkan berada di
bawah node induknya.
Cara
penggunaan Tree :
• notasi kurung
• diagram venn
• notasi tingkat
• notasi garis
• notasi kurung
• diagram venn
• notasi tingkat
• notasi garis
Sehingga dari data
diatas dapat disimpulkan bahwa, tree dapat didefinisikan sebagai kumpulan
simpul atau node dengan satu elemen yang disebut akar (root) dan cabang (node)
atau disebut juga sub tree atau sub pohon. Sehingga secara sederhana pohon bisa
didefinisikan sebagai kumpulan elemen yang salah satu elemennya disebut dengan
akar (root) dan elemen yang lainnya (simpul), terpecah menjadi sejumlah
himpunan yang saling tidak berhubungan satu dengan yang lainnya.
Dibawah ini adalah istilah – istilah umum yang digunakan dalam tree
:
a) Prodecessor : node yang berada diatas node tertentu.
b) Successor : node yang berada di bawah node tertentu.
c) Ancestor : seluruh node yang terletak sebelum node tertentu dan
terletak pada jalur yang sama.
d) Descendant : seluruh node yang terletak sesudah node tertentu
dan terletak pada jalur yang sama.
e) Parent : predecssor satu level di atas suatu node.
f) Child : successor satu level di bawah suatu node.
g) Sibling : node-node yang memiliki parent yang sama dengan suatu
node.
h) Subtree :
bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki
semua karakteristik dari tree tersebut.
i) Size : banyaknya node dalam suatu tree.
j) Height : banyaknya tingkatan/level dalam suatu tree.
k) Root : satu-satunya node khusus dalam tree yang tak punya
predecssor.
l) Leaf : node-node dalam tree yang tak memiliki seccessor.
m) Degree : banyaknya child yang dimiliki suatu node.
Dikutip dari (Struktur Data TREE dan Penjelasaanya Secara
Lengkap New Funday.htm)
B.
Implementasi
Implementasi dalam
pemrograman, dalam pokok bahasan ini akan dibicarakan untuk pohon biner saja.
Asumsi awal adalah data yang hendak dimasukkan ke dalam node, bertipe data
integer.
1. Deklarasi Tree
Karena tree tersusun oleh node-node, maka yang perlu kita
deklarasikan adalah komponen node itu sendiri. Dalam contoh dibawah, akan kita
namai Node.
Contoh deklarasi Source code:
Struct node {
Int data;
node *kanan;
node *kiri;
};
Variabel data adalah untuk menyimpan nilai, sedangkan kiri dan
kanan, bertipe pointer, masing-masing yang akan menunjuk ke node anak kiri dan
kanan.
2. Inisialisasi Tree
Untuk pertama kali, saat kita akan membuat sebuah pohon biner,
asumsi awal adalah pohon itu belum bertumbuh, belum memiliki node sama sekali,
sehingga masih kosong.
3. 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.
Binary Tree
Pohon biner bisa
didefinisikan sebagai suatu kumpulan simpul yang mungkin kosong atau mempunyai
akar dan dua subpohon yang saling terpisah yang disebut dengan subpohon kiri
dan sub pohon kanan. Subpohon disebut juga sebagai cabang. Karakteristik dari
pohon biner ialah bahwa setiap simpul paling banyak hanya mempunyai dua buah
anak. Dengan kata lain derajat tertinggi dari sebuah pohon biner adalah dua.
Pengertian daun, root, level, tinggi dan derajad yang berlaku pada pohon juga
berlaku pada binary tree. Penyajian binary tree pada komputer di gunakan double
link list. Pengertian lain dari Pohon biner adalah sebuah tree yang pada
masing-masing simpulnya hanya dapat memiliki maksimum 2 (dua) simpul anak.
Tidak boleh lebih.
Pada pohon biner,
umumnya kedua node
anak disebut dengan posisinya, yaitu kiri dan kanan.
Pada setiap simpul
pohon biner hanya berisi dua buah pointer yang menunjuk ke cabang kiri dan
cabang kanan, dengan melihat hal tersebut maka lebih baik struktur double link
list dapat digunakan dalam binary tree ini.
· Operasi pada Binary Search Tree
a.Searching/Pencarian
Pencarian pada
BST dapat dilakukan dengan cara rekursif atau iteratif.
Langkah
–langkah pencarian:
1. Periksa
apakah nilai pada simpul yang sekarang sedang diperiksa sesuai dengan yang dicari.
Jika ya maka nilai ditemukan, jika tidak:
2. Jika nilai
yang dicari lebih kecil daripada nilai yang sedang diperiksa sekarang: jika
simpul yang sekarang sedang diperiksa tidak memiliki anak kiri, maka nilai yang
dicari tidak ada pada BST.
Jika ada,
ulangi langkah yang sama pada anak kiri.
3. Jika nilai
yang dicari lebih besar daripada nilai yang sedang diperiksa sekarang , periksa
anak kanan. Jika simpul yang sedang diperiksa tidak punya anak kanan maka nilai
yang dicari tidak ada dalam BST. Jika punya, ulangi lankah yang sama pada anak
kanan.
b. Insertion/Penyisipan
Awal dari cara
kerja penyisipan sama dengan pencarian, jika akar yang sedang diperiksa tidak
sama dengan nilai yang ingin disisipi, kunjungi anak pohon kiri atau kanan
hingga akhirnya kita menemukan simpul eksternal dan menyisipkan nilai sebagai
anak kiri atau kanan—bergantung dari nilai.
c.
Deletion/Penghapusan
Terdapat 3
kasus yang mungkin dan perlu diatasi dalam penghapusan elemen pohon BST:
- Menghapus
simpul yang merupakan daun
- Menghapus
simpul dengan 1 anak
- Menghapus
simpul dengan 2 a
Jadi dapat
disimpulkan bahwa pohon biner adalah jenis dari struktur data pohon dimana
setiap node hanya bisa paling banyak memiliki 2 anak node. Seperti struktur
data lainnya, pohon digunakan untuk menyimpan informasi. Tidak seperti struktur
data Stack dan Queue, yang keduanya adalah struktur data linear,
pohon (biner) adalah struktur data hirarkis. Untuk mengatakan bahwa struktur
data pohon hirarkis berarti elemen pohon terurut diatas atau dibawah elemen
lainnya.
Share On
Tidak ada komentar:
Posting Komentar