Jumat, 23 Mei 2014
penjelasan lebih jauh tentang heap n deap lalu penjelasan dekilas tentang leftist, tries, hashing, dan btree
pert 10
heap n deap
ciri:
heap = complete binary tree
min - tree ascending
max - tree descending
index parent = index child /2
child left = index parent * 2
child right = index parent * 2+1
(upheap = ngecek parent, downhead = ngecek child)
fungsi:
buat ngebantu cari nilai max n min
implementasi:
index dari 1
insertion:
min heap = node di tempat index terakhir, banding dgn parent ,parent lbih besar dari child tukar, sampai parent lbih kecil dari child.
max heap = node di tempat index terakhir, banding dgn parent ,parent lbih kecil dari child tukar, sampai parent lbih besar dari child.
deletion:
root di hapus (cuma bisa root yang di hapus), langsung di tukar dengan index terakhir lalu tukar dengan child bila child lbh kecil sampai tree sesuai urutan nilainya antara parent node & child .
min - max heap = gabungan min & max heap
ciri :
root berawal dari min lalu childnya max lalu min lagi lalu max lagi dan seterusnya
insertion:
kalau masuk di level min banding dengan parent, kalau parent lbih kecil swap , terus banding dengan granparent kalau grand parent (sama - sama level min) lbih besar ga swap
kalau masuk di level max banding dengan parent, kalau parent lbih besar swap , terus banding dengan granparent kalau grand parent (sama - sama level max) lbih kecil ga swap
deletion
min = root hapus , index terakhir gantiin ,trus root baru bandingin sama grandchild ke satunya (sama - sama level min) cari sama yang paling kecil di level tsb , lalu bila ada yg lbih kecil daripada root maka tukar dengan root node yg paling kecil
bila masih 1 level di bawahnya lagi maka banding dengan childnya kalo lebih kecil childnya maka swap
max = pilih yang paling besar di level max teratas, lalu hapus, lalu ganti dengan index terakhir, terus index yang di ganti itu banding dengan grandchildnya lalu bila ada yg lbih besar daripada node maka tukar dengan node yg paling besar
bila masih 1 level di bawahnya lagi maka banding dengan childnya kalo lebih besar childnya maka swap
deap (dable ended heap)
root selalu null
sebelah kanan min, kiri max
pratner = kalau node di tumpuk ada di titik yang sama
level min = index - index/2
level max = index + index/2
kalau partner kosong maka partner jadi parent dari partner seharusnya
level min =(index - index/2) /2
level max = (index + index/2) /2
insertion deap :
node masuk di index trakhir, lalu banding dengan partner, kalo partner lebih besar maka swap , lalu cek dengan parent kalau ga cocok maka swap
deletion
min = seperti heap lalu di cek dengan partner kalo lebih besar maka swap
max = seperti heap lalu di cek dengan partner kalo lebih kecil maka swap
Btree :
ciri -> orde (m) , key(m-1),
node sejumlah m
insertion:
masuk ke key yang sudah ada, kalau node penuh
deletion:
tandai,
leftist tree , tries , hashing
leftist tree :
s(kiri ) >= s(kanan)
penjelasan lebih jauh di lihat dapat di lihat di:
certifiedshare.blogspot.com
soundia
tries (previx tree):
auto correct di hp
hashing :
(hashing table)
collision(2 data yang sama) -> linear probing (baca slide)
-> chaining (linked list)
Langganan:
Posting Komentar (Atom)
Tidak ada komentar:
Posting Komentar