Balanced Binary Search Tree terdiri dari 2 jenis, yaitu:
- AVL Tree
- Red Black Tree
Pada pertemuan kali ini, kami belajar AVL tree. AVL tree sendiri adalah binary search tree yang dapat menyeimbangkan tree nya sendiri. Tujuannya adalah untuk mempermudah searching.
Dalam AVL terdapat yang namanya balance factor. Balance factor ini adalah faktor keseimbangan antara child node kiri dan kanan. Dihitung dengan selisih antara child node kiri dan kanan. Jika tidak memiliki anak, maka dihitung 0. Balance factor pasti tidak lebih dari 1.
Lalu ada juga height factor. Dihitung dengan:
- Jika node root, tidak memiliki subtree, height factor = 0.
- Jika node adalah leaf, height factor = 1
- Jika node internal, height factor dihitung dari height tertinggi child node + 1.
To balance an AVL tree, we do these steps:
Single Rotation
Double Rotation
