Final Review

Chrysanti Anastasya Silaban

2301877464

Kelas : CB01

Lecture : Henry Chong (D4460) dan Ferdinand Ariandy Luwinda(D4522)

apa itu avl tree?

sebuah pohon biner terurut yang dapat menyeimbangkan dirinya sendiri. Pada sebuah pohon AVL, tinggi dari dua anak sub pohon dari simpul apapun memiliki perbedaan paling besar 'satu'. 

AVL Tree ditemukan oleh Adelson-Velskii dan Landis

Lookup, penyisipan (insertion), dan penghapusan (deletion) semuanya memerlukan O(logn) kali dalam kasus biasa dan kasus terburuk. 

Penambahan (additions) dan penghapusan membutuhkan pohon tersebut untuk menyeimbangkan kembali dirinya melalui rotasi pohon satu kali atau lebih.

cara perurutannya yaitu sebelah kiri nilai yang paling rendah sedangkan sebelah kanan nilai paling besar dari nilai utamanya (root),left<root<right.

Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu :

anggap T adalah node yang harus diseimbangkan kembali

– Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)

– Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)

– Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)

– Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)

Ke-4 kasus tersebut dapat diselesaikan dengan melakukan rotasi

– dengan single rotation

– Kasus 3 dan 4 dengan double rotation

ini adalah unbalanced tree.

setelah di rebalance menjadi AVL Tree

Ada 2 kasus yang biasanya terjadi saat operasi delete dilakukan, yaitu :

– Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus.

• Jika node yang akan dihapus memiliki anak, maka proses penghapusannya harus di cek kembali untuk menyeimbangkan Binary Search Tree dengan perbedaan tinggi / level maksimal 1.
• anggap T adalah node yang harus diseimbangkan kembali
  – Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)
  – Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)
  – Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)
  – Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)
  

Berikut contoh dalam menghapus node AVL Tree, terdapat AVL Tree yang kemudian di hapus node 60. Dengan gambaran sebagai berikut :

Yang akan menggantikan posisi node 60 adalah node 55. Akan terjadi ketidak seimbangan. Dengan tampilan sebagai berikut :

Maka akan dilakukan single rotation pada node 55 dengan kasus ketidak seimbangan pada kasus no. 2. Dengan tampilan setelah dilakukan single rotation sebagai berikut :

Ketika sudah dilakukan single rotation dan dilakukan kembali perbedaan tinggi / level maksimal 1 ternyata terdapat ketidak seimbangan yang terjadi. Sehingga diperlukan double rotation dengan kasus no. 4. Sehingga hasil dari rotasi yang dilakukan adalah sebagai berikut :

HEAP

Nah, jadi guys Heap adalah complete binary tree (bukan binary search tree) yang mempunyai properties sebagai berikut:

Min Heap terdiri atas Setiap node(parents) lebih kecil dari masing-masing childnya

Root merupakan node paling kecil, sedangkan node terbesar terletak pada leaf node

min heap

Max Heap terdiri atas Setiap node(parents) lebih besar dari masing-masing childnya

Root merupakan node paling besar, sedangkan node terkecil terletak pada leaf node

max heap

Setelah itu ada juga min-max heap.

Min-max heap adalah Heap dengan Min heap pada level ganjil(1,3,5 dst) dan Max heap pada level genap(2,4,6,8,dst)

min max heap

Heap bisa diimplementasi dengan array maupun dengan linked list. Aplikasi heap merupakan menjadi berikut:

Priority Queue

1. Selection algorithm
2. Dijkstra's Algorithm
3. Prim Algorithm

Implementasi heap memakai array yaitu Array dimulai menggunakan indeks ke 1
Rumus umum pelaksanaan heap dengan array (x adalah current node):

• Parent(x): x/2
• Left-child(x): 2*x
• Right-Child(x): 2*x+1

Operasi pada Min Heap

• Find-Min

Minimum node terletak pada root

• Insertion pada Min-heap

Insert node selalu berurutan berdasarkan level paling rendah menggunakan urutan left ke right

New node selalu menjadi leaf node

Sesuikan sesuai heap properties secara rekursif

• Deletion-Min dalam Min-Heap

Node yg dihapus selalu root karena merupakan node paling kecil, kemudian diganti dengan node yang paling terakhir di insert

Sesuaikan dengan heap properties secara rekursif

Operasi pada Max Heap

Insertion dan deletion untuk Max heap, hanya saja disesuakan menggunakan properties Max-Heap

• Min-Max Heap

Insert node sinkron urutan, lalu cek upheap lalu sesuaikan dengan properties level.

Umumnya dilakukan penyesuaian rekursif dengan urutan menjadi berikut:

1. Parent
2. Grand Parent

• Deletion selalu dilakukan dalam root, kemudian sesuaikan menggunakan downheap sesuai properties

Umumnya dilakukan penyesuaian secara rekursif dengan urutan sebahai berikut:

1. Grand child
2. Child ( grand child disesuaikan menggunakan parentnya)

TRIES

Trie adalah struktur data pencarian informasi yang efisien.

 Menggunakan Trie, kompleksitas pencarian dapat dibawa ke batas optimal (panjang kunci). Jika kita menyimpan kunci dalam BST, BST yang seimbang akan membutuhkan waktu yang proporsional dengan M * log N, di mana M adalah panjang string maksimum dan N adalah jumlah kunci dalam pohon. Dengan menggunakan Trie, kita dapat mencari kunci dalam waktu O (M).

tries

Jadi kesimpulannya Tries adalah tree yang dilakukan buat menyimpan array asosiatif

Properties pada tries terdiri atas:

1. Setiap vertex/node merepresentasikan satu huruf
2. Root merepresentasikan karakter kosong
3. Aplikasi pada trees adalah fitur auto-complete yg ada pada web-browser

SEKIAN DAN TERIMA KASIH

credit:

https://www.geeksforgeeks.org/binary-heap/
https://en.wikipedia.org/wiki/Min-max_heap
https://www.geeksforgeeks.org/minimum-element-in-a-max-heap/
https://www.geeksforgeeks.org/max-heap-in-java/
https://www.geeksforgeeks.org/trie-insert-and-search/

https://socs.binus.ac.id/2016/12/20/insertion-avl-tree/

https://socs.binus.ac.id/2017/05/15/deletion-avl-tree/