AVL Tree

AVL Tree

Apa itu AVL Tree?

AVL Tree adalah Binary Search Tree yang dapat menyeimbangkan dirinya sendiri dimana perbedaan tinggi cabang kiri dan kanan tidak bisa lebih dari 1 atau seluruh jumlah node.

Contoh AVL Tree

Kenapa AVL Tree?

Binary Search Tree dengan AVL Tree, yang mana yang lebih baik? Dalam hal processing Binary Search Tree lebih lama dengan kecepatan sebesar O(n) sementara AVL Tree memiliki kecepatan processing sebesar O(log n).

Insertion

Untuk memasukan node baru dalam AVL Tree yang harus dilakukan sama saja dengan Insertion dari BST bedanya kita harus memperhatikan apakah node yang dimasukan akan merusak syarat AVL Tree nya.  Jika insertion membuat pohon tidak seimbang maka harus diseimbangkan menggunakan teknik Single Rotation atau Double Rotation.

Contoh Insertion pada AVL Tree

Deletion

Untuk melakukan deletion langkah dan cara yang dilakukan sama saja dengan melakukan deletion pada BST tetapi seperti insertion kita harus melihat apakah pohon seimbang atau tidak, jika tidak kita harus melakukan rebalancing dengan Single Rotation atau Double Rotation

Contoh Deletion