Minggu, 03 Mei 2020


AVL TREE & B – TREE


AVL – TREE
AVL TREE merupakan kepanjangan dari Adelson Veleskii Landis Tree. AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. Dengan Balanced Binary Search Tree, kita dapat membuat suatu tree dengan tinggi minimum. Untuk menetapkan tingginya, kita dapat menggunakan rumus berikut:
O(log n)
Penerapan struktur data AVL tree digunakan pada Binary Search Tree bertujuan untuk menyeimbangkan tree tersebut, sehingga waktu pencarian dan struktur tree dapat disederhanakan.


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

1.      Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)
2.      Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)
3.      Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)
4.      Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)
T adalah node yang harus diseimbangkan kembali.
4 kasus tersebut dapat diselesaikan dengan melakukan rotasi yaitu:
1.      Kasus 1 dan 2 dengan single rotation
2.      Kasus 3 dan 4 dengan double rotation

Single rotation
Single rotasi (rotasi 1x) dilakukan apabila searah, left-left atau right-right.
Contoh Single Rotation :


Jika suatu Tree diinsert node baru dengan nilai 12, maka akan terjadi ketidak seimbangan dan hal ini terletak pada posisi root.

Double rotation
Double rotasi (rotasi 2x) dilakukan apabila searah, left-right atau right-left.
Contoh Double Rotation :

Gambar diatas merupakan kasus left – right

Delete AVL TREE
Deletion dalam AVL Tree sama seperti teknik deletion dalam binary search tree yang tidak seimbang.
Ada 2 kasus yang biasanya terjadi saat operasi delete dilakukan yaitu :
1.      Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus.
2.      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)

Contoh:



B - TREE
B-Tree merupakan pengembangan dari 2-3 Tree. Sehingga aturan-aturan yang berlaku pun mirip.
Berikut beberapa hal yang perlu diketahui mengenai B-Tree:
·         M adalah jumlah order tree tersebut. (Contoh: order 4 mempunyai maksimal 3 node dan 4 child).
·         Semua "Leaf" berada level yang sama.
·         Setiap Node (kecuali root) punya minimal M/2 children.
·         Root memiliki paling tidak 2 children (bila bukan leaf)
·         Node tanpa leaf dengan k anak mengandung kunci k-1
·         Semua data yang disimpan dalam urutan yang diurutkan.

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 saja 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.
Contoh:


Pada gambar diatas, misalkan yang ingin di delete adalah angka 15 maka langsung di hapus karena 15 merupakan leaf.




Sumber:
https://socs.binus.ac.id/2016/12/20/insertion-avl-tree/
https://socs.binus.ac.id/2017/05/15/deletion-avl-tree/
http://strukturdatatugas.blogspot.com/2016/05/rangkuman-pertemuan-6.html
http://sysbreaker.blogspot.com/2014/05/b-tree-dan-heap-deap-tree.html
http://alecatmadja.blogspot.com/2011/06/2-3-tree-part-1.html
http://nurahman11.blogspot.com/2011/06/deletion-2-3-tree.html
https://www.geeksforgeeks.org/2-3-trees-search-and-insert/




Tidak ada komentar:

Posting Komentar