Nama: Vincent Fanditama Wijaya
NIM: 2301885983
Hari, tanggal: Selasa, 9/6/2020
Kelas: CB01-CL
Lecturer: Ferdinand Ariandy Luwinda (D4522) dan Henry Chong ( D4460 )
Lecturer kelas kecil LB08: Diana (D4458)
AVL Tree
NIM: 2301885983
Hari, tanggal: Selasa, 9/6/2020
Kelas: CB01-CL
Lecturer: Ferdinand Ariandy Luwinda (D4522) dan Henry Chong ( D4460 )
Lecturer kelas kecil LB08: Diana (D4458)
Jadi pada pertemuan tanggal 28 April 2020, kelas kami membahas tentang AVL Tree. Penamaan AVL Tree berasal dari 2 penemu nya yang bernama "Adelson-Veleskii dan Landis". Fungsi utama dari penerapan konsep AVL tree adalah untuk menyeimbangkan BST (Binary Search Tree). Tingkat kekompleksan pengunaan AVL Tree hingga log n, dimana BST hanya sampai n saja.
Ciri-ciri AVL Tree mirip seperti BST, hanya dia memerlukan keseimbangan antara subtree kiri dengan kanan, dengan toleransi max selisih kanan-kiri nya =1.
Jika terdapat ketidakseimbangan antara subtree kanan dan subtree kiri yang melebihi selisih 1, maka kita perlu melakukan rebalance, bisa hanya single rotation, maupun double rotation
untuk melakukan pengukuran penyeimbangan, diperlukan pencarian node yang paling terdalam di subtree kiri vs subtree kanan
1. Untuk operasi insertion pada AVL Tree:
1. pertama masukkan key baru seperti biasa di BST
2. Jika tidak seimbang antara subtree kiri dengan subtree kanan, maka bisa dilakukan rebalanced, seperti ilustrasi dibawah
Seperti kita lihat, ketika kita memasukkan key "4", maka terjadi ketidakseimbangan di node key 3, maka perlu dilakukan penggeseran node di node "3"
Penyeimbangan, dilakukan pada node yang paling terdalam
Ketidaksesuaian pada subtree bagian kiri dan anak subtree kiri terdalam DAN Ketidaksesuaian pada subtree bagian kanan dan anak subtree kanan terdalam, dapat dilakukan hanya menggunakan single rotation. (paling mudah, cari yang paling terdalam dan lurus tidak bengkok)
Sedangkan, Ketidaksesuaian pada subtree bagian kiri dan anak subtree kanan terdalam DAN Ketidaksesuaian pada subtree bagian kanan dan anak subtree kiri terdalam, dapat dilakukan menggunakan double rotation. (paling mudah, cari yang paling terdalam dan terlihat cabangnya bengkok)
Contoh ilustrasi single rotation (ketika new key 12, barusan dimasukkan kedalam tree)
Terlihat di node 30 terjadi ketimpangan, antara subtree kanan dan subtree kiri, oleh sebab itu, subtree yang terpanjang/terdalam digeser ke arah berlawanan, dan tiap anak node "22" yang terkena geser (27 dan 29), maka diperlukan penataan ulang juga dari atas.
Contoh ilustrasi double rotation (ketika new key 26, barusan dimasukkan kedalam tree)
Rotasi pertama:
Terjadi ketimpangan pada node 30, dimana node terdalam berada di cabang node 22 (cabang bengkok) , maka pertama tama diperlukan penarikan node 27 ke arah berlawanan. Lalu anak dari node 27, perlu penataan ulang dari atas.
Rotasi kedua:
Setelah itu, terjadi ketimpangan di node 30 sebelah kiri, maka perlu ditarik node 27 ke arah berlawanan, dan tiap anak dari node 27 (29), ditata ulang dari atas.
2. Untuk operasi delete pada AVL tree:
1. Node yang boleh di delete, adalah node yang hanya memiliki 1 anak saja atau 0 anak
2. Jika tidak seimbang antara subtree kiri dengan subtree kanan, maka bisa dilakukan rebalanced, seperti insertion balanced (single rotation maupun double rotation).
Untuk simulasi dan lebih jelasnya, bisa dicoba sendiri menggunakan simulator:
https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
Sekian, ringkasan pada pertemuan pembelajaran kali ini. Terima Kasih.
Ciri-ciri AVL Tree mirip seperti BST, hanya dia memerlukan keseimbangan antara subtree kiri dengan kanan, dengan toleransi max selisih kanan-kiri nya =1.
Jika terdapat ketidakseimbangan antara subtree kanan dan subtree kiri yang melebihi selisih 1, maka kita perlu melakukan rebalance, bisa hanya single rotation, maupun double rotation
untuk melakukan pengukuran penyeimbangan, diperlukan pencarian node yang paling terdalam di subtree kiri vs subtree kanan
1. Untuk operasi insertion pada AVL Tree:
1. pertama masukkan key baru seperti biasa di BST
2. Jika tidak seimbang antara subtree kiri dengan subtree kanan, maka bisa dilakukan rebalanced, seperti ilustrasi dibawah
Seperti kita lihat, ketika kita memasukkan key "4", maka terjadi ketidakseimbangan di node key 3, maka perlu dilakukan penggeseran node di node "3"
Penyeimbangan, dilakukan pada node yang paling terdalam
Ketidaksesuaian pada subtree bagian kiri dan anak subtree kiri terdalam DAN Ketidaksesuaian pada subtree bagian kanan dan anak subtree kanan terdalam, dapat dilakukan hanya menggunakan single rotation. (paling mudah, cari yang paling terdalam dan lurus tidak bengkok)
Sedangkan, Ketidaksesuaian pada subtree bagian kiri dan anak subtree kanan terdalam DAN Ketidaksesuaian pada subtree bagian kanan dan anak subtree kiri terdalam, dapat dilakukan menggunakan double rotation. (paling mudah, cari yang paling terdalam dan terlihat cabangnya bengkok)
Contoh ilustrasi single rotation (ketika new key 12, barusan dimasukkan kedalam tree)
Terlihat di node 30 terjadi ketimpangan, antara subtree kanan dan subtree kiri, oleh sebab itu, subtree yang terpanjang/terdalam digeser ke arah berlawanan, dan tiap anak node "22" yang terkena geser (27 dan 29), maka diperlukan penataan ulang juga dari atas.
Contoh ilustrasi double rotation (ketika new key 26, barusan dimasukkan kedalam tree)
Rotasi pertama:
Terjadi ketimpangan pada node 30, dimana node terdalam berada di cabang node 22 (cabang bengkok) , maka pertama tama diperlukan penarikan node 27 ke arah berlawanan. Lalu anak dari node 27, perlu penataan ulang dari atas.Rotasi kedua:
Setelah itu, terjadi ketimpangan di node 30 sebelah kiri, maka perlu ditarik node 27 ke arah berlawanan, dan tiap anak dari node 27 (29), ditata ulang dari atas.
2. Untuk operasi delete pada AVL tree:
1. Node yang boleh di delete, adalah node yang hanya memiliki 1 anak saja atau 0 anak
2. Jika tidak seimbang antara subtree kiri dengan subtree kanan, maka bisa dilakukan rebalanced, seperti insertion balanced (single rotation maupun double rotation).
Untuk simulasi dan lebih jelasnya, bisa dicoba sendiri menggunakan simulator:
https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
Sekian, ringkasan pada pertemuan pembelajaran kali ini. Terima Kasih.
Heaps and Tries
Heap adalah binary tree yang terdiri dari berbagai macam jenis heap.
Macam-macam heap:
1. Min Heap (ascending order)
2. Max Heap (descending order)
3. Min-Max Heap
Aturan Heap mirip dengan aturan binary tree biasa, tetapi ditambah spesifik, seperti:
Min heap: memiliki ciri root nya merupakan bilangan terkecil. Heap biasanya menggunakan implementasi array yang dimulai dari index ke 1 (root) untuk mempermudah perhitungan rumus.
Contoh ilustrasi:
Terlihat angka 7 merupakan nilai minimum dan diletakkan di root
Bentuk Array dan index dr tree disamping
7, 15, 10, 18, 28, 17, 12, 21, .....
1, 2, 3, 4, 5, 6, 7, 8, ....
Rumus untuk mencari f(x), dimana x merupakan current node:
- Parent(x) = x/2
- Anak kiri(x) = 2*x
- Anak kanan(x) = 2 *x+1
Jadi, pembuktiannya:
1. misalkan kita mau mencari parent dari 15. 15 merupakan index ke 2. Maka 2/2= 1. Jadi parent dari 15 adalah index ke 1 yaitu 7
2. misalkan kita mau mencari anak kanan dari 15. 15 merupakan index ke 2. Maka 2*2 + 1 = 5. Jadi anak kanan dari 15 adalah index ke 5 yaitu 28.
Nilai min dari min-heap selalu berada di index pertama atau di root
Cara push heap di min-heap adalah dengan metode push-uphead. Isi dari index paling akhir. Lalu swap (tukar) dengan parent nya jika value childnya lebih kecil. Tukar terus sampai value anaknya nya lebih besar daripada parent nya atau sampai dengan root (index ke 1).
Cara delete di min-heap adalah dengan membuang root nya saja (value terkecil/index ke 1). Setelah selesai delete, maka tukar root dengan index terakhir dari heap. Lalu sesuaikan lagi nilai minimum root dengan cara tukar dengan child bagian kanan/kiri nya (downheap root) sampai nilai paling kecil kembali ke root nya.
Max Heap: memiliki ciri root nya merupakan bilangan terbesar. Heap biasanya menggunakan implementasi array yang dimulai dari index ke 1 (root) untuk mempermudah perhitungan rumus.
Cara push dan delete nya sama dengan min-heap, tapi dia fokus dari besar-kecil.
Min-Max Heap: Tiap kedalaman genap selalu berisi nilai min dari anak-anaknya. Sedangkan tiap kedalaman ganjil selalu berisi nilai max dari anak-anaknya.
Contoh ilustrasinya:
Nilai Minimum selalu berada di rootnya. Sedangkan nilai max selalu berada di salah satu anak dari root nya (baik kanan atau kiri nya) (level 1).
Insertion selalu dari index paling terakhir. Dan intinya adalah baris yang min level dibandingkan dengan baris yang min level atasnya. Sedangkan baris yang max level dibandingkan dengan max level atasnya.
Jika node baru berada di kedalaman genap (min):
Jika parent nya lebih kecil dari node barunya maka tukar dan berlakukan upheapmax
Jika parent nya lebih besar dari node barunya maka berlakukan upheapmin
Jika node baru berada di kedalaman ganjil (max):
Jika parent nya lebih besar dari node barunya maka tukar dan berlakukan upheapmin
Jika parent nya lebih kecil dari node barunya maka berlakukan upheapmax
Upheapmin
Bandingkan nilai node saat ini dengan nilai grand-parent-nya. Jika nilai node saat ini lebih kecil dari nilai induknya daripada swap nilai-nilai mereka dan teruskan sampai grand-parent node.
Upheadmax
Bandingkan nilai node saat ini dengan nilai grand-parent-nya. Jika nilai node saat ini lebih besar dari nilai induknya daripada swap nilai-nilai mereka dan teruskan sampai grand-parent node.
Delete hanya bisa dilakukan pada nilai max dan nilai min
Jika melakukan delete pada nilai minimum atau maximum, maka gantikan nilai root dengan element di index terakhir (genap/ganjil). Mirip caranya dengan min heap.
TRIES adalah tree yang tiap setiap vertex nya mempresentasikan 1 kata (string)
Ciri-ciri nya:
1. Root nya selalu berupa karakter NULL (kosong) (takde isi)
2. Setiap vertex nya mempresentasikan 1 kata (string) yang terdiri dari kumpulan char
3. Ada boolean yang menyatakan end. (Kata itu sudah berakhir)
Contoh ilustrasinya:
Contoh aplikasi Tries:
1. Spell checker
2. Autocomplete/predictive text
3. Dictionary searching
Sekian pertemuan minggu ini.
Macam-macam heap:
1. Min Heap (ascending order)
2. Max Heap (descending order)
3. Min-Max Heap
Aturan Heap mirip dengan aturan binary tree biasa, tetapi ditambah spesifik, seperti:
Min heap: memiliki ciri root nya merupakan bilangan terkecil. Heap biasanya menggunakan implementasi array yang dimulai dari index ke 1 (root) untuk mempermudah perhitungan rumus.
Contoh ilustrasi:
Terlihat angka 7 merupakan nilai minimum dan diletakkan di root
Bentuk Array dan index dr tree disamping
7, 15, 10, 18, 28, 17, 12, 21, .....
1, 2, 3, 4, 5, 6, 7, 8, ....
Rumus untuk mencari f(x), dimana x merupakan current node:
- Parent(x) = x/2
- Anak kiri(x) = 2*x
- Anak kanan(x) = 2 *x+1
Jadi, pembuktiannya:
2. misalkan kita mau mencari anak kanan dari 15. 15 merupakan index ke 2. Maka 2*2 + 1 = 5. Jadi anak kanan dari 15 adalah index ke 5 yaitu 28.
Nilai min dari min-heap selalu berada di index pertama atau di root
Cara push heap di min-heap adalah dengan metode push-uphead. Isi dari index paling akhir. Lalu swap (tukar) dengan parent nya jika value childnya lebih kecil. Tukar terus sampai value anaknya nya lebih besar daripada parent nya atau sampai dengan root (index ke 1).
Cara delete di min-heap adalah dengan membuang root nya saja (value terkecil/index ke 1). Setelah selesai delete, maka tukar root dengan index terakhir dari heap. Lalu sesuaikan lagi nilai minimum root dengan cara tukar dengan child bagian kanan/kiri nya (downheap root) sampai nilai paling kecil kembali ke root nya.
Max Heap: memiliki ciri root nya merupakan bilangan terbesar. Heap biasanya menggunakan implementasi array yang dimulai dari index ke 1 (root) untuk mempermudah perhitungan rumus.
Cara push dan delete nya sama dengan min-heap, tapi dia fokus dari besar-kecil.
Min-Max Heap: Tiap kedalaman genap selalu berisi nilai min dari anak-anaknya. Sedangkan tiap kedalaman ganjil selalu berisi nilai max dari anak-anaknya.
Contoh ilustrasinya:
Nilai Minimum selalu berada di rootnya. Sedangkan nilai max selalu berada di salah satu anak dari root nya (baik kanan atau kiri nya) (level 1).
Insertion selalu dari index paling terakhir. Dan intinya adalah baris yang min level dibandingkan dengan baris yang min level atasnya. Sedangkan baris yang max level dibandingkan dengan max level atasnya.
Jika node baru berada di kedalaman genap (min):
Jika parent nya lebih kecil dari node barunya maka tukar dan berlakukan upheapmax
Jika parent nya lebih besar dari node barunya maka berlakukan upheapmin
Jika node baru berada di kedalaman ganjil (max):
Jika parent nya lebih besar dari node barunya maka tukar dan berlakukan upheapmin
Jika parent nya lebih kecil dari node barunya maka berlakukan upheapmax
Upheapmin
Bandingkan nilai node saat ini dengan nilai grand-parent-nya. Jika nilai node saat ini lebih kecil dari nilai induknya daripada swap nilai-nilai mereka dan teruskan sampai grand-parent node.
Upheadmax
Bandingkan nilai node saat ini dengan nilai grand-parent-nya. Jika nilai node saat ini lebih besar dari nilai induknya daripada swap nilai-nilai mereka dan teruskan sampai grand-parent node.
Delete hanya bisa dilakukan pada nilai max dan nilai min
Jika melakukan delete pada nilai minimum atau maximum, maka gantikan nilai root dengan element di index terakhir (genap/ganjil). Mirip caranya dengan min heap.
TRIES adalah tree yang tiap setiap vertex nya mempresentasikan 1 kata (string)
Ciri-ciri nya:
1. Root nya selalu berupa karakter NULL (kosong) (takde isi)
2. Setiap vertex nya mempresentasikan 1 kata (string) yang terdiri dari kumpulan char
3. Ada boolean yang menyatakan end. (Kata itu sudah berakhir)
Contoh ilustrasinya:
Contoh aplikasi Tries:
1. Spell checker
2. Autocomplete/predictive text
3. Dictionary searching
Sekian pertemuan minggu ini.
Tidak ada komentar:
Posting Komentar