AVL TREE & B TREE

AVL TREE

Avl tree adalah binary search tree yang didalamnya memiliki perbedaan ketinggian antara subtree kiri dan subtree kanan dari node 0 atau yang sama dengan 1.

teknik menyeimbangkan tinggi binary tree ditemukan oleh Adelson, Velskiidan Landi dan dengan demikian diberikan bentuk pendek sebagai pohon AVL atau Balanced Binary Tree.

Keuntungan
Karena AVL adalah pohon yang berimbang tinggi, operasi seperti penyisipan dan penghapusan memiliki kompleksitas waktu yang rendah.

Pohon AVL memeriksa ketinggian kiri dan kanan sub-pohon dan menjamin bahwa perbedaan tidak lebih dari 1. Perbedaan ini biasanya disebut sebagai faktor keseimbangan .

Pada pohon kedua, sub-pohon kiri dari C memiliki tinggi 2 dan sub-pohon kanan memiliki tinggi 0, jadi perbedaannya adalah 2. Pada pohon ketiga, subpohon kanan dari A memiliki tinggi 2 dan kiri hilang, jadi itu adalah 0, dan perbedaannya adalah 2 lagi. Pohon AVL memungkinkan perbedaan (keseimbangan faktor) menjadi hanya 1.

Balance Factor = height(left sub-tree) - height(right sub-tree)

Insertion :

Langkah 1: pertama, sisipkan elemen baru ke dalam pohon menggunakan logika penyisipan BST (pohon pencari biner).
Langkah 2: setelah memasukkan elemen Anda harus memeriksa Balance Factor setiap node.
Langkah 3: ketika faktor keseimbangan setiap node akan ditemukan seperti 0 atau 1 atau-1 maka algoritma akan dilanjutkan untuk operasi berikutnya.
Langkah 4: ketika faktor keseimbangan dari setiap node datang Selain tiga nilai di atas maka pohon itu dikatakan tidak seimbang. Kemudian lakukan rotasi yang cocok untuk membuatnya seimbang dan kemudian algoritma akan dilanjutkan untuk operasi berikutnya.
Ada empat jenis rotasi:
1. Left rotate

 2. Right Rotate

 

3. Left Right Rotate

4. Right Left Rotate

Deletion 

Langkah 1: pertama, menemukan bahwa node mana k disimpan
Langkah 2: kedua menghapus isi dari node (Misalkan node x)
Langkah 3: klaim: menghapus node dalam pohon AVL dapat dikurangi dengan menghapus daun. Ada tiga kemungkinan kasus:

Bila x tidak memiliki anak, Hapus x.
Ketika x memiliki satu anak, biarkan x ' menjadi anak x.
Perhatikan: x ' tidak bisa memiliki anak, karena sub T dapat berbeda di tinggi oleh paling satu:
        kemudian ganti isi x dengan isi x '
        kemudian Hapus x ' (daun)
Langkah 4: ketika x memiliki dua anak,
        kemudian menemukan penerus x z (yang tidak memiliki anak kiri)
        kemudian ganti isi x dengan isi z, dan
        Hapus z

Dalam semua tiga kasus, Anda akan berakhir menghapus daun.

B tree
Ada jenis khusus pohon yang disebut  B tree di mana node berisi lebih dari satu nilai/kunci dan lebih dari dua anak.