ALGORITMA DAN STRUKTUR DATA : BAB 10

BINARY SEARCH TREE & AVL TREE

10.1 Binary Search Tree

Kelemahan dari Binary Tree yang telah dibahas pada bab sebelumnya adalah tidak efisien dalam
pencarian (searching the target Node), yang harus dilakukan secara sequensial dari mulai ROOT
sampai ke Node yang dikehendaki. Selain juga penghapusan terhadap Node Binary Tree tidak dapat
dilakukan, yang dapat dilakukan penghapusan 1 sub tree. Hal ini disebabkan karena pada Binary Tree
node tidak diurut. Binary Search Tree mengeliminir kelemahan tersebut diatas, dengan cara
mengurutkan node yang ada.

Ketentuan peletakkan node dalam binary search tree adalah sebagai berikut :
• Semua LEFT CHILD harus lebih kecil dari pada PARENT dan RIGHT CHILD
• Semua RIGHT CHILD harus lebih kecil dari pada PARENT dan LEFT CHILD

Gambar ini merupakan contoh dari Binary Search Tree :

Gambar
Gambar 10.1: Binary Search Tree

Keuntungan dari Binary Search Tree dibandingkan dengan Binary Tree adalah :

• Searching / pencarian target node menjadi lebih efisien dan cepat dibandingkan dengan
Binary Tree.

• Penghapusan dapat dilakukan terhadap target node, bukan terhadap 1 subtree seperti pada
Binary Tree.
Semua operasi dalam Binary Tree bisa di implementasikan langsung pada Binary Search Tree ,
kecuali :
• INSERT
• UPDATE
• DELETEKEY
Karena operasi diatas dapat mengakibatkan Binary Search Tree tidak urut. Sehingga harus dilakukan
modifikasi terhadap posisi node agar Binary Search Tree tetap terurut.

OPERASI INSERT
Operasi insert pada Binary Search Tree dilakukan dengan cara mencari lokasi untuk node yang akan
di insert. Pencarian selaku dimulai dari ROOT, jika node yang akan diinsert ternyata lebih kecil dari
ROOT, maka akan dilakukan insert pada left sub tree sedangkan bila node yang akan diinsert lebih
besar dari ROOT, maka akan dilakukan insert pada right sub tree. Pencarian lokasi untuk node
diteruskan sampai memenuhi kondisi Binary Search Tree yaitu semua node yang berada pada left
sub tree lebih kecil dari parentnya, sedangkan yang berada pada right sub tree harus lebih besar dari
parentnya.

Berikut ini akan dilakukan operasi insert, yang langsung akan digambarkan Binary Search Tree
setelah dilakukan operasi insert

insert (20)
Gambar

insert (50)
Gambar

insert (40)
Gambar

Gambar 10.2: Operasi Insert pada BST

OPERASI DELETEKEY
Berbeda dengan Binary Tree dimana penghapusan harus dilakukan terhadap sebuah sub tree, maka
pada Binary Seacrh Tree, penghapusan dapat dilakukan terhadap sebuah node (key) tertentu.
Operasi deletekey dapat mengakibatkan Binary Search Tree menjadi tidak urut lagi, sehingga perlu
dilakukan rotasi terhadap Binary Search Tree tersebut agar menjadi urut kecuali, beberapa posisi
node pada saat dilakukan operasi deletekey adalah :

1. Node yang dihapus adalah LEAF, sehingga penghapusan akan tetap membuat Binary Search
Tree terurut. Bila yang terjadi adalah ini, maka operasi penghapusan dapat langsung
dilakukan.

2. Node yang dihapus adalah node yang memiliki node 1 child, sehingga child yang
bersangkutan dapat langsung dipindahkan untuk menggantikan posisi node yang dihapus.

3. Node yang akan dihapus memiliki 2 children (2 subtree), maka node yang diambil untuk
menggantikan posisi node yang dihapus adalah :
a. Bisa berasal dari left sub tree, dimana node yang diambil adalah node yang
mempunyai nilai paling besar (yang berada pada posisi paling kanan).
b. Bisa berasal dari Right Sub Tree, dimana node yang diambil adalah node yang
mempunyai nilai paling kecil (yang berada pada posisi paling kiri).
Dengan menggunakan gambar Binary Search Tree berikut ini ,akan diilustrasikan operasi deletekey
untuk masing-masing kondisi di atas.

Gambar

Posisi 1: jika yang didelete adalah LEAF, maka tidak perlu dilakukan modifikasi terhadap lokasi contoh :
Gambar

Posisi 2 : jika yang didelete adalah NODE yang hanya memilki 1 child, maka child tersebut langsung
menggantikan parentnya contoh :
Gambar

POSISI 3: jika yang didelete adalah NODE dengan 2 children ( 2 Subtree), maka node yang diambil
untuk menggantikan posisi node yang dihapus adalah :

