Data Structure – Pertemuan 6
Balanced Binary Search Tree
BT (Binary Tree)
BST (Binary Search Tree)
Gambar diatas merupakan contoh-contoh binary tree dan binary search tree.
Ketika kita membuat binary search tree, maka kadang terlihat bagian tree yang berbentuk skewed tree.
Skewed tree boros dan tidak efisien dan juga tidak balance.
Untuk membuat tree yang seminimal mungkin maka terciptalah balanced binary search tree.
Balanced binary search tree dibagi menjadi 2 bentuk yaitu :
- AVL Tree
- Red Black Tree
AVL tree pertama kali ditemukan oleh Adelsen – Veleskii dan E.M.Landis pada tahun 1962.
Nama mereka dipakai sebagai singkatan “AVL” pada AVL tree.
Contoh AVL tree
Angka 4, 3, 2, 1 merupakan jarak angka tersebut dengan anak yang paling bawah.
Misalnya berupa angka 4.1 berarti angka 1 itu merupakan selisih yang bawah. (3-2=1)
AVL tree memiliki single rotation dan double rotation untuk membuat tree nya menjadi balance.
Contoh AVL tree menggunakan single rotation
Contoh AVL tree menggunakan double rotation
