ADT Tabel dengan Struktur Hirarkis
Suatu struktur binary tree dapat digunakan untuk mengimplementasikan ADT
tabel. Sebagai suatu tabel struktur ini memberikan kelebihan-kelebihan
mengingat strukturnya yang hirarkis memungkinkan proses-proses pencarian
yang logaritmis. Sementara dengan struktur linier seperti linear linked-list
diperlukan waktu pencarian yang linear. (Tanya: Bagaimana bisa jadi logaritmis?)
Definisi Binary Search Tree
Stuktur Binary Search Tree (BST) didefinisikan sebagai suatu binary tree
dimana pada setiap subtree T -nya:
key dari node-node subtree kiri dari T < key root T < key dari
node-node subtree kanan dari T.
Contoh:
|
|
Cara paling mudah apakah key-key dalam suatu binary tree membentuk struktur
BST adalah dengan melihatnya harga-harga key jika ditraverse secara inorder.
Secara inorder maka key-key tersebut terurut menaik dan tidak ada yang
sama. Contoh inorder traversal pada BST di atas menghasilkan:
3, 5, 8, 11, 14, 19, 22, 24, 25, 31, 39, 41, 44.
|
Algoritma Pencarian
Berdasarkan definisinya yang demikian maka pencarian suatu key tertentu
dapat dilakukan secara rekursif, yaitu setiap saat akan dilakukan pemeriksaan
harga key yang dicari terhadap harga key dari root suatu subtree:
-
jika sama, yang dicari berarti ketemu dan selesai,
-
jika lebih kecil, maka ada di cabang kiri dan pencarian diteruskan dalam
subtree kiri,
-
sebaliknya jika lebih kecil, ada di cabang kanan.
Selengkapnya algoritma pencarian suatu data dengan key K adalah
sbb.
BinaryTreeNode BinarySearchSearch (KeyType Key) {
if (this.equals(Key)) return P;
else if (this.greaterThan(Key))
if (left != null)
return left.BinarySearchSearch(K);
else return null;
else
if (left != null)
return right.BinarySearchSearch(K);
else return null;
}
Masalah algoritmis muncul apabila terjadi perubahan struktural:
-
penyisipan data key baru, atau
-
penghapusan suatu data key, atau
-
modifikasi suatu data key.
Karena modifikasi dapat dianggap sebagai penghapusan dan penyisipan
yang dilakukan sekaligus maka secara algoritma yang akan dibahas adalah
hanya dua masalah: penyisipan dan penghapusan.
Penyisipan Key K
Penyisipan suatu key baru ditangani dengan dengan sederhana, yaitu node Q
dicreate untuk key tsb. dan disisipkan sebagai leaf baru pada posisi
yang sesuai setelah proses pencarian. Algoritma penyisipan selengkapnya:
InsertNode(Q) {
if (this.equals(Q)) {
system.out.println("has already
been in the table\n");
} else if (this.greaterThan(Q)) {
if (left != null) left.Insert(Q);
else left = Q;
} else {
if (left != null) right.Insert(Q);
else right = Q;
}
}
Contoh jika pada diagram tree di atas dilakukan penyisipan berturut-turut
key-key 33, 50, 10, 17 maka tree akan berubah menjadi sbb.
Penghapusan Key K
Proses penghapusan lebih rumit karena bisa terjadi bahwa node
(kita sebut node P) dimana K berada merupakan internal node.
Masalah ini dipecahkan adalah dalam tiga kasus (secara rekursif):
- Kasus 1:
Jika subtree kiri P kosong maka P didelete dan digantikan oleh
digantikan oleh subtree kanan (kalau subtree kanan kosong berarti
P digantikan oleh tree kosong alias null)
- Kasus 2:
Jika subtree kiri tidak kosong, tapi subtree kanan kosong,
maka P digantikan oleh subtree kiri.
- Kasus 3:
Jika kedua subtree tidak kosong maka:
-
jika subtree kiri dari P ada maka cari predesesor inorder dari K, misalnya
di peroleh G yang berada dalam node Q
-
memindahkan G menggantikan K dalam P, lalu
-
dilakukan penghapusan isi node Q (penghapusan ini mengulangi secara rekursif
hal yang terjadi pada penghapusan node P dan hal ini bisa terjadi terus
menerus sampai suatu ketika ketemu kasus 1 atau 2).
Contoh
- jika dari hasil penyisipan-penyisipan di atas dilakukan penghapusan
key 22 maka rule kasus 1 yang diaplikasikan.
-
kemudian dilakukan penghapusan 44 maka juga rule kasus 1
diaplikasikan.
-
jika selanjutnya dilakukan penghapusan 39 maka rule kasus 2 diaplikasikan.
-
Jika sekarang 24 dihapus maka rule kasus 3 yang diaplikasikan dengan
key 19 sebagai predesesor inordernya berpindah ke node asal 24
dan seterusnya menyebabkan rule kasus 3 diaplikasikan kembali
dengan 17 sebagai predesesor inorder dari 19 untuk menempati node 19 semula
dan kemudian terakhir rule kasus 1 diaplikasikan.
Binary Search Tree ini dalam kondisi kedatangan key acak yang
membentuk suatu struktur tree
yang imbang (balance). Namun, kemunculan data baru atau penghapusan suatu
data kurang acak akan menyebabkan struktur tree yang tidak merata (tidak
imbang). Paling ekstrim jika menyusun BST dengan data yang sudah terurut,
maka struktur yang terbentuk adalah suatu linear list. Dalam kasus demikian,
manfaat struktur tree, yang memungkinkan pencarian logaritmis, jadi
tidak tercapai. Jadi BST mensyaratkan kemunculan data pada penyisipan yang
cukup acak.
Apabila syarat tersebut tidak bisa terpenuhi dan struktur BST harus
berfungsi sebagai indeks dalam proses pencarian yang logaritmis maka ada
beberapa hal yang
bisa dilakukan. Cara pertama adalah cara yang naif, dilakukan penyusunan ulang
(restrukturisasi) secara total, setiap kali dilakukan penyisipan dan
penghapusan atau secara periodik setelah sejumlah penyisipan dan
penghapusan dilakukan. Namun, hal ini amat mahal untuk data yang
banyak kecuali jika penyisipan/penghapusan tersebut tidak terlalu sering
terjadi.
Untuk menemukan suatu solusi efisien maka digunakan suatu kelas binary
tree yaitu Balanced Binary Tree, yang lebih dikenal dengan nama AVL Tree.
AVL TREE
AVL tree memiliki sifat-sifat khusus yang memungkinkan restrukturisasi
terjadi secara lokal dengan aturan-aturan sederhana. Nama AVL berasal
dari inisial nama-nama penemunya: G.M. Adelson-Velskii dan E.M. Landis.
Mereka pada tahun 1962 adalah yang pertama melakukan studi mengenai
sifat-sifat tree ini. Nama Balanced Binary Tree berkaitan dengan
sifat strukturnya yang selalu
"imbang" atau "hampir imbang".
Definisi
Suatu AVL Tree adalah suatu tree kosong atau suatu binary tree dengan kedua
subtree yang juga merupakan AVL Tree dengan perbedaan tinggi tidak lebih
dari 1.
Generalisasi definisi "tinggi" suatu tree untuk dapat digunakan untuk
AVL Tree:
-
tinggi suatu tree kosong adalah -1
-
tinggi suatu tree yang tidak kosong adalah jumlah path dari root hingga
leaf terjauh.
Secara grafis dapat digambarkan sebagai berikut.
Contoh-contoh AVL tree dengan tinggi h.
|
h=0
|
|
|
h=1
|
|
|
h=2
|
|
|
h=5
|
|
Fibonacci Tree
Anda mungkin sudah tahu Fibonacci Numbers, yaitu bilangan-bilangan yang
digenerate oleh fungsi Fibonacci fib(x):
fib(x) = fib(x-1) + fib(x-2) untuk x > 1
fib(1) = 1
fib(0) = 0
Fibonacci Tree adalah suatu AVL tree yang mana beda tinggi antara
subtree kiri dan kanan pada setiap internal node SELALU 1.
Jumlah node dalam suatu Fibonacci Tree dengan tinggi h adalah
g(x) = g(x-1) + g(x-2) + 1 untuk x > 1
g(1) = 2
g(0) = 1
Jadi dengan demikian Fibonacci Tree dengan tinggi h adalah AVL Tree
dengan tinggi h dengan jumlah node minimum sementara AVL Tree
dengan tinggi h dengan jumlah node maksimum adalah Perfect Binary Tree.
Pertanyaan:
Berapakah tinggi AVL Tree dengan jumlah node n?
TInggi minimal adalah tinggi dari Perfect Binary Tree dengan jumlah node n
dan tinggi maksimal adalah tinggi dari Fibonacci Tree dengan jumlah node n.
Dan tinggi AVL Tree berada di antara kedua ekstrimnya itu. Tinggi
Perfect Binary Tree mudah dijawab, tetapi tinggi berapa Fibonacci Tree?
Balance Factor
Untuk memudahkan algoritmanya maka perlu didefinisikan juga pada tiap node
dalam AVL tree suatu flag yang berisikan selisih tinggi subtree kanan dikurangi
dengan tinggi subtree kiri dari node tersebut. Kita namaan flag tersebut
adalah Balance Factor (BF).:
BF(node P)= tinggi subtree kanan - tinggi subtree kiri
Jadi suatu binary tree dengan BF dari node-nodenya berharga -1 atau
0 atau +1 adalah suatu AVL tree. Operasi penyisipan atau penghapusan pada
AVL-tree hanya akan mempengaruhi BF dari ancestor dari node tempat terjadinya
operasi tersebut sehingga pemeriksaan dilakukan sepanjang path ancestor
tersebut saja mulai dari bawah ke atas.
Dari contoh h=5 di atas maka BF dari masing-masing node digambarkan
sebagai bilangan di samping masing-masing node sbb.
Suatu Fibonacci tree adalah suatu
AVL Tree dengan node-node internalnya memiliki BF = +1 atau -1. Suatu
Perfect Binary Tree adalah suatu AVL Tree dengan node-node internalnya
memiliki BF = 0. Contoh AVL dengan h=5 di atas adalah juga merupakan Fibonacci Tree.
Handout
berikutnya, atau sebelumnya,
atau kembali ke halaman
utama