RSS Feed
Twitter
10/21/2013 11:02:00 PM
dedi.neo
Leaf sebuah node yang tidak memiliki
children. Leaf biasa disebut sebagai external node, sedangkan node selainnya
disebut sebagai internal node
Leaf merupakan semua simpul yang berada
pada tingkat terendah dari pohon dinamakan daun (leaf node). Sejak
mereka terletak pada tingkat paling bawah, mereka tidak memiliki anak satupun.
Seringkali, daun merupakan simpul terjauh dari akar. Dalam teori grafik, sebuah
daun adalah sebuah sudut dengan tingkat 1 selain akar (kecuali jika pohonnya
hanya memiliki satu sudut; maka akarnya adalah daunnya juga). Setiap pohon
memiliki setidaknya satu daun.
Dalam pohon berdasarkan genetic programming sebuah
daun (juga dibilang terminal) adalah bagian terluar dari sebuah program pohon.
Jika dibandingkan dengan fungsinya atau simpul dalam, daun tidak memiliki
argumen. Di banyak kasus dalam daun-GP input ke programnya.
Dimulai dari node root,
menggunakan tes terhadap atribut dari record yang belum ada
kelasnya ini lalu mengikuti cabang yang sesuai dengan hasil dari tes tersebut,
yang akan membawa kepada internal node (node yang memiliki satu
cabang masuk dan dua atau lebih cabang yang keluar), dengan cara harus
melakukan tes lagi terhadap atribut
atau node leaf. Record yang kelasnya tidak diketahui
kemudian diberikan kelas yang sesuai dengan kelas yang ada
pada node leaf. Pada pohon keputusan setiap simpul leaf menandai
label kelas. Proses dalam pohon keputusan yaitu mengubah bentuk data (tabel) menjadi
model pohon (tree) kemudian mengubah model pohon tersebut menjadi aturan (rule)
(J R Quinlan, 1993). –
Algoritma Insert Elemen y:
- Cari leaf yang tepat bagi y
Persis dgn BST, bandingkan y dgn isi node2 pd path
yang tepat, dari ROOT turun menuju leaf.
•
jika
y sudah ada pd tree, insert gagal
•
jika
tree masih kosong, create root baru dengan elemen y di data_l (>)
•
jika
leaf yang tepat telah ditemukan, ada 3 kemungkinan:
A: Leaf hanya punya 1 elemen (data_l) (>)
•
jika
y > data_l : masukkan y sbg data_r (data_r = y)
•
jika
sebaliknya: geser elemen lama (data_r = data_l), dan masukkan y sbg data_l
(data_l = y)
B:
Leaf berisi 2 elemen (FULL) dan parent berisi 1 elemen
–
Bandingkan
ketiga elemen (2 elemen leaf dan y). Nilai tengah dimasukkan ke parent.
–
Jika
leaf adalah left_child dari parent, geser elemen parent ke kanan dan masukkan
nilai tengah ke data_l parent.
–
Pointer
left_child dan middle_child pada parent harus digeser.
–
Jika
leaf adalah middle_child dari parent, masukkan nilai tengah ke data_r parent.
–
Dua
nilai terkecil dan terbesar, akan menjadi elemen pertama pada leaf yang lama
dan leaf yang baru.
C:
Jika leaf dan parent sudah berisi 2 elemen (FULL)
–
Seperti
kasus B, nilai tengah diserahkan pada parent. Karena parent sudah full,
dilakukan hal yang sama menuju root hingga bertemu dgn 2-node.
–
Jika
pada path dari leaf hingga root, semua node merupakan 2-node, akan terbentuk
root baru dengan elemen nilai tengah. Nilai terkecil dan terbesar akan menjadi
2 children dari root baru.
“Doing a
few small 2-3 trees by hand helps to understand this algorithm”
Delete Elemen:
Penghapusan elemen
berlawanan
- Cari elemen yang akan dihapus
- Jika elemen berada di leaf p
a) Jika p 3-node (berisi 2 elemen)
Elemen langsung dihapus, shg p hanya memiliki 1 elemen
a) Jika p 2-node (berisi 1-elemen)
Node parent p disebut r, dan sibling kiri/kanan p adalah
q.
•
Jika
sibling q 3-node, dilakukan rotasi, elemen parent r diletakkan di p dan elemen
q diletakkan di r
•
Jika
sibling q 2-node, dilakukan penggabungan
q dan q, sehingga jumlah children r berkurang 1
d) Jika setelah rotasi/penggabungan node parent r kosong,
berarti r = root, maka node p dijadikan root baru
3.
Jika
elemen yang akan dihapus tidak ada di leaf, maka elemen tsb akan digantikan elemen
terbesar dari subtree kiri atau elemen terkecil dari subtree kanan yang berada
di leaf. Selanjutnya penghapusan elemen di leaf akan mengikuti langkah 2.
Mencari Leaf
(daun)
void
leaf(Tree *root){
if(root == NULL) printf("kosong!");
if(root->left!=NULL)
leaf(root->left);
if(root->right!=NULL)
leaf(root->right);
if(root->right == NULL
&& root->left == NULL) printf("%d ",root->data);
}
Daftar
Pustaka
