AVL Tree & B-Tree

AVL Tree
AVL Tree merupakan salah satu jenis BST (binary Search Tree) yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree dibentuk untuk menyeimbangkan Binary Search Tree, supaya waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.

(Sumber: https://medium.com/@aksh0001/avl-trees-in-python-bc3d0aeb9150)

Metode penyeimbang ini dibagi menjadi 4 metode berdasarkan kondisi tree setelah melakukan insert, yaitu :

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)

*T adalah node yang harus diseimbangkan kembali.

B-Tree
B-tree adalah suatu metode untuk menyimpan dan menemukan suatu file (disebut juga records atau keys) dalam suatu database. Algoritma b-tree meminimalkan jumlah dari media yang harus dilalui untuk mencapai suatu record database yang diinginkan sehingga akan mempercepat proses.

(Sumber: https://dzone.com/articles/database-btree-indexing-in-sqlite)

Aturan pada B-Tree : m = order

Setiap node (kecuali leaf) memiliki anak paling banyak sejumlah m anak
Setiap node (kecuali root) memiliki anak paling sedikit m/2 anak
Root memiliki anak minimal 2, selama root bukan leaf
Jika node non leaf memiliki k anak, maka jumlah data yang tersimpan dalam node k-1
Data yang tersimpan pada node harus terurut secara inorder
Semua leaf berada pada level yang sama, level terbawah

Dalam prakteknya b-tree bisa memiliki ribuan atau jutaan record. Tidak harus semua leaves memiliki suatu record, namun paling tidak adalah separuhnya harus memiliki. Perbedaan depth antara skema b-tree dan binary-tree adalah dalam penggunaan di sebuah sistem database dimana b-tree bisa memiliki order yang lebih tinggi, misalnya 32,64,128 atau lebih..

Contoh Insert dan Delete AVL Tree