HEAP & TRIES

I. PENGERTIAN HEAP

Heap merupakan sebuah complete binary tree yang memiliki beberapa sifat tertentu.

Ada 3 jenis :

1. Min-Heap

Root paling atas memiliki nilai terkecil.

2. Max-Heap

Kebalikan dari min-heap. Root paling atas memiliki nilai terbesar.

3. Min-Max Heap

Kondisi antar level bergantian antara minimum dan maximum. Dimulai dengan level paling atas (0) bernilai paling minimum dan level 1 bernilai paling maksimum.

II. INSERTION

1. Min-Heap

1. Insert nilai baru sebagai node terakhir dari heap.
2. Bandingkan nilai baru yang diinsert dengan parent-nya. Jika lebih kecil dari parent, maka tukar nilainya.
3. Swap dihentikan jika nilai parent-nya lebih kecil dari current node atau jika current node adalah root.

2. Max-Heap

Cara menginsert sebuah nilai baru pada Max-Heap sama dengan Min-Heap. Perbedaannya adalah nilai parent lebih besar daripada nilai child.

3. Min-Max Heap

1. Insert nilai baru sebagai node terakhir dari heap.
2. Jika nilai baru ada pada Min-Level dan parent dari nilai  baru  lebih kecil dari nilai yang diinsert, maka nilai baru ditukar dengan parentnya.
3. Jika nilai baru ada pada Max-Level dan parent dari nilai baru lebih besar dari nilai yang diinsert, maka nilai baru ditukar dengan parentnya.
4. Upheapmin : Bandingkan nilai dari current node dengan nilai dari grand-parent. Jika nilai dari current node lebih kecil dari parent-nya, maka keduanya ditukar.
5. Upheapmax : Bandingkan nilai dari current node dengan nilai dari grand-parent. Jika nilai dari current node lebih besar dari parent-nya, maka keduanya ditukar.

III. PENGERTIAN TRIES

Tries adalah tree struktur data terstruktur yang digunakan untuk menyimpan array asosiatif, biasanya string.

Root berisi kosong dan setiap node berisi 1 huruf.

Kata-kata yang ada pada tries diatas : ALGO, API, BOM, BOS, BOSAN, BOR.

Referensi :
https://mikesebastian.weebly.com/blog/category/struktur-data
http://prillysia.blog.binusian.org/tag/tries/






Dibuat oleh :
Livia Leonita - 2301905726
CB 01

AVL TREE

I. PENGERTIAN

AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi atau level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree dibuat untuk menyeimbangkan Binary Search Tree. AVL Tree dapat membuat bentuk tree lebih simple atau sederhana dan juga waktu pencarian lebih efektif.

II. OPERASI INSERT

Insertion adalah operasi menambahkan node pada tree.

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

misalkan : T adalah node yang harus diseimbangkan

1. Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T

2. Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T

3. Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T

4. Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T

Kasus-kasus di atas dapat diselesaikan dengan cara rotasi. Rotasi ada 2 yaitu: single rotation dan double rotation. Single rotation untuk menyelesaikan kasus 1 dan 2. Double rotation untuk menyelesaikan kasus 3 dan 4.

• Single rotation

• Double rotation

II. OPERASI DELETE

Operasi delete adalah menghapus atau menghilangkan node dari tree. Ada 2 tipe delete yaitu :

1. Jika node yang ingin dihapus merupakan leaf atau node yang tidak mempunyai anak, maka node tersebut dapat langsung di delete.

2. Jika node yang ingin dihapus memiliki anak seperti terletak pada 4 kasus dibawah berikut, maka penghapusannya harus di cek kembali agar tree dapat seimbang dan perbedaan tinggi atau levelnya maksimal 1.

4 Kasus yang dapat terjadi pada operasi delete, jika node yang ingin didelete memiliki anak:

1. Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri

2. Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan

3. Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri

4. Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan

Referensi :

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

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

Dibuat oleh :

Livia Leonita - 2301905726

CB01