Merupakan tree perpanjangan dari extended Binary Tree, dimana external
node pada extended Binary Tree akan digunakan untuk menghitung jarak yang
nantinya akan berguna saat melakukan operasi” pada leftist tree.
s(x) merupakan jarak antara node tersebut dengan extended binary tree terdekat.
Contoh:
Angka berwarna biru merupakan nilai s(x) nya.
Operasi-operasi pada Leftist Tree:
·
Combine
o
Berarti
menggabungkan 2 tree menjadi 1.
o
Cara:
§ Misal kan ada 2 tree yg ingin dicombine, maka compare
root pada kedua tree tsb, yg root nya lbh kecil jadi root, lalu compare root yg
tadi lbh besar dengan anak kanan dr root tree baru, dst.
·
Insert
o
Menggunakan
konsep combine juga.
o
Node baru yg
diinsert itu selalu menjadi tree baru terlebih dahulu sebelum diinsert ke tree.
o
Node baru akan
menjadi anak kanan dari root.
o
Hitung s(x)
nya dimana s(x) di anak kiri harus>=s(x)di anak kanan, bila tidak maka
diswap antara anak kiri dan anak kanan.
·
Delete
o
Yang bisa di
delete hanya rootnya saja spt heap,deap.
o
Setelah root didelete maka aka nada 2 tree yaitu tree
yang sebelumnya menjadi right subtree dr root dan juga yang tadinya menjadi
left subtree dari root.
o
Maka lakukan
kembali proses combine.
Tries
Bukan lah sebuah tree karena memiliki banyak sekali cabang.
Kata trie berasal dari kata retrieval, sesuai dengan kegunaannya.
Digunakan dalam search engine, missal ketika kita mengetik a, maka pada
search engine akan ada suggestion seperti ayam,adi ,dst.
Operasi pada Tries:
·
Insert:
o
Yang lebih
besar akan menjadi anak kanan, sehingga semakin besar huruf awal(ascii) semakin
ke kanan.
o
Kalo masukkin
data yang awal”nya sama missal bar sama barang, awalnya sama-sama bar, maka
Pada huruf r dikasih lambang sebagai penanda bahwa ada kaga bar jg.
·
Delete:
o
Kalo data nya
unik/ga ada cabang maka hapus saja.
o
Kalau key
merupakan awalan spt cth tadi bar dan barang maka pada huruf r lambing nya
hapus saja.
o
Kalau key
merupakan cabang, maka hapus lah cabang nya.
Contoh tries:
Hashing
Hash table adalah sebuah table array dimana kita menyimpan
data.
Biasanya ukuran hash table lebih keccil dibandingkan
dengan kemunkinan string yang diinsert,sehingga bisa / ada kemunkinan
terjaidinya hased key yang sama.
Hash table terdiri dari array nya missal a[], dan juga
value/ data nya.
Ada beberapa cara untuk menentukkan string ini
dimasukkna kemana, dst.
1.
Mid-square
a.
String
nya(ascii) dikuadratkan, kemudian ambil nilai tengah(bisa 1 data, 2 data, dst),
nah hasilnya akan dihjadikkan tempat dimana data tsb diletakkan.
2.
Division:
a.
String
nya(ascii) dimoduluskan dengan sebuah angka(lbh baik bilangan prima agar
hasilnya random dan unik), nah hasilnya menjadi tempat peletakkan string
tersebut.
3.
Folding:
a.
String nya
diubah jadi ascii kemudian ascii dari masing masing huruf ditambahkan antara
satu dan yang lainnya, dan hasilnya dijadikan hash key (tempat peletakkan
string nya).
Delete pada Hash table walaupun setelah di delete dan ternyata data
kosong, maka ga bleh dikoongn begitu saja, tetap harus di kasih tanda
bahwasanya array tersebut sebelumnya
pernah keisi.
Collision adalah suatu kondisi dimana ada string lain nya yang
ditempatkan di tempat yang sudah ada string nya.
Cara mengatasi nya:
1.
Linear
probing: sehingga jika terjadi collision maka string yang baru tersebut ditaruh
di array setelahnya yang masih kosong, tapi cara ini memiliki kelemehan
terlebih ketika array nya penuh maka tidak ada cara lagi, makanya lebih baik
memakai cara yang kedua.
2.
Chaining,
sehingga dengan cara ini jika terjadi collision pada array dibuat linked list,
sehingga sulit untuk kehabisan array dengan cara linked list ini sehingga cara
ini lebih baik digunakan dibandingkan dengan liear probing, contoh : a[0] :
adi->alam->agar
Tidak ada komentar:
Posting Komentar