Data Structure – Pertemuan 6

Balanced Binary Search Tree

BT (Binary Tree)img151

BST (Binary Search Tree)2000px-Binary_search_tree.svg

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 treeavl1

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.avl2

Contoh AVL tree menggunakan single rotation

avl7

Contoh AVL tree menggunakan double rotation

  • Digg
  • Del.icio.us
  • StumbleUpon
  • Reddit
  • Twitter
  • RSS

Leave a Reply