Balanced Binary Search Tree

Balanced Binary Search Tree adalah Binary Search Tree dengan height seminimal mungkin dan mempunyai kompleksitas O(log n). Sehingga, dapat mempersingkat waktu dan memudahkan pencarian. Contoh dari Balanced BST adalah AVL Tree.

AVL Tree

AVL Tree 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. AVL Tree dinamakan berdasarkan penemunya, yaitu G. M. Adelson-Velsky dan E. M. Landis.

Balance Factor adalah selisih dari height node kiri dan height node kanan. balance factor yang diperbolehkan hanya -1, 0 dan 1. Apabila lebih atau kurang, maka terjadi violation.

Apabila terjadi violation, maka cara agar tree menjadi balance kembali adalah dengan rotation. Ada dua cara rotation, yaitu single rotation dan double rotation.

Single Rotation memiliki dua jenis, yaitu:

1. Left Left

2. Right Right

Double Rotation

contoh double rotation: