AVL TREE & B-TREE

AVL Tree

AVL tree adalah Binary Search Tree (BST) yang dapat menyeimbangkan diri sendiri di mana perbedaan antara ketinggian subtree kiri dan kanan tidak boleh lebih dari satu untuk semua node.

CONTOH TREE YANG MERUPAKAN AVL TREE

The above tree is AVL because differences between heights of left and right subtrees for every node is less than or equal to 1.

CONTOH TREE YANG BUKAN MERUPAKAN AVL TREE

WHY AVL Trees?

Sebagian besar operasi BST (Search, max, min, insert, delete, dll) Mengambil O (h) waktu di mana h adalah ketinggian BST. Biaya operasi ini dapat menjadi O (n) untuk pohon Biner miring. Jika kami memastikan bahwa ketinggian pohon tetap O (Logn) setelah setiap penyisipan dan penghapusan, maka kami dapat menjamin batas atas O (Logn) untuk semua operasi ini. Ketinggian pohon AVL selalu O (Logn) di mana n adalah jumlah node di pohon.

Insertion
Untuk memastikan bahwa pohon yang diberikan tetap AVL setelah setiap penyisipan, kita harus menambah operasi penyisipan BST standar untuk melakukan penyeimbangan ulang. Berikut ini adalah dua operasi dasar yang dapat dilakukan untuk menyeimbangkan kembali BST tanpa melanggar properti BST

(keys(left) < key(root) < keys(right)).
1) Left Rotation
2) Right Rotation

B-TREE

B-Tree adalah pohon pencarian self-balancing. Di sebagian besar pohon pencarian self-balancing lainnya (seperti AVL dan Red-Black Trees), diasumsikan bahwa semuanya ada dalam memori utama. Untuk memahami penggunaan B-Trees, kita harus memikirkan sejumlah besar data yang tidak dapat ditampung dalam memori utama. Ketika jumlah kunci tinggi, data dibaca dari disk dalam bentuk blok. Waktu akses disk sangat tinggi dibandingkan dengan waktu akses memori utama. Gagasan utama menggunakan B-Trees adalah untuk mengurangi jumlah akses disk. Sebagian besar operasi pohon (pencarian, masukkan, hapus, maks, min, ..etc) memerlukan O (h) akses disk di mana h adalah ketinggian pohon. B-tree adalah pohon yang gemuk. Ketinggian B-Trees dijaga tetap rendah dengan meletakkan kunci maksimum yang mungkin dalam simpul B-Tree. Secara umum, ukuran simpul B-Tree dijaga sama dengan ukuran blok disk. Karena h rendah untuk B-Tree, akses disk total untuk sebagian besar operasi berkurang secara signifikan dibandingkan dengan Binary Search Trees yang seimbang seperti AVL Tree, Red-Black Tree.

Properties of B-Tree

1) Semua daun berada pada level yang sama.

2) B-Tree didefinisikan dengan istilah tingkat minimum ‘t ’. Nilai t tergantung pada ukuran blok disk.

3) Setiap node kecuali root harus mengandung setidaknya kunci t-1. Root mungkin berisi kunci minimal 1.

4) Semua node (termasuk root) dapat berisi maksimal 2t - 1 kunci.

5) Jumlah anak-anak dari sebuah simpul sama dengan jumlah kunci di dalamnya ditambah 1.

6) Semua kunci simpul diurutkan dalam urutan yang meningkat. Anak antara dua tombol k1 dan k2 berisi semua kunci dalam kisaran dari k1 dan k2.

7) B-Tree tumbuh dan menyusut dari akar yang tidak seperti Binary Search Tree. Binary Search Trees tumbuh ke bawah dan juga menyusut dari bawah.

8) Seperti Pohon Penelusuran Biner seimbang lainnya, kompleksitas waktu untuk mencari, menyisipkan, dan menghapus adalah O (Logn).