MORENO

AVL Tree

Pengenalan

Ketinggian dari suatu Binary Search Tree (BST) bisa mencapai n-1, jika BST berbentuk miring. Sementara itu kecepatan berjalannya suatu fungsi pada BST seperti insertion, deletion, searching, dan fungsi lainnya, bergantung sepenuhnya pada tinggi BST tersebut. Jika tinggi suatu BST tidak dibuat seminimal mungkin, maka kecepatan suatu fungsi juga tidak akan optimal / lambat (O(n)). Oleh sebab itu kita memerlukan Balanced Binary Seacrh Tree.

Fungsi dari Balanced BST adalah membuat tinggi dari BST menjardi seminimal mungkin, dengan begitu kecepatan berjalannya suatu fungsi akan optimal (O (log n)). Balanced BST sendiri memiliki beberapa jenis, contohnya: AVL Tree, B-Tree, dll.

Konsep AVL Tree

Pada Balance Tree kita mengenal yang namanya Balance Factor (Faktor keseimbangan), dimana faktor keseimbangan harus sebesar (-1), (0), atau (1). Faktor keseimbangan pada suatu Balanced Tree dihitung dengan rumus:

BalanceFactor(N) = Tinggi(SubTree kiri) - Tinggi(SubTree kanan)

Untuk praktiknya silahkan lihat gambar di bawah ini,

Source: condor.depaul.edu/glancast/383class/docs/lecFeb22.html

*Note: berikutnya dalam blog ini, Balance Factor akan disebut dengan singkatan BF
Pada gambar di atas tiap node telah disertai keterangan tinggi / height masing-masing. Tinggi suatu node dihitung dengan menjumlahkan tinggi maksimal anak dengan satu (maximum child height + 1). Contohnya tinggi dari node 500 adalah 3, karena tinggi maksimal dari anaknya adalah 2 (tinggi node 400) dan kita tambahkan 1. Sementara untuk node yang merupakan daun / leaf tingginya adalah 0, karena tidak memiliki anak.

Setelah mendapat tinggi dari node, barulah kita dapat menghitung BF. Sebagai contoh, kita akan menghitung BF dari node 450, 400, dan 500:

• BF node 450 = 1 - 1 = 0
• BF node 400 = 1 - 2 = -1
• BF node 500 = 3 - 2 = 1

Operasi AVL Tree

Insertion 
Untuk fungsi insertion pada AVL sama saja dengan BST biasa, node baru dimasukkan sebagai leaf. Namun, node baru tersebut bisa saja membuat tree menjadi tidak balanced. Untuk itu kita harus melakukan rebalance, yang dapat kita lakukan dengan cara memutar posisi node atau yang disebut rotation.

Ada 4 kondisi yang harus diperhatikan saat rebalance:
*Note: misalkan X = node yang harus di rebalance

1. Node terendah ada pada SubTree kiri & merupakan anak kiri dari X
2. Node terendah ada pada SubTree kanan & merupakan anak kanan dari X
3. Node terendah ada pada SubTree kanan & merupakan anak kiri dari X
4. Node terendah ada pada SubTree kiri & merupakan anak kanan dari X 
   

Untuk kondisi 1 & 2, kita perlu menerapkan single rotation.
Untuk kondisi 3 & 4, kita perlu menerapkan double rotation.

Jenis rotation:

• LL rotation (Left Rotation) : kesalahan muncul dari anak kanan SubTree kanan
• RR rotation (Right Rotation) : kesalahan muncul dari anak kiri SubTree kiri
• LR rotation (Left-Right): kesalahan muncul dari anak kiri SubTree kanan
• RL rotation (Right-Left) : kesalahan muncul dari anak kanan SubTree kiri

LL Rotation
Perhatikan gambar berikut,

Source: javatpoint.com/ll-rotation-in-avl-tree

Pada gambar diatas, node baru dimasukkan sebagai anak kiri dari T1 pada bagian SubTree kiri. Hal tersebut membuat BF dari "A" menjadi 2, untuk itu kita melakukan LL rotation dimana "A" menjadi anak kanan dari "B". Sementara itu, anak kanan mula-mula (T2) akan kita pindahkan menjadi anak kiri dari "A". Perpindahan tersebut sudah pasti memenuhi BST karena sejak awal T2 merupakan bagian dari SubTree kiri "A", sehingga sudah pasti T2 lebih kecil dari "A".

