AVL-TREE
AVL Tree adalah
Binary Search Tree yang memiliki perbedaan tinggi atau level maksimal 1 antara
subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary
Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat
dipersingkat dan disederhanakan.
 |
AVL tree memiliki
dua metode dalam mengoperasikannya , yaitu:
Inserion
Pada
Insertion terdapat 4 kondisi yang akan terjadi saat ingin memasukkan data pada
struktur data AVL.
- Kasus I (Single Rotation -> LL Rotation).
- Kasus II (Single Rotation -> RR Rotation).
- Kasus III (Double Rotation -> LR Rotation).
- Kasus IV (Double Rotation -> RL Rotation).
Dalam Insertion di AVL Tree,
kita mengenal dengan 2 macam cara untuk melakukan rotasi node, yaitu:
A. SINGLE ROTATION
- Single Rotation : dalam kasus single rotation suatu tree diinsert node baru dan menyebabkan terjadi ketidak seimbangan yang terletak pada posisi root kasus yang sering terjadi pada single rotation yaitu node terdalam terletak pada subtree kiri dan anak kiri node yang harus di seimbangkan kembali (left-left) dan node terdalam terletak pada subtree kanan dari anak kanan node yang harus di seimbangkan kembali(right-right).
- Double Rotation : double rotation digunakan pada kondisi AVL tree diinsert node baru dan menyebabkan terjadi ketidak seimbangan dan node yang baru ditambahkan akan menjadi child dari subtree. Kasus yang sering terjadi pada double rotation adalah node terdalam terletak pada subtree kanan dari anak kiri node yang harus diseimbangkan kembali(right-left) dan node terdalam terletak pada subtree kiri dari anak kanan node yang harus diseimbangkan kembali(left-right).
Cth. gambar diatas melakukan rotasi dari node 22 dan 27
Dan selanjutnya gambar diatas melakukan rotasi antara node
27 dan 30 dikarenakan tree belum stabil.
Deletion
Operasi penghapusan
node sama seperti pada Binary Search Tree, yaitu node yang dihapus digantikan
oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan.
Jika yang dihapus adalah leaf, maka langsung hapus saja. Namun jika node yang
dihapus memiliki child maka childnya yang menggantikannya. Namun setelah
operasi penghapusan dilakukan, cek kembali apakah tree sudah seimbang atau
belum, jika belum maka harus diseimbangkan kembali. Cara menyeimbangkannya pun
sama seperti insertion.
Pada
Deletion terdapat 3 kondisi yang harus diperhatikan agar tidak terjadi
kerusakan atau error pada data.
- Kasus I (Jika node yang akan dihapus tidak memiliki child kiri maupun kanan maka tinggal dihapus).
- Kasus II (Jika node yang akan dihapus hanya memiliki satu child saja maka child tersebut yang akan menggantikan parentnya yang akan dihapus tersebut).
- kasus III (Jika node yang akan dihapus memiliki 2 child yaitu child kiri dann juga child kanan, jika terjadi demikin harus ada kesepakatan yang konsisten untuk memilih pengganti node yang dihapus tersebut. Pilihannya antara child sub tree kiri yang paling kanan dan child sub tree kanan yang paling kiri).
Contoh code AVL-TREE
berserta test casenya:
AVL dengan soal:
* insert: 5,6,7,0,4,3,8
* delete: 3,4,8
* insert: 5,6,7,0,4,3,8
* delete: 3,4,8
B - TREE
B-Tree adalah struktur data yang
memfasilitasi akses data yang lebih cepat yang disimpan dalam memori sekunder
dengan membuat dan menggunakan indeks untuk mengakses sejumlah besar data. Ini
mirip dengan pengunaan indeks dalam buku untuk mengakses konten terkait secara
cepat.
Sebuah BST itu termasuk B-Tree juga lebih tepatnya Two-Way B Tree karena ia mempunyai satu nilai di setiap node dan dua subtree sehingga ia memiliki derajat dua. M-Way Tree adalah generalisasi dari BST dimana M adalah branching factor
2 – 3 Tree
2-3 Tree adalah salah satu tipe
struktur data, dimana setiap node dengan anaknya, memiliki 2 children dan 1
elemen data (2 node) atau 3 children dan 2 elemen data (3 node).
Sifat-sifat 2-3 Tree :
·
Setiap non-leaf terdapat 2-node atau 3-node. Sebuah
2-node berisi satu item data dan memiliki dua anak/children (anak kiri dan anak
tengah). Sebuah 3-node berisi dua item data dan memiliki 3 anak/children (anak
kiri, tengah, dan kanan).
·
Semua leaf berada di level yang sama (level
bawah/bottom level).
·
Semua data yang disimpan akan diurutkan :
o Misalkan A
adalah data yang tersimpan di 2-node. Subtree kiri harus berisi data yang
nilainya lebih kecil dari A. Subtree tengah harus berisi data yang nilainya
lebih besar dari A.
o Misalkan A
dan B adalah data yang tersimpan di 3-node. Subtree kiri harus berisi data yang
nilainya kurang dari A. Subtree tengah berisi nilai antara A dan B, dan subtree
kanan berisi nilai yang lebih dari B.
Contoh :
Gambar diatas merupakan contoh 2 –
node yaitu node yang berisi 1 data dan mempunyai 2 child
Insert
Syarat insertion yaitu:
·
Pertama tentukan dahulu dimana key akan diletakkan
menggunakan algoritma search, key pasti ditempatkan pada node leaf.
·
Jika node tadi adalah 2-node, maka letakkan saja key
tersebut disitu.
·
Jika nodenya adalah 3-node, maka jadikan data tengah
dari key, A, dan B (A dan B adalah data yang sudah ada sebelumnya di dalam
node), menjadi parent, dan split 2 data tersisa menjadi 2 buah 2-node. Cek
apakah parent adalah 3-node, jika iya maka ulangi langkah 3 sampai parent
menjadi 2-node.
Contoh:
Delete
Syarat Deletion yaitu:
·
Tentukan di node mana data yang ingin dihapus
·
Jika berada dalam 3-node, langsung hapus datanya.
·
Jika berada dalam 2-node :
o Jika parent
adalah 3-node : ambil satu data dari parent.
Jika sibling adalah 3-node, ambil salah satu data nya untuk dijadikan data pada parent (agar parent
menjadi 3-node lagi).
Jika sibling adalah 2-node, buat parent menjadi 2-node dengan
menggabungkan (merge) sibling dengan node tempat data didelete.
o Jika parent
adalah 2-node : Jika sibling adalah 3-node, turunkan data parent ke node dan
ambil satu data dari sibling untuk menggantikan parent. Jika sibling 2-node,
gabungkan sibling dengan node yang dihapus datanya.
