A. Struktur Data
1. Stuktur Data Pohon AVL
AVL merupakan pohon pencarian biner seimbang (self-balancing binary search tree). Pencarian, penyisipan dan penghapusan memiliki kompleksitas waktu O (log n) untuk kasus rata-rata dan kasus terburuk. Jika factor seimbang (balance factor) -1, 0, 1 maka pohon masih AVL dan tidak perlu rotasi pohon (penyeimbangan lagi), namun jika factor seimbangnya -2 , 2 maka perlu rotasi pohon. Untuk meyeimbangkan kembali.
a. Stuktur Data Pohon Merah Hitam (Red Black Tree)
Karakteristik pohon merah hitam :
o Simpul berwarna hitam atau merah
o Akar selalu berwarna hitam
o Semua daun pada pohon berwarna hitam
o Kedua anak dari simpul merah harus berwarna hitam
o Setiap jalur yang dilalui dari akar sampai ke daun memiliki jumlah simpul hitam yang sama.
Jumlah simpul hitam dalam satu jalur disebut black-height pohon. Karakteristik di atas menjamin jalur yang dilalui dari akar ke daun tidak lebih dari dua kali . Jumlah memory yang dibutuhkan untuk menyimpan simpul merah hitam harus dijaga agar tetap minimum, terutama bila simpul ini telah dialokasi. Pencarian, penyisipan dan penghapusan memiliki kompleksitas waktu O (logn).
b. Stuktur Data Pohon Splay (Splay Tree)
Pohon splay merupakan self-adjusting binary search tree yang strukturnya telah dimodifikasi (tidak unutk isinya). Operasi splay pada simpul x pada pohon pencarian biner terdiri dari langkah-langkah berikut, hingga x menjadi akar pohon . Berikut disebutkan langkah splay :
Kasus 1 : jika x adalah anak kiri dari akar y, maka maka rotasi kanan y menjadi anak kanan x, seperti pada gambar 1 (a). Berlaku pada arah kebalikannya. Kasus ini disebut kasus zig.
Kasus 2 : jika x adalah anak kiri y dan y adalah anak kiri dari z, maka rotasi kanan z, diikuti rotasi kanan y, seperti gambar 1(b). Berlaku juga untuk arah kebalikannya. Kasus ini disebut kasus zig-zig.
Kasus 3 : jika x adalah anak kanan dari y dan y adalah anak kiri dari z, maka rotasi kiri y
Diikuti rotas kanan z, seperti gambar 1(c). Kasus ini disebut kasus zig-zag.
Gambar 1: Langkah splay. Simpul yang diakses adalah x .
(a) zig : rotasi tunggal.
(b) Zig-zig : dua rotasi tunggal.
(c) Zig-zag : rotasi ganda.
c. Stuktur Data Treap
Treap adalah struktur data dasar pada pohon pencarian random/acak. Kata treap berasala dari tree dan heap. Lebih jelasnya, misalkan x menyatakan satu set item di mana setiap item memiliki kunci dan priority. Treap dari set x menyata kan kasus istimewa dari pohon pencarian biner yang mana set simpul disusun berurutan (tergantung kunci) seperti heap fashion ( tergantung pada prioritas). Waktu pencarian proposional terhadap kedalaman elemen pada pohon. Penyisipan elemen memerlukan proses 2-langkah. Langkah pertama menempatkan posisi daun (sesuai dengan nilai kunci) dan langkah kedua rotasi item ke atas (sesuai dengan priority dalam sturktur pohon ). Begitu juga dengan penghapusan yang memerlukan proses 2-langkah. Kompleksitas waktu untuk pencarian, penyisipan dan penghapusan adalah O (logn).
d. Stuktur Data Skip List.
Skip list menyatakan list berkait yang terurut di mana setiap simpul berisi variable nomor dari link ke simpul lain dalam suatu struktur. Sebagai gambaran link nth dari simpul point yang diberikan simpul-simpul di dalam suatu list melewati/skip bebrapa nomor simpul perantara. Untuk beberapa aplikasi, skip list menyatakan gambaran yang lebih umum dibandingkan struktur pohon karena menggunakan algoritma yang lebih simple untuk diimplementasikan. Namun, ukuran simpul yang bervariasi merupakan salah satu kelemahan skip list. Kompleksitas waktu rata-rata pada pencarian, penghapusan dan penyisipan adalah O (logn). Kemungkinan menemui kinerja yang buruk (kompleksitas waktu O(n) )memang sangat kecil, meskipun demikian, kemungkinan itu tetap ada.
e. Stuktur Data Pohon Radix.
Pada pohon pencarian radix , data disimpan sebagai objek daun sehingga simpul internal tidak memiliki nilai kunci . Simpul internal dari anak menyatakan simpul internal yang lain atau data yang sebenarnya. Untuk pengurutan (sort), memiliki kompleksitas waktu O (nk), di mana n menyatakan jumlah item dan k menyatakan rata-rata dari panjang kunci. Kelemahan algoritma pengurutan pada pohon radix adalah tidak bisa langsung dieksekusi pada tempatnya. Hal ini menyebabkan, kebutuhan penambahan memory O (n). Pengurutan radix membutuhkan 1 pass/langkah untuk setiap symbol kunci, sehingga kurang effisien.
2. Representasi Simpul
Idealnya, operasi traversal untuk menemukan suksesor dan predesor secara urut harus mencapai O (1). Berikut kompleksitas waktu kasus normal, terurut dari yang tercepat.
o list berkait O(1) traversal dengan sigle branchless pointer dereference.
o Threads O(1) traversal dengan mengikuti pointer tunggal upward atau downward.
o Right treads O(1) operasi suksesor, sepeerti simpul thread, tapi menemukan simpul predessor memerlukan O(log n), pencarian dari akar pohon di mana simpul tidak memiliki anak kiri.
o Parent pointer O(1) , traversal dengan menngikuti O(1) pointer upward atau downward dalam pohon.
o Plain O(1) traversal dengan mempertahankan tumpukan eksplisit (explicit stack). Jika pohon dimodofikasi maka kinerja menurun ke O (kg n).
Operasi rotasi yang digunakan untuk mempertahankan keseimbangan pohon seimbang, harus menanggulangi banyak representasi simpul. Dengan parent pointer, setiap rotasi membutuhkan 3 ekstra pointer assignment, jumlah assignment yang dilakukan menjadi ganda. Pada pohon threaded , setiap rotasi membutuhkan 1 atau 2 ekstra assignment dan dua cara cabang. Pada pohon right-threaded , setipa rotasi membutuhkan dua cara cabang dan 1 ekstra assignment. Representasi simpul juga membutuhkan memory yang berbeda. Parent pointer menambah pointer tunggalk pada setiap simpul ; simpul list berkait menambahkan dua. Simpul threaded menambahkan 2 “tag” bit setiap simpul untuk membedakan treads dari pointer anak dan simpul right threaded menambahkan 1 tag bit.
B. Pembahasan Kinerja Pohon Pencarian Biner
1. Operasi Penyisipan, Pencarian, dan Penghapusan.
Berikut beberapa sample variasi struktur data pohon pencarian biner dalam proses penyisipan. Pada kasus di atas, simpul terurut menurun, stuktur data treap merupakan yang terbaik. Namun, analisa lebih lanjut melalui pengukuran data , fluktuasi penyisipan, pencarian dan penghapusan yang berbeda (menaik, menurun, maupun random) membuktikan bahwa struktur pohon merah hitam memiliki kekonsistenan dan lebih cemerlang dalam hal implementasi.
a. Kinerja Pada Sytem Software
Perbandingan antara pohon yang tidak seimbang (treap, radix, split) dengan pohon seimbang (pohon merah hitam,pohon AVL, dan pohon splay) menghasilkan setiap struktur pohon lebih baik dalam situasi yang berbeda. Pohon tak seimbang paling baik saat input/ masukan data adalah random, tapi jika perintah randomnya adalah normal dan perintah pengurutan/sort berjalan seperti yang diharapkan naka pohon merah hitam merupakan piilihan yang tepat. Di lain pihak, jika penyisipan sering terjadi dalam perintah pengurutan,pohon AVL baik ketika akses selanjutnya cenderung random, sedangkan pohon splay memiliki kinerja yang baik ketika akses selanjutnya adalah berurut/sequential atau berkelompok/clustered .
Berikut merupakan penjelasan dari eksperimen yang dilakukan untuk mengetes kinerja dari struktur data pohon pencarian biner.
b. Virtual Memory Areas
Setipa proses dalam Unix seperti kernel memiliki virtual memory areas (VMAs). Minimum scara statis pohon berkait memiliki satu VMA untuk setiap kode, data dan segmen tumpukan (stack segments). Secara dinami, pohon berkait juga mmiliki kode dan data VMAs untuk setipa library yang dinamis. Pemroses dapat menciptakan sebuah VMAs yang berubah-ubah, bergantung pada btasa suatu system opersai atau arsitektur mesin dengan memetakan (mapping) disk files ke memory dengan mmap system call. VMAs bervariasi dalam ukuran dari 4 kB hinggnan 1 GB, sehingga konvensional hash tables tidak dapat mejaga track secara efisien. HAsg tables juga tidak dapat mendukung secara efisien jangkauan antrian yang dibutuhkan untuk menentukan yang mana VMAs yang ada dan yang tumpang tindih di area permintaan oleh mmap atau munmap call. Untuk mengatasi kedua hal di atas, digunakan sturktur data pohon pencarian biner (BST). Terbukti dari banyak kernel menggunakan BSTs untuk menjaga track VMAs : Linux sebelum 2.4.10 menggunakan pohon AVL, OpenBSD dan versi Linux selanjutnya menggunakan pohon merah hitam, Free BSD menggunakan pohon splay. Begitu juga dengan Windows NT.
Untuk random data set, semua implemntasi dikelompokkan dengan jangkauan yang relative kecil sekitar 2.3 kali perbedaan. Secara intuitif, implementasi tercepat haruslah yang memiliki ekstra kerja yang paling sedikit. Pada random data set , pohon pencarian biner biasa tidak ada rotasi, pohon merah-hitam 209 rotasi, pohon AVL 267, pohon splay 2678. Sehingga urutan mulai dari tercepat hingga yang paling lama adalah pohon pencarian biner yang biasa, pohon merah hitam, pohon AVL dan pohon splay. Dalam representasi simpul, dari yang tercepat adalah simpul list berkait, simpul dengan parent pointer, simpul threaded, simpul right-threaded dan terakhir simpul plain.
2. Internet Peer Cache
RFC 791 membutuhkan setiap IP dikirim dengan host internet yang ditandai dengan 16-bit identifikasi yang harus unik dari source tujuan dan protocol pada saat datagram aktif dalam internet system. Kernel Linux menggunakan pohon AVL yang indexnya dari peer IP address. Implementasi ini merupakan cara yang memudahkan dan membuat DoS menjadi lebih efisien. Contohnya hashing yang dapat membuat collision attack dapat diatasi dengan menggunakan teknik pohon seimbang. Peer pohon AVL digunakan sebagai second-level cache . Paket data dikirim ke host tertentu , sebuah simpul dan IP address nya disisipkan ke pohon. Penunjuk langsung ( direct pointer) ke simpul ini diletakkan pada route cache (first-level cache). Berikut merupakan data hasil test pada kondisi normal dan attack.
Tabel 1. Waktu dalam detik scenario pada normal dan attack simulasi. * menandakan lebih besar dari 60 detik.
a. Data tes normal
Dari hasil simulasi didapat urutan yang tercepat berdasarkan representasi simpul dimulai dari parent pointer, threads, plain, list berkait, right threads. Kecepatan parent pointer dan thread mempengaruhi kemampuan untuk menggunakan t_delete untuk penghapusan O(1). Di antara representasi simpul lainnya , plain merupakan yang tercepat karena tidak terhambat oleh manipulasi list berkait atau right thread yang tidak menguntungkan dalam eksperimen ini . Namun ada pengecualian, untuk pohon splay yang walaupun menggunakan representasi simpul thread, tetap merupakan yang paling lama. Hal ini disebakan oleh hasil yang tidak sesuai pada saat implementasi pohon splay. Untuk mengatasi keanehan ini, pohon splay dengan representasi simpul thread ini dimodifikasi untuk mempertahankan tumpukan parent pointer dan bergantung pada algoritma untuk mendapatkan simpul parent.
Tes Set Representasi BST AVL RB Splay
Normal plain parent threads right thread list berkait 4.74 3.94 3.99 5.52 4.93 5.10 4.07 4.45 5.71 5.40 5.06 3.78 4.17 5.64 5.25 7.70 7.19 13.25 8.29 8.41
attack plain parent threads right thread list berkait * * * * * 3.76 2.65 2.97 4.04 4.10 4.32 2.92 3.27 4.77 4.46 4.14 3.21 7.77 4.62 4.78
Tabel 1. Waktu dalam detik , scenario simulasi , * lebih besar dari 60 detik
Ketika eksperimen ini dijalankan pada system analisa didapat bahwa Pentium IV memiliki kerja ekstra terhadap cabang. Pomter parent dan list berkait membutuhkan lebih sedikit cabang dibandingkan yang lain. Itulah sebabnya mereka bisa lebih cepat.Untuk kasus normal dengan representasi simpul yang konsisten , maka urutan yang tercepat adalah pohon tak seimbang, pohon merah-hitam, pohon AVL dan pohon splay.
b. Data tes attack
Pohon AVL lebih baik dibanding pohon merah hitam karena pada pohon AVL yang seimbang sangat membantu dalam hal menjaga tinggi pohon menjadi minimum pada penyisipan selanjutnya dan menjaga langkah maksimum untuk semua operasi. Berdasarkan data yang diperoleh rata-rata internal panjang langkah semua operasi bervariasi kurang dari 1 % antara pohon AVL dengan pohon merah hitam. Pohon splay sangat buruk pada data set attack, karena proses sekuensial akses menjadi waktu linear.
Pentium IV, hasilnya berneda dengan sebelumnya di mana urutan yang tercepat adalah parent pointer, list berkait, threads, right threads dan plain.
3. Cross Reference Collator
Penggunaan cross reference collator ini berguna untuk pengembangan perangkat lunak. Dikatakan “cross reference collator” karena menyisipkan satu set pengenal yang dibaca ke pohon tunggal . Setiap pengenal memilikki pohon sendiri yang terdiri dari nama file di mana pengenal itu muncul. Setiap file memiliki satu set jumlah baris yang berkorespondensi dengan baris file pengenal itu muncul.
a) Data tes normal
Untuk kasus normal pohon splay merupakan yang tercepat diikuti pohon merah hitam, pohon AVL, dan pohon tak seimbang.
b) Data tes terurut
Untuk kasus terurut, pohon splay merupan yang terbaik diikuti pohon AVL dan pohon merah hitam.
c) Data tes acak
Untuk kasus acak, justru pohon splay merupakan yang terburuk, sehingga lebih baik menggunakan pohon merah hitam.
4. Perbandingan
Berdasarkan hasil percobaan dibandingkan hingga diperoleh struktur data representasi simpul yang sesuai untuk berbagai kasus.
a. Pemilihan Stuktur Data
Pada kasus penyisipan pada urutan acak pohon tidak seimbang merupakan pilihan yang terbaik karena waktu yang dibutuhkan singkat dan ruangan yang kosong banyak. Sebaliknya jika penyisipan dilakukan pada data yang terurut pohon tidak seimbang ini jauh lebih buruk dibandingkan dengan pohon merah hitam ataupun pohon AVL. Pada kasus penyisipan data acak, namun dalam menjalankan program mengikutsertakan program pengurutan maka pohon merah hitam lebih baik dibandingkan pohon AVL karena pohon merah hitam lebih memerlukan kerja yang lebih sedikit dalam aturan penyeimbangan dalam menyeimbangkan data acak.Pohon splay sangat tidak direkomendasikan karena pengorbanan dalam hal splaying setiap akses. Untuk pohon splay merupakan pilihan terbaik saat program yang berikutnya merupakan data yang sekuensial (seperti pada percobaan VMA).
b. Pemilihan Representasi Simpul
Parent pointer merupakan yang terbaik diikuti representasi thread. Namun thread lebih baik digunakan saat ruang minimum karena penggunaan memory lebih sedikit. Representasi plain tanpa parent pointer atau thread lebih hemat waktu dalam meng-update penambahan bidang, namun tampaknya menghalangi efisiensi dalam implementasi t_delete. Representasi simpul list berkait merupakan pilihan terbaik pada percobaan VMA yang menggunakan operasi traversal t_next dan t_prev, namun sangat susah untuk internet peer. Hal ini disebabkan pengorbanan memory yang tinggi karena menggunakan dua penunjuk/pointer dalam satu simpul terutama jika traversal jarang dilakukan. Perpresentasi right thread tidak terlalu mendukung karena cara yang tidak efisien dalam hal implementasi t_delete.
C. Sebuah Program Menggunakan Bahasa Pascal
Program grafik;
uses crt;
type
tahun= array[1..6] of byte;
procedure input(var Thn: Tahun);
var i: byte;
begin
clrscr;
gotoxy(5,1); write('Data : (Dalam Jutaan)');
for i:=1 to 6 do
begin
repeat
gotoxy(5,2+i); write('Tahun ',i,' :');
gotoxy(16,2+i); ClrEol;
gotoxy(16,2+i); Readln(Thn[i]);
until (Thn[i] > 0) and (Thn[i] < 16);
end;
end;
Procedure gambar (Thn: Tahun);
var i, j: byte;
begin
for i:=0 to 14 do
begin
gotoxy(35,2+i); write(15-i:2,'|' );
end;
gotoxy(36,17); write(0,' ');
for i:= 1 to 34 do write('-');
gotoxy(39,18); write('2003 2004 2005 2006 2007 2008');
gotoxy(48,21); write('Jumlah Mahasiswa');
gotoxy(43,22); write('Universitas Serambi Mekkah');
for i:= 1 to 6 do
for j:= 1 to Thn[i] do
begin
gotoxy(33+i*6, 17-j); write('|**|');
end;
ReadKey;
end;
var Data : Tahun;
begin
Input(Data);
Gambar(Data);
end.
Hasil Output :
Data : (Dalam Jutaan)
15|
Tahun 1 : 1 14|
Tahun 2 : 3 13|
Tahun 3 : 4 12|
Tahun 4 : 5 11|
Tahun 5 : 7 10|
Tahun 6 : 9 9| |**|
8| |**|
7| |**| |**|
6| |**| |**|
5| |**| |**| |**|
4| |**| |**| |**| |**|
3| |**| |**| |**| |**| |**|
2| |**| |**| |**| |**| |**|
1| |**| |**| |**| |**| |**| |**|
0 --------------------------------------------
2003 2004 2005 2006 2007 2008
Jumlah Mahasiswa
Universitas Serambi Mekkah
Bisnis Online Pemula
