AVL TREE & B-TREE

Sebelumnya kita sudah pelajari yang namanya Binary Search Tree (BST) yang bisa dipelajari disini nah sekarang kita akan mempelajari yang namanya AVL Tree dan B-Tree. untuk konsepnya tidak berbeda jauh dengan Binary Search Tree (BST).

AVL Tree sendiri adalah Binary Search Tree yang memiliki perbedaan tinggi/ 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.

B-Tree adalah self balancing search tree. 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.

Properties Dari B-Tree 1) Semua leaf 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 children dari sebuah simpul sama dengan jumlah kunci di dalamnya ditambah 1. 6) Semua kunci simpul diurutkan dalam urutan yang meningkat. child antara dua tombol k1 dan k2 berisi semua kunci dalam kisaran dari k1 dan k2. 7) B-Tree tumbuh dan menyusut dari root yang tidak seperti Binary Search Tree. Binary Search Trees tumbuh ke bawah dan juga menyusut dari bawah. 8) Seperti balanced binary search tree lainnya, kompleksitas waktu untuk mencari, menyisipkan, dan menghapus adalah O (Logn).

Balanced binary tree juga memiliki beberapa ketentuan yaitu

1) Ketinggian Binary Search Tree bisa sebesar n-1 (saat BST miring).

2) Waktu yang diperlukan untuk melakukan penyisipan, penghapusan, pencarian, atau banyak operasi lainnya bergantung pada ketinggian pohon, ini berarti mereka dapat menjadi O (n) dalam kondisi terburuk.

3) Perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan.

Operasi Insert

1) Pertama, masukkan kunci baru sebagai leaf baru seperti dalam strategi memasukkan Binary Search Tree biasa. 2) Tetapi ini dapat menyebabkan pelanggaran pada properti AVL Tree. 3) Selanjutnya, kembalikan kondisi keseimbangan.

Cara untuk menyeimbangkan ada 2 yaitu

1) Single Rotation

Caranya pertama cek node yang menjadi menyebab masalah nya , setelah itu kita ambil jalur nya sampai ke root. jika garisnya searah artinya kita bisa melakukan single rotation untuk menyeimbangkan tree nya.

Untuk melakukan single rotation bisa dilakukan dengan cara merotate pada satu poros jika dia berat dikanan maka putarnya kekiri. maka child akan berubah menjadi root.

2) Double Rotation

Nah dari cara untuk menyeimbangkan double rotation adalah yang paling sulit biasanya double rotation kita tidak bisa langsung bilang 1x rotate akan membuat treenya langsung seimbang.

caranya tidak berbeda dengan single rotation hanya dilakukan 2x rotasi

Nama : Antonio Michael Kurniawan

NIM : 2301924063