Rangkuman UAS

Biodata

Nama : Dikky Larson

NIM   : 2301853930

Kelas  : CB01-CL

Dosen : Ferdinand Ariandy Luwinda (D4522)

              Henry Chong (D4460)

AVL Tree

Pendahuluan

Binary Search Tree (BST) yang telah dipelajari selama ini masih memiliki kekurangan. Jika tree yang terbentuk berupa Skewed Tree, maka diperlukan pencarian sebanyak jumlah data yang ada (n). Untuk itu, kita akan menggunakan AVL Tree. AVL Tree merupakan subtipe dari Binary Search Tree. Fyi, AVL Tree diambil dari nama penemunya yaitu Adelson, Velskii dan Landis (sumber:https://www.freecodecamp.org/news/avl-tree-insertion-rotation-and-balance-factor/). Dengan adanya AVL Tree, maka pencarian yang dilakukan dapat dikurangi hingga berjumlah ²log(n).

Ciri-ciri

Konsep tree : https://linked-list-dikky.blogspot.com/2020/03/hashmap-and-binary-tree.html

BST               : https://binustreereview.blogspot.com/2020/03/binary-search-tree.html

AVL Tree memiliki semua ciri yang dimiliki oleh Tree dan BST dengan satu tambahan ciri, yaitu:
- Perbedaan tingkat (depth) dari subtree kiri dan kanan dari setiap node tidak boleh lebih dari satu.

Dengan adanya tambahan syarat tersebut, diperlukan metode balancing (penyeimbangan) depth untuk setiap subtree yang ada, atau dikenal dengan Rotating Method.

Rotating Method

Jika dikelompokkan, ada dua metode rotasi, yaitu:

- Single Rotation (Left(L)/Right(R) Rotation)

- Double Rotation (LR/RL Rotation)

Untuk penggunaannya, dapat disesuaikan sesuai dengan kondisi di bawah ini:

1. Jika node dengan subtree/leaf yang berlebih selalu dalam arah yang sama (segaris) (kanan-kanan atau kiri-kiri) digunakan Single Rotation.

   

   1.1. Single Rotation Case (sumber: binusmaya.ac.id)

2. Jika node dengan subtree/leaf yang berlebih mengalami belok/bengkok di antara link yang ada, dapat digunakan Double Rotation.

   

   2.1. Double Rotation Case Example (sumber: binusmaya.ac.id)

   Step awal menggunakan node S sebagai poros untuk menarik R ke kiri (left rotation).

   

   2.2. Double Rotation Case, step 1. (sumber: binusmaya.ac.id)

   Lalu, node T akan digunakan sebagai poros selanjutnya untuk menarik R ke kanan. (right rotation).

   

   2.3. Double Rotation Case, step 2. (sumber: binusmaya.ac.id)

Untuk mendapatkan gambaran mengenai cara kerjanya dapat melihat link berikut: 

https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

Heap and Trie

Heap

Heap adalah bentuk unik dari balanced binary tree dimana ia akan selalu melakukan pengecekan value node yang dimasukkan dengan parentnya. Sehingga diperoleh hasil yang rapi dan teratur.

Jenis-jenis heap dapat dibagi sesuai dengan value root dan childnya menjadi:

• Min Heap
• Max Heap
• Min-max Heap

I. Min Heap

1.1. Min Heap Example (sumber: https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm)

Min Heap adalah bentuk dimana nilai root-nodenya akan menjadi yang terkecil dari semua node yang ada.

II. Max Heap

1.2. Max Heap Example (sumber: https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm)

Max Heap adalah bentuk dimana nilai root-nodenya akan menjadi yang terbesar dibandingkan dengan semua node yang ada.

III. Min-Max Heap

1.3 Min-Max Heap Example

Min-max Heap adalah gabungan dari Min Heap dan Max Heap. Height genap diisi minimal value, sedangkan height ganjil diisi maximal value atau sebaliknya. 

Trie

Trie adalah tree yang khusus diciptakan untuk menampung string-string keyword. Implementasinya dapat kita jumpai di autocorrect dan word suggestions. Trie menyimpan setiap character dalam keyword sebagai node-node yang saling berhubungan. Rootnya dikosongkan sebagai syarat utama Trie untuk memudahkan pencarian child-node keyword yang ada. Ia juga menggunakan isFinal untuk mengetahui apakah di node tersebut sudah terbentuk kata atau belum.

2.1. Trie Example (sumber: https://www.weheartswift.com/working-trie-data-structure-part-1/)