Final Rangkuman

Rangkuman Final

Nama: Michael Susilo

NIM: 2301876000

Kelas: CB01 CL

Lecturer : Ferdinand Ariandy Luwinda (D4522) , Henry Chong (D4460)

AVL Tree

AVL Tree merupakan lanjutan dari binary search tree. AVL Tree sendiri bertujuan untuk menyeimbangkan binary search tree. dimana kadang-kadang binary search tree akan membentuk pohon yang tidak seimbang, sehingga untuk menyempurnakan digunakan lah AVL Tree.

* untuk mengetahuinya bahwa sudah seimbang , binary search tree nya harus memiliki perbedaan tinggi /  level / kedalaman maksimal 1. 

* untuk mencari tau kedalamanny adalah di hitung dari node paling bawah ke atas. lalu node kiri dan kanan dibandingkan yaitu yang kedalamanya lebih besar dikurang kedalamanya lebih kecil, jika lebih dari satu artinya Tree nya tidak seimbang sehingga harus di seimbangkan dengan AVL Tree.

Insertion

terdapat 2 cara untuk insert / menyeimbangkanya, yaitu;

1. Single Rotation

2. Double Rotation

1. Single Rotation

cara mengeceknya adalah dengan melihat node yang menjadi menyebab masalah nya , setelah itu kita ambil jalur nya sampai ke root. jika garisnya searah( cth: kiri -> kiri) artinya kita bisa melakukan single rotation untuk menyeimbangkan tree nya.

cara menyeimbangkanya adalah

kita bisa bayangkan seperti katrol , dimana porosnya adalah rootnya. setelah itu jika berat dikiri maka kita tarik ke kanan, maksudnya adalah rootnya akan kita pindahkan menjadi anak kanan dan anak kiri kita ubah menjadi root, maka anak kiri dari anak kiri akan menjadi anak kiri yang baru.

jika di anak kiri terdapat anak kanan, maka anak kananya akan kita pindahkan dengan cara meng insert ulang.

cth: single rotation

2. Double Rotation

cara mengeceknya yaitu dengan melihat node yang menjadi penyebab masalah. lalu kita ambil jalur node tersebut ke root ,jika garisnya belok atau tidak searah (cth: kiri -> kanan) maka kita akan melakukan double rotation untuk menyeimbangkanya.

dinamakan double rotation karena pengerjaanya dilakukan 2 step

* 1st step

setelah kita mendapatkan garis jalan dari node yang bermasalah ke root. kita akan mengambil 3 node atau 2 garis . node ke3 dari atas akan kita pindahkan menjadi anak kiri atau anak kanan dari root (kiri / kanan menyesuaikan) dan node ke2 dari atas sebelumnya akan kita ubah menjadi anak dari node ke 3 yang telah kita pindahkan.

kesimpulannya kita akan mengubah posisi node ke 3 menjadi anak dari root , yang bertujuan membuat jalur node bermasalah ke root menjadi searah.

cth: double rotation

setelah searah kita akan melakukan single rotation untuk menyelesaikannya.

Deletion

untuk delete atau menghapus node pada avl tree adalah dengan menghapus node nya seperti biasa, setelah node di hapus baru kita cek apakah tree teresebut seimbang atau tidak.

jika tidak seimbang kita cek , apakah kita harus melakukan double atau single rotation untuk menyeimbangkanya.

Heaps & Tries

*Heaps

heaps adalah suatu data structure yang merupaka complete binary tree.

haeps sendiri menggunakan array. setiap melakukan insert dimulai dari index 1.

untuk mengetahui letaknya(index) terdapat rumus:

parent = myIndex / 2

left child = myIndex * 2

right child = (myIndex * 2) + 1

heaps terbagi menjadi 3:

1. Min Heaps

2. Max Heaps

3. Min-Max Heaps

1. Min Heaps

min heaps berarti adalah suatu binary tree dimana root / parentnya nya harus lebih kecil (minimum) dari pada child / anak-anak nya.

*Insert

untuk insert di Min Heaps adalah dengan memasukan data ke array secara berurut. lalu harus di bandingkan agar yang lebih kecil menjadi parent dan yang lebih besar menjadi child.

1. masukan data ke node sesuai urutan (dari parent -> left child -> right child ) 

2. data yang baru masuk di bandingkan dengan parentnya

-jika lebih kecil maka data akan di naikan ke atas (swap dengan parentnya) [lakukan sampai ke root]

-jika lebih besar maka tetap di posisinya

*delete 

untuk delete di Min Heaps adalah data yang terakhir masuk ( di index terakhir) di swap dengan data yang ingin di delete. lalau data yang telah di swap akan di cek dengan anaknya agar sesuai dengan konsep Min heaps (yang kecil menjadi parent).

1. data di index terakhir (data yang terakhir masuk) di swap dengan data yang ingin di delete.

2. data yang telah di swap di bandingkan dengan anaknya (anak kiri dan kanan) apakah lebih kecil atau lebih besar.

-jika lebih kecil dari kedua anaknya maka tetap di posisi.

-jika lebih besar dari anaknya maka (step3);

3.anak kiri dan kanan di cek nya yang mana yang lebih kecil. ketika sudah dapat data yang lebih kecil , maka data nya di swap dengan anak nya yang lebih kecil. [secara rekursif] (jadi anaknya di cek lagi dengan cucunya, dst)

2. Max Heaps

max heap adalah suatu binary tree dimana rootnya lebih besar (maximum) dari pada child atau anak-anaknya.

*insert

untuk insert di Max Heaps adalah dengan memasukan data ke array secara berurut. data harus di bandingkan agar data yang lebih besar menjadi root/parent dan data yang lebih kecil menjadi anak.

1. masukan data ke node sesuai urutan (dari parent -> left child -> right child ) 

2. data yang baru masuk di bandingkan dengan parentnya

-jika lebih besar maka data akan di naikan ke atas (swap dengan parentnya) [lakukan sampai ke root]

-jika lebih kecil maka tetap di posisinya

*delete

untuk delete di max Heaps adalah data yang terakhir masuk ( di index terakhir) di swap dengan data yang ingin di delete. lalau data yang telah di swap akan di cek dengan anaknya agar sesuai dengan konsep max heaps (yang besar menjadi parent).

1. data di index terakhir (data yang terakhir masuk) di swap dengan data yang ingin di delete.

2. data yang telah di swap di bandingkan dengan anaknya (anak kiri dan kanan) apakah lebih kecil atau lebih besar.

-jika lebih besar dari kedua anaknya maka tetap di posisi.

-jika lebih kecil dari anaknya maka (step3);

3. anak kiri dan kanan di cek nya yang mana yang lebih besar. ketika sudah dapat data yang lebih besar, maka data nya di swap dengan anak nya yang lebih besar. [secara rekursif] (jadi anaknya di cek lagi dengan cucunya, dst)

3. Min-Max Heaps

min-max heaps artinya adalah gabungan min heaps dan max heaps. 

maksunya adalah parentnya min heaps (data yang kecil) anaknya max heaps (data yang lebih besar)

min dan max heaps ini selalu berurut , jadi level genap menjadi min heaps , level ganjil max heaps.

*Insert

1. masukan data ke node sesuai urutan (dari parent -> left child -> right child ) 

2. data yang baru masuk di bandingkan dengan parentnya, lalu kita cek lebih besar atau lebih kecil ( kita harus ngecek parentnya min heaps atau max heaps) , lalu kita bisa melihat sesuai aturan heaps nya.

*delete

1. data di index terakhir (data yang terakhir masuk) di swap dengan data yang ingin di delete.

2. data yang telah di swap akan di cek dengan grand childnya (karena memiliki jenis heaps yang sama) yang mana yang lebih kecil (krn min heaps) setelah dapat lalu di swap.

3. setelah itu di cek lagi dengan parentnya apakah sdh sesuai dengan konsep max heaps.

Tries

tries adalah suatu konsep data structure yang menyimpan chracthers . berfungsi untuk mencari kata dengan lebih mudah dan hemat memori, karena terdapat cabang-cabang  di setiap huruf.

di setiap node memiliki banyak cabang yang menghubungkan satu huruf dengan huruf lainya untuk membentuk suatu kata yang berbeda.

di cth tries ini dapat membentuk kata; "roll" , "round" , "to" , "tour" .

cth dari tries.