AVL TREE
T H E E V O L V E D B I N A R Y T R E E
A. Introduction
---------------------------------------------------------------------------------
Pada blog yang lalu , mimin peik sudah bahas tentang Binary Search Tree secara umum . Nah , kalian sadar gak sih ? Kalau BST itu sendiri kadang mempunyai kasus yang unik . Coba kalian masukkan input yang sifatnya incremental / decremental , seperti 2 , 3 , 4 , 5 , 6 . Apa yang terjadi ?
Hal inilah yang akan terjadi seakan-akan kita tidak membuat Binary Search Tree , malah seperti " Linear Search " Tree . Dengan kata lain , BST memiliki kelemahan yakni jikalau input user sifatnya incremental ataupun decremental , maka BST akan menjadi tidak seimbang . Lalu lahirlah ide dan strategi untuk membuat BST Seimbang ( Balanced BST ) yang dinamakan AVL Tree.
AVL Tree sendiri adalah bentuk BST yang lebih tinggi karena ada algoritma
"penyeimbang" Tree yang memiliki perbedaan depth / height / tinggi tree MAKSIMAL hanya 1 antara subtree kiri dan kanan. Jadi kalau inputnya seperti pada contoh di atas ( 2 , 3 , 4 , 5 , 6 ) , maka dengan implementasi AVL Tree akan berubah menjadi bentuk berikut :
Jadi seimbang kan ? :) Ditambah lagi , waktu pencarian lebih cepat dan efisien lho ! Kompleksitasnya mencapai O(log n )
B. Case and How does it work ?
---------------------------------------------------------------------------------
1. Single Rotation
***
Jadi , kasus krusial yang berperan disini adalah ketika user atau kalian melakukan input data . Penyeimbangan pada insertion itu terjadi saat ada node yang membuat Tree menjadi tidak seimbang ! Jikalau demikian , node tersebut dapat kalian ibaratkan seperti sebuah poros katrol . Jikalau subtree kiri yang cenderung tidak seimbang , maka si node ( poros katrol ) dapat digeser ke arah sebaliknya , yakni ke kanan . Hal ini juga berlaku sebaliknya . PERLU DIINGAT BAHWA KASUS INI berlaku untuk SINGLE ROTATION !
Single Rotation adalah teknik atau metode yang digunakan jikalau node subtree yang tidak seimbang berada lurus dari node root Tree. Untuk lebih jelasnya mari kita lihat gambar berikut :
Pada gambar (a) , terlihat BST yang sudah seimbang ( sudah menjadi AVL Tree ) . Karena bisa terlihat dari perspektif node root ( 2 ) , sebelah kirinya TINGGInya 1 dari node root , dan sebelah kanannya TINGGINYA 2 dari si node root , selisih antara subtree kiri dan kanan adalah 2 - 1 = 1. ( masih seimbang , karena selisih maksimal AVL Tree = 1 ).
Tiba-tiba , user melakukan input ( insertion ) dengan data bernilai 6 pada gambar (b) . Karena datanya lebih besar dari 2 , dari 4 , dan dari 5 , maka data 6 ditempatkan di sebelah kanan node 5 ( algoritma BST , data yang lebih besar ditempatkan di sebelah kanan si Node sub , begitu juga sebaliknya).Oke , sekarang kita hitung TINGGI masing-masing anak kiri dan kanan dari perspektif node ROOT ( 2 ). Untuk sebelah kiri , tingginya hanya 1. Sedangkan untuk sebelah kanan , tingginya 3 ( dapat dilihat ada 3 h yang berbeda yakni h1,h2 dan h3 ). Wah ternyata selisih kiri dan kanan 3 - 1 = 2 ( lebih dari syarat AVL Tree ) . Maka node yang membuat Tree tersebut tidak seimbang adalah 2 ( root )dengan node subtree di sebelah kanan paling dalam , si 6. Maka , node root , karena dia yang membuat tidak seimbang , harus ditarik atau digeser ke sebelah kiri ( berhubung si node 6 ada di sebelah kanan terdalam ) --> Single Rotation .
Dengan melakukan Single Rotation , node root sekarang adalah node di bawah kanan si 2 yakni si 4 . Dan otomatis node subtree kiri dari si 4 sebelumnya ( si 3 ) sekarang milik node si 2 dan ditempatkan di sebelah kanannya ( karena > 2 ). Akhirnya jadilah AVL Tree !
2. Double Rotation
***
(a) (b) (c)
Nah , kasus Double Rotation tidak jauh berbeda dari Single Rotation . Pada gambar (a) , coba lihat ketika user menginput data F , maka Tree menjadi tidak seimbang ( bisa terlihat dari perspektif node root A , anak kiri ( TINGGI 3 ) dan anak kanan ( TINGGI 1 ) berselisih 3 - 1 = 2 , melebihi syarat AVL Tree) . Node F lah penyebab ketidakseimbangan Tree dan dilihat dari perspektif node root A . Sekarang , kita melakukan traverse dari node root ( A ) ke node F . Wah , ternyata A - B - E - F itu BENGKOK traversingnya .... bukan lurus :( , gimana dong ?
Tenang saja , kalau gitu kita gunakan Single Rotation sebanyak 2 kali , makanya dinamakan Double Rotation . Rotasi pertama , yakni dilakukan di titik belok setelah node root , yakni pada node B . Berarti node B ditarik ke kiri , dan akan menjadi seperti pada gambar (b). Lho , masih tidak seimbang nih !Ya memang belum seimbang wuy ! Sekarang kita lakukan Single Rottion lagi seperti biasa . Dari perspektif node root A , kiri ( t = 3 ) dan kanan ( t = 1 ) masih berselisih 2 . Oke kalau gitu , node root A sebagai poros katrol lagi , kita tarik ke KANAN ya guys karena balance factor nya ( kanan lebih berat ).
Akhirnya , AVL Tree terwujud pada gambar (c) dimana node root nya sekarang menjadi si E . Anak kiri ( t = 2 ) dan anak kanan ( t = 2 ) , maka selisihnya 0 guys .
Kondisi ini disebut juga :
P E R F E C T A V L T R E E !
Min , abis Insertion , harusnya ada Deletion juga dong kayak di BST ? Betul !
Nah , Deletion disini juga algoritmanya sama seperti BST , namun setelah dilakukan Deletion , syarat AVL Tree juga harus diimplementasikan lagi ^_^ .
Selain AVL Tree , ada juga lho namanya Red-Black Tree . Namanya udah kayak nama buah aja ya ^_^ .... Ditunggu untuk blog selanjutnya ya ! Mimin harap kalian paham AVL Tree dulu nih .
Sumber :
Comments
Post a Comment