RR Rotation
Perhatikan gambar berikut,

Source: javatpoint.com/rr-rotation-in-avl-tree

RR rotation memiliki konsep dan cara kerja yang sama dengan LL rotation hanya saja berbeda arah.

LR Rotation
Perhatikan gambar berikut,

Source: javatpoint.com/lr-rotation-in-avl-tree

Pada LR rotation, node "A" akan menggantikan posisi "C". Anak kiri dari "C" akan berpindah enjadi anak kanan dari "B" dan anak kanan "C" akan menjadi anak kiri dari "A".

RL Rotation
Perhatikan gambar berikut,

Source: javatpoint.com/rl-rotation-in-avl-tree

RL rotation memiliki konsep dan cara kerja yang sama dengan LR rotation hanya saja berbeda arah.

Contoh soal:
Insert → 5, 6, 7, 0, 4, 3, 8

Jawab:























Deletion
Untuk fungsi hapus sama saja seperti deletion pada BST biasa. Bedanya, kita harus kembali melakukan pengecekan BF setelah deletion sama seperti insertion.


Contoh soal:
Delete → 3, 4, 8

Jawab:

B-Tree

Pengenalan

B-tree adalah struktur data yang memungkinkan akses data dengan cepat, dimana data disimpan pada memori sekunder dengan membuat dan menggunakan indeks untuk mengakses data yang berukuran besar.

Selama ini, kita telah belajar mengenai BST. Ciri khas dari BST adalah tiap node memiliki paling banyak 2 anak, karena itu BST bisa disebut juga two-way tree. Dari pernyataan tersebut, kita bisa mengelompokkan berbagai jenis tree sebagai M-way tree dimana M merupakan jumlah maksimal anak yang bisa dimiliki suatu node. Sementara B-tree merupakan balanced tree dari M-way tree.

Ciri-ciri B-tree dari suatu M-way tree:

• Setiap node memiliki paling banyak M anak
• Setiap node kecuali root memiliki minimal M/2 anak
• root harus memiliki minimal 2 anak (bila dia bukan leaf)
• Suatu node yang bukan leaf dengan n jumlah anak, harus memiliki keys sebanyak n-1
• Setiap data disimpan secara teratur / sorted
• Setiap leaf berada level yang sama

Operasi 2-3 tree

SearchingFungsi searching pada B-tree sangat mudah, karena data sudah sorted.
Berikut adalah algortima untuk fungsi searching (bahasa C):











Insertion
Aturan memasukkan node masih sama seperti BST, dimana node baru kita masukkan ke salah satu leaf. Bedanya, kita harus mengecek apakah leaf tersebut telah berisikan 2 node atau belum. Bila leaf belum penuh, masukkan node baru ke dalam leaf. Jika leaf sudah penuh, naikkan node tengah pada leaf ke parent dan pisahkan 2 node yang sebelumnya.

Agar lebih mudah dipahami, perhatikan contoh soal berikut:
Insert → 5, 6, 7, 0, 4, 3, 8



Jawab:








Deletion
Untuk deletion perhatikan kondisi berikut:

• Bila key yang ingin dihapus berada pada node x dan merupakan leaf, langsung hapus
• Bila key yang ingin dihapus berada pada node x dan merupakan internal node, maka sesuaikan dengan syarat:
• kalau parent punya 3 node, ambil salah satu isinya. kalau anak punya 3 node, push salah satunya ke parent. Kalau anak hanya 2 node, masukkan salah satu parent ke anak.
• kalau parent punya 2 node. jika anak punya 3 node, ambil salah satu node dari parent dan push satu isi dari anak ke parent. Selain kondisi tersebut, maka gabungkan parent dengan anak.

Contoh soal:
Delete → 3, 4, 8

Jawab:




Peraturan untuk fungsi pada 2-3 tree berlaku juga pada 4-5 tree, Namun batasan untuk isi suatu node lebih besar.