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)

                                                                   

Minggu, 18 Mei 2014

b tree & heap n deap


->B- tree

> b-tree mempunyai beberapa sifat sebagai berikut
- setiap node mempunyai jumlah node dalam tree yang sempurna
- mempunyai ciri yang sama deperti 2-3 tree
- setiap node paling tidak mempunyai 2 child
- bila dalam 1 node mempunyai jumlah nilai sebanyak 'i' maka jumlah anaknya 'i+1'
- semua nilai data terurut

insert
- cara memasukan nilai yang baru tergantung dalam nilai yang i dimasukan itu sendiri
- bisa dimsukan dalam node diatas atau child


delete
- cara menghilangkan nilai tergantung dalam nilai yang i dimasukan itu sendiri
- dalam mendelete nilai bisa mempengaruhi seluruh struktur tree itu sendiri


->heap & deap

> heap & deap adalah suatu tree yang mempunyai struktur yang sangat bergantung pada urutan nilai dalam nodenya
>min heap = nilai node paling kecil d atas
>max heap = nilai node paling besar di atas
>min-max heap = mempunyai nilai ascending di 1 sisi dan descending di sisi lainnya
>piq =  fungsi buat ngambil plg atas (min)
>maxim = fungsi buat ngambil plg atas (max)


Jumat, 09 Mei 2014

pembelajaran sesi 8 RBT dan 2-3 tree


-> Red Black Tree
ciri2:
> dalam sebuah rbt setiap nodenya mempunyai warna  yaitu warna merah atau  hitam
> bagian root dalam sebuah rbt  selalu berwarna hitam
> dalam rbt juga mempunyai 2 fungsi yaitu insert dan delete
> dalam rbt juga ada yang namanya external nodenya, yaitu node yang selalu ada di paling akhir yang berwarna black.
> kalau parent (merah) maka anak2nya hitam.
> parent(merah) tidak boleh ketemu anak(merah)

a>dalam fungsi insert di rbt ada beberapa rules seperti:
- setiap node yang baru warnanya merah
- kalau paman (merah) maka parent dan paman di buat jadi warna hitam, lalu grand parent jadi merah
- kalau node pertama selalu merah tapi karena root langsung di ubah ke  hitam
- kalau paman (hitam) maka lakukan rotasi (double / singgle) setelah itu parentnya jadi warna hitamda kedua warna anaknya jadi merah.
note :

double akan di gunakan kalau ketemu bentuk node:
o
 \
  o
 /
o

single
o
 \
  o
     \
      o

b>dalam fungsi delete di rbt ada beberapa rules seperti:
- parent (merah) kalau punya child maka di ambil penggantinya dulu dari child sebelah kiri yang punya nilai terbesar atau child sebelah kanan yang punya nilai terkecil.
- kalau parent (black) dan child (red)  kalau parent delete maka child  akan naik dan jadi hitam
- kalau parent (merah) dan child (hitam) kalau parent delete child naik dan tdak berubah warna
- kalau yang di hapus berwarna hitam maka dilihat dulu dari sibingnya:
  :- jika sibling merah maka tukar warna parent dan sibling dan rotasi dari(doube atau singgle) parent (warna menempel pada node)
  :- jika sibling dan 2 anak nya hitam maka ubah warna sibling jadi merah

->2-3 tree
> adalah suatu tree yang dalam satu nodenya mengandung 1 atau 2 nilai
> kalau dalam 1 node mengandung 1 nilai maka anaknya ada 2 node sedangkan kalau mengandung 2 nilai maka anaknya ada 3 node
> dalam 2-3 tree juga mempunyai 2 fungsi yaitu insert dan delete