PERTEMUAN KEENAM BALANCED BINARY SEARCH TREE (pt.1)

Balanced Binary Search Tree adalah BST yang diperpendek dengan tujuan untuk mempermudah pencarian sebuah node dalam tree. Balanced Binary Search Tree berasal dari dua buah metode yaitu AVL Tree dan Red Black Tree.

AVL Tree


AVL Tree adalah tree yang dibuat oleh G.M. Adelson-Veleski dan E.M. Landis pada tahun 1962. AVL Tree digunakan untuk mempermudah pembuatan balanced Balanced Binary Search Tree. Berikut adalah contoh dari sebuah AVL Tree Concept :



Didalam AVL Tree terdapat tiga proses yang dapat dilakukan, yaitu:

Insertion

Sama pada seperti cara insertion pada Binary Search Tree tetapi bentuk dari tree harus tetap balance. 

Single Rotation & Double Rotation

Single Rotation adalah proses dimana hanya terjadi suatu pertukaran node, biasanya proses ini juga disebut sebagai left left case atau right right case. Sedangkan Double Rotation adalah proses dimana terjadi dua kali pertukaran node, biasanya awal dari proses ini disebut left right case atau right left case.

Yang menentukan proses-proses ini adalah jumlah dari balance factor suatu node. Balance factor suatu node dapat ditentukan dari hasil pengurangan height node anak dari suatu node (Height anak yang nilainya lebih besar - nilainya lebih kecil). Jika hasil tersebut lebih dari 1 maka terjadi sebuah kesalahan dan harus dilakukan single atau double rotation tergantung dari dimana kesalahan tersebut dimulai.

Berikut adalah cara melakukan double rotation dan single rotation pada Balanced Binary Search Tree