1. Berasal dari LEFT SUB TREE, yang diambil adalah node yang paling kanan
(yang mempunyai nilai yang terbesar)
2. Atau dari RIGHT SUBTREE, yang diambil adalah node yang paling kiri ( yang
mempunyai nilai yang terkecil).

10. 2 AVL TREE
Walaupun Binary SearchTree sudah dapat mengatasi kelemahan pada Binary Tree dengan cara
mengurutkan / sort node yang di-insert, di-update dan di-delete, tetapi masih ada kendala lain yang
dihadapai binary search tree , yaitu masih ada kemungkinan terbentuk skewed binary tree
(treemiring), yang mempunyai perbedaan height (height-balanced) antara subtree kiri dengan subtree
kanan sampai AVL (Adelson, Velskii dan Landis) Tree mengatasi hal ini dengan cara membatasi
height-balanced maksimum 1. AVL Tree dapat didefinisikan sebagai Binary Search Tree yang
mempunyai ketentuan bahwa “ maksimum perbedaan height antara subtree kiri dan subtree kanan
adalah 1”. AVL Tree juga sering disebut dengan height-balanced 1-tree. Gambar di bawah ini

memperlihatkan Binary Search Tree setelah dilakukan operasi insert sebagai berikut : +1, +2,
+3,……………..+n.

Gambar

Bila dilakukan pencarian terhadap node n diatas, maka pencarian sama seperti dilakukan pada Binary
Search Tree, yaitu pencarian menjadi sekuensi, yang memakan waktu lama, hal ini tidak mungkin
terjadi pada AVL Tree karena perbedaan height dibatasi maksimal hanya 1. berikut ini adalah contoh
ATL Tree dan yang bukan AVL Tree.

Gambar

Bila dilakukan pencarian terhadap node n diatas, maka pencarian sama seperti dilakukan pada Binary
Search Tree, yaitu pencarian menjadi sekuensi, yang memakan waktu lama, hal ini tidak mungkin
terjadi pada AVL Tree karena perbedaan height dibatasi maksimal hanya 1. berikut ini adalah contoh
ATL Tree dan yang bukan AVL Tree.

Gambar

Path pencarian lokasi untuk penentuan lokasi elemen pada operasi INSERT disebut dengan
Searching Path. Bila node pada search Path yang balancenya TallLeft (tanda-) tau TallRight (tanda +)
dan terletak paling dekat dengan node yang baru maka node tersebut dinamakan PIVOT POINT.
Gambar di bawah ini menunjukan pivot point :

Gambar

OPERASI INSERT
Agar AVL Tree dapat tetap mempertahankan Height-Balanced 1-Tree maka setiap kali pelaksanaan
operasi insert, jika diperlukan maka harus dilakukan rotasi. Operasi insert dalam AVL Tree ada 3
kondisi / kasus , yaitu :
• Case 1
Tidak ada Pivot Point dan setiap node adalah balance, maka bisa langsung diinsert sama
seperti pada Binary Search Tree (tanpa perlu diregenerate)

Gambar

• Case 2
Jika ada Pivot Point tetapi subtree yang akan ditambahkan node baru memiliki height yang
lebih kecil, maka bisa langsung diinsert .

Gambar

 

• Case 3
Jika ada Pivot point dan subtree yang akan ditambahkan node baru memiliki height yang lebih
besar, maka tree harus diregenerate , supaya tetap menghasilkan AVL Tree. Cara melakukan
re-generate adalah dengan melakukan :
o Single Rotation
o Double Rotation

Gambar

Contoh 1 : insert (5), sebelum dilakukan Single-Rotation
Gambar

 

Contoh 1

Gambar

(a) menunjukan sebelum ditambah angka 25, sedangkan gambar (b) menunjukkan setelah
ditambahkan angka 25 dan dilakukan Double – Rotation

kasus – kasus yang dapat diatasi dengan single rotation:
􀂃 kasus 1

Gambar

􀂃 kasus 2

Gambar

Gambar

Double Rotation
Pada beberapa kasus di AVL tree dapat diselesaikan hanya dengan cara single rotation, seperti pada
contoh diatas, tetapi ada pula yang tidak dapat diselesaikan hanya dengan single rotation, itu artinya
kita harus menggunakan teknik double rotation untuk menyelesaikan masalah imbalance pada tree.
􀂃 Kasus 1

Gambar

Gambar

Gambar

Operasi Delete
Operasi delete dalam AVL Tree adalah sama dengan operasi Deletekey dalam Binary Search Tree
(3 kasus yang bisa terjadi ). Yang harus diperhatikan adalah harus diusahakan agar pohon asli Delete
tetap berupa AVL-Tree yaitu dengan melakukan rotasi.

Iklan

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s