Dasar Kerja Pengaplikasian Self-balancing Binary Search Tree untuk Pencarian sebagai Struktur Data yang Lebih Mangkus dan Sangkir

1

Dasar Kerja Pengaplikasian Self-balancing Binary Search Tree untuk Pencarian sebagai Struktur Data yang Lebih Mangkus dan Sangkir Michell Setyawati Handaka (135 08 045) Program Studi Teknik Informatika Sekolah Teknik Elektro dan Informatika Institut Teknologi Bandung Jl. Ganeca no. 10, Bandung e-mail: [email protected]

ABSTRAK Proses pencarian adalah salah satu operasi paling krusial dalam pengolahan data, khususnya mengingat perkembangan ruang memori yang makin lama, tak ayal lagi, akan menjadi –dapat dikatakan– tidak terbatas. Dengan proses pencarian secara traversal, kompleksitas waktu dalam notasi asimptotik setara dengan O(n) yang dalam hal ini tergolong algoritma polinomial yang mangkus dalam spektrum waktu. Akan tetapi, dengan pencarian biner, kompleksitas dapat ditekan sampai kepada tingkat O(log n) saja, yang tentunya jauh lebih baik. Pencarian secara rekursif dapat dilakukan dengan memanfaatkan tipe struktur data yang juga rekursif, seperti pohon –yang dalam hal ini adalah pohon biner–. Ide pencarian biner hanya dapat dilakukan terhadap suatu data yang sudah terurut dengan baik, dalam struktur data pohon, tipe yang demikian ini dikenal dengan nama pohon biner terurut. Persoalan berikutnya adalah, pencarian pada pohon biner terurut sangat bergantung kepada tinggi pohon, sehingga akan sangat menguntungkan jika kedalaman suatu pohon dapat dibuat minimum. Hal ini dapat dicapai dengan pendekatan pohon biner seimbang, dimana kedalaman pasti minimum dan banyak simpul per aras berjumlah maksimum. Untuk membangun suatu pohon seimbang sebenarnya sangat mudah. Akan tetapi permasalahan yang dihadapi adalah ketika kita ingin pohon seimbang ini terurut dan proses penyeimbangan haruslah tidak mengganggu keterurutan data. Untuk menangani kasus ini, dapat digunakan suatu struktrur data baru yang dikenal sebagai selfbalancing binary search tree. Pada struktur data ini, kompleksitas waktu pencarian akan selalu bernilai O(log n). Hal yang demikian ini dapat tercipta karena pohon merepresentasikan pohon terurutnya dalam porsi yang seimbang. Untuk menjaga struktur data yang demikian ini, diperlukan suatu operasi tambahan, yakni pemeliharaan struktur, setiap kali penyisipan atau penghapusan dilakukan. Menariknya,

operasi ini tidaklah mengubah kompleksitas waktu baik penyisipan maupun penghapusan tanpa pemeliharaan struktur : yakni tetap O(log n). Kata kunci: pohon biner terurut, pohon biner seimbang, pencarian beruntun, pencarian biner, self-balancing binary seacrh tree : pohon Red-black, pohon AVL, pohon AA, pohon Splay, pohon Scapegoat, Treap.

1. PENDAHULUAN Dewasa ini, kapasitas divais penyimpanan data / memori terus menerus bertumbuh membesar dengan laju yang mana kian lama kiat pesat. Sebagai acuan, dalam waktu satu tahun, kapasitas HDD –Hard Disk Drive– meningkat 50% dari yang semula hingga kini (tahun 2009) hanya mencapai 2TB akan segera menjadi 3TB pada tahun 2010[3]. Sementara itu, kapasitas memori selalu diidentikkan pertumbuhannya berlawanan dengan kecepatan pengolahan. Dapat diibaratkan, memori beranalogi dengan sebuah tas : semakin besar ukuran tas, semakin besar pula kapasitas tas tersebut untuk dapat menampung barangbarang yang akan dimasukkan ke dalamnya; akan tetapi, hal ini juga diimbangi dengan bertambah beratnya beban tas tersebut. Dengan demikian, salah satu hal yang menjadi concern masyarakat umum saat ini adalah mencari devais memori yang memiliki kapasitas besar namun tidak memberatkan, atau setidaknya memiliki efektivitas kinerja tinggi. Salah satu operasi mendasar yang sering dilakukan dalam pengolahan maupun penggunaan data adalah searching atau yang lebih dikenal sebagai proses pencarian. Proses pencarian data mendapat porsi prioritas yang semakin tinggi seiring dengan meningkatnya ruang memori, mengingat hal ini menjadi krusial jika pengguna sedikit “jorok”. Bahkan, ketika pengguna berlaku apik sekalipun, bukan tidak mungkin tempat suatu data tertentu disimpan menjadi terlupakan akibat proses fragmentasi

MAKALAH IF2091 DASAR KERJA PENGAPLIKASIAN SELF-BALANCING BINARY SEARCH TREE UNTUK PENCARIAN SEBAGAI STRUKTUR DATA YANG LEBIH MANGKUS DAN SANGKIR TAHUN 2009

2

meemori yang terlampau banyak diakkibatkan kareena beesarnya ukurann memori. Adapun rata--rata jumlah waktu w yang diibutuhkan unttuk suuatu proses pencarian p meenggunakan traversal dalam koompleksitas assimtotik adalaah O(n); semeentara itu, proses peencarian mengggunakan binnary search tree t atau pohhon binner terurut hannya memakann sejumlah O(llog n) saja, yaang tenntunya lebih baik. b

2.. STRUKT TUR DATA A (TERLAM MPIR) 3.. DASAR TEORI T PR ROSES PEN NCARIAN Pada umumnnya, algoritm ma untuk prroses pencarian beeruntun (sequuential searcch) pada suaatu list adalah sebbagai berikut :

atauu dst. dengan prooses rekursiif yang demikian d puun, ko ompleksitas waktunya w adalaah atau O(n). Jadi, keuntunngan penggunaaan struktur data d pohon unttuk prroses pencariaan beruntun hhanyalah algorritma yang lebbih rin ngkas karenaa penanganaan kasus diilakukan secara rek kursif. Lain halnya,, jika data yyang kita miiliki sudah kita k urrutkan sebelum mnya. Ide innilah yang mendasari m proses peencarian binerr (binary seacrrh). Pada prosess pencarian menggunakan n pohon binner terrurut, algoritm manya menjaddi sebagai beriikut : Perikksa akar pohoon Jika sama −> selesai Jika tidak sama − −> bandingkan n Jika X yang dicarri lebih kecil daripada d Akarr(P) −> cari di upapohhon kiri Jika lebih besar − −> cari di upaapohon kanan

>>

attau

<< deengan atau O(nn). Adapun skem ma pencariann untuk strukktur data beruupa poohon biner dappat digambarkkan sebagai beerikut :

Perikksa akar pohoon Jika ketemu −> selesai s Jika tidak ketemuu −> cari di d upapohon kiri k atau upapohon kannan

waktu yang diiperlukan secara dengan demikian, besar w otomatis pasti berkurang m mengingat sek karang pencarrian beerikutnya, jikka diperlukaan, hanya dilakukan d paada up papohon kiri saja s atau upapoohon kanan saaja. Adapun benttuk suatu poohon biner teerurut sangattlah beergantung keppada urutan masukan dan n semakin tiddak terrurut masukann yang diberiikan hasilnya akan cenderuung seemakin baik, sebagai contohh : Data : 12 14 17 19 223 50 54 67 72 76 9 Urutan masukkan : 23 14 119 12 76 54 72 67 50 0 17 9 Hasil :

X

DASAR A KERJA PENGAPLIKASIIAN SELF-BALAANCING BINARY SEARCH TREEE UNTUK PENC CARIAN SEBAG GAI STRUKTUR R DATA YANG G LEBIH E MANGKU US DAN SANGK KIR

3

Urutan masukkan : 500 17 12 23 9 Hasil :

14

19

72

54

76

67

seeimbang tanpaa merusak ketterurutan poho on biner terurrut. Jaawaban dari persoalan p ini adalah pohon n biner teruruut – seeimbang (self-bbalancing binnary search treee).

4.. SELF-BA ALANCING G BINARY Y SEARCH H [11] TREE

Demikian pulla jika data yaang dimasukkkan sudah teruurut (m membesar / meengecil), makka pohon yangg terbentuk akkan tenntu berbeda pula, yakni terbentuk pohon p condoong (kkanan / kiri). Sementara ituu, dengan algoritma pencarrian pada pohhon binner terurut, beentuk pohon yang y menjadii input sangatlah beerpengaruh teerhadap kebuttuhan waktu daripada suatu prroses pencariaan. Seandainnya bentuk masukan m adalah poohon biner terurut conndong, makaa kompleksiitas waaktunya adalaah O(n). Akaan tetapi, jikaa bentuk pohhon yaang diberikann adalah yanng menyeruppai pohon paada coontoh terakhir,, kompleksitas waktu menjadi hanya O(llog n), yang tentunyya tak dapat disangkal d lagii akan lebih baik –leebih mangkuus (efektif) dan d lebih sanngkir (efisienn)–. M Mengapa hal inni dapat terjadii? Jika kita perhatikan, paada kasus pohon p terakhhir, peencarian selannjutnya hanyya dikenakan pada setenggah jum mlah dari penncarian sebeluumnya. Kasuss yang demikian jellaslah menunnjukkan suatuu fungsi loggaritmik denggan baasis 2. Prosess pencarian yang demikiann ini dinamakkan sebbagai proses pencarian p bineer. Pohon teruruut yang dapatt menekan kebutuhan wakktu peencarian adalah pohon dengan jum mlah kedalam man miinimum denggan cara mem maksimumkann jumlah simppul peer arasnya. Poohon yang dem mikian ini adaalah pohon binner seimbang. Dengan deemikian, maasalah selannjutnya adalah baagaimana mem mbuat suatu pohon p biner yang seimbanng. Addapun algorritma untuk pembuatan pohon binner seimbang secaraa umum adalaah sebagai berrikut ini :

Yang menjaddi pertanyaan berikutnya b addalah, bagaimaana meenggunakan algoritma a unttuk membenttuk pohon binner

Sebagian beesar operasi pada pohon n biner teruurut membutuhkan waktu w yang ssebanding den ngan kedalam man daaripada pohoon tersebut, sehingga ak kan jauh lebbih menguntungkann jika kedalam man pohon daapat dijaga unttuk tettap minimal. Self-balancing S g binary searrch tree / heigghtba alanced binarry search treee adalah pohon biner teruurut yaang secara otomatis o mem mpertahankan n kedalamannnya un ntuk tetap minimum m denggan cara mellakukan operrasi peenyisipan dan / atau penghaapusan. Mengingat pohon p biner dengan kedaalaman h daapat memuat sebaanyaknya 2 2 ⋯ 2 2 −1 sim mpul, maka berlaku b bahwa kedalaman minimum suuatu po ohon biner deengan jumlahh simpul seb banyak n adaalah dengann pembulatan ke bawah, attau dapat dituulis log . og lo Menjaga kedaalaman suatu pohon biner untuk u tetap paada – ternyataa tidaklah daapat nilai minimum mnya – log dilakukan menggingat algoritm ma pengolahaannya melakukkan ek ksploitasi yang y berlebbihan. Deng gan demikiian, keebanyakan alggoritma self-bbalanced BST T hanya menjaaga ag gar kedalamann dari suatu ppohon biner selalu dibatasii di ataas oleh suatuu konstanta yyang merupak kan suatu fakktor daari batas minim mum log . Adapun implementasi sesuungguhnya dari self-balancing binary search tree adalah menggunakaan struktur data d seeperti yang terttera di bawah ini, di antaran nya : <so ource-code / ilusstrasi untuk setiaap uraian di baw wah ini terlampiir> [12] RED E -BLACK TRE EE / SYMMETR RIC BINARY B--TREES

Pohon P Red-bblack memilikki struktur yang y kompleeks, tettapi hal ini diimbangi ddengan komp pleksitas wakktu op perasinya yanng baik selainn daripada kemangkusann k nya daalam dunia prraktis : operasi pencarian, penyisipan, dan d peenghapusan hanya mem miliki kompleksitas wakktu asimtotik setaraa O(log n) sajaa. Dalam D pengggunaanya, daaun pada po ohon Red-blaack tid daklah digunaakan untuk meenyimpan data sehingga tiddak memakan ruangg memori padda praktisnya; akan tetapi, jika daaun-daun ini tetap disimpaan secara ekssplisit, beberaapa alg goritma pengoolahannya meenjadi lebih seederhana. Dalam prrakteknya, poiinter kepada daun dapat hanya h satu buuah eleemen dummy / sentinel sajja bagi satu pohon p Red-blaack deengan semuaa elemen daaun mengacu u pada alam mat terrsebut.

G Gambar 4.1. P Pohon Red-blacck


4

Setiap simpul pada pohon Red-black memiliki atribut warna, yang mana hanya mungkin merah saja atau hitam saja. Adapun karakteristik lainnya –selain daripada karakteristik standar pada pohon biner terurut– dari pohon Red-black adalah sebagai berikut ini : 1. Suatu simpul hanya dapat merah saja atau hitam saja. 2. Atribut warna akar adalah hitam. (atribut warna suatu simpul yang menjadi akar hanya dapat berubah dari merah menjadi hitam). 3. Seluruh daun berwarna hitam. 4. Setiap anak dari seluruh simpul merah berwarna hitam. 5. Setiap lintasan sederhana dari suatu simpul yang diberikan kepada sebarang daun keturunannya berukuran sejumlah simpul hitam. Batasan karakteristik di atas berimplikasi kepada sifat kritis dari sebuah pohon Red-black : lintasan terpanjang dari akar ke sebarang daun tidak mencapai dua kali ukuran lintasan terpendek dari akar ke daun lainnya. Dengan demikian, secara umum, pohon dapat dikatakan seimbang. Karakteristik ini dapat terlaksana karena : tidak ada lintasan yang mengandung dua simpul merah secara berturutan. lintasan terpendek yang mungkin hanya mengandung simpul hitam, dan alternatif lintasan terpanjang yang mungkin mengandung simpul merah dan hitam berselingan. setiap lintasan terpanjang berukuran sejumlah seluruh simpul hitam sehingga tidak mungkin ada lintasan yang mencapai lebih dari dua kali panjang lintasan lainnya. Dampak lain daripada karakteristik di atas adalah setiap simpul internal pada pohon Red-black pastilah memiliki dua anak, yang mana salah satu atau keduanya mungkin kosong. Operasi pembacaan pada pohon Red-black menyerupai operasi standar pada BST. Akan tetapi, pada operasi penyisipan dan penghapusan, dibutuhkan suatu mekanisme perbaikan untuk menjaga agar karakteristik pohon Red-black tidak dilanggar. Operasi perbaikan ini memiliki kompleksitas waktu yang sangat baik, yakni sebesar O(log n) atau O(1) saja dan merupakan operasi yang dibutuhkan untuk mengubah warna simpul dan tidak lebih dari tiga operasi tree rotation. Dengan demikian, operasi penyisipan dan penghapusan tetap memiliki kompleksitan waktu O(log n). Penyisipan Penyisipan dimulai dengan menambahkan sebuah simpul, seperti pada penyisipan dalam BST, yang kemudian diwarnai dengan merah. Penyisipan selalu menggantikan sebuah daun hitam dengan simpul dalam yang berwarna merah dengan dua buah anak berupa daun hitam. Langkah selanjutnya ditentukan oleh warna simpul lain di sekitar simpul baru tersebut. Adapun kondisi pada saat penyisipan baru dilakukan adalah sebagai berikut ini : Sifat (3) selalu tetap terjaga.

Sifat (4) terancam dilanggar hanya jika terjadi penambahan simpul merah, mewarnai ulang suatu simpul hitam menjadi merah, atau terjadinya rotasi. Sifat (5) terancam dilanggar hanya jika terjadi penambahan simpul hitam, mewarnai ulang suatu simpul merah menjadi hitam, atau terjadinya rotasi. Catatan : N −> simpul yang disisipkan; P −> ayah N; G −> ayah P; U −> saudara P. Dalam bahasa C, simpul U dan G ditemukan dengan cara : struct node * grandparent(struct node *n) { if ((n != NULL) && (n->parent != NULL)) return n->parent->parent; else return NULL; } struct node * uncle(struct node *n) { struct node *g = grandparent(n); if (g == NULL) return NULL; // No grandparent means no uncle if (n->parent == g->left) return g->right; else return g->left; } KASUS 1 : SIMPUL N MENJADI AKAR POHON RED-BLACK,

dengan demikian pewarnaan ulang menjadi hitam dilakukan untuk memenuhi sifat (2). Semenjak penambahan ini menambahkan satu simpul hitam ke seluruh lintasan sekaligus, sifat (5) tetap terjaga. KASUS 2 : SIMPUL P BERWARNA HITAM, dengan demikian sifat (4) tetap valid. Karena simpul N berwarna merah, sifat (5) tetap berlaku. KASUS 3 : Ketika baik simpul P MAUPUN SIMPUL U BERWARNA MERAH, maka kedua simpul ini dapat diwarnai ulang menjadi hitam sementara simpul G menjadi merah untuk menjaga sifat (5). Akan tetapi, hal ini (simpul G diwarnai merah) dapat berimbas kepada pelanggaran sifat (2) atau (4) −> jika ayah G berwarna merah. Untuk menyelesaikan masalah ini, dapat dilakukan secara rekursif dengan “N” yang baru adalah G. KASUS 4 : Pada kasus ini, SIMPUL P BERWARNA MERAH TETAPI SIMPUL U BERWARNA HITAM; JUGA BERLAKU SIMPUL N ADALAH ANAK KANAN DARI P, SEMENTARA P ADALAH ANAK KIRI DARI G. Dalam pada kasus ini, left rotation (pertukaran antara simpul N dan simpul P) dapat dilaksanakan untuk kemudian simpul P masuk ke dalam kasus 5 (penamaan ulang simpul N dan P) dikarenakan sifat (4) masih tetap terlanggar. Pada rotasi ini,

DASAR KERJA PENGAPLIKASIAN SELF-BALANCING BINARY SEARCH TREE UNTUK PENCARIAN SEBAGAI STRUKTUR DATA YANG LEBIH MANGKUS DAN SANGKIR

5

karena kedua simpul berwarna merah, maka sifat (5) tidak terganggu. Catatan : untuk P sebagai anak kanan, left dan right tinggal dipertukarkan. KASUS 5 : SIMPUL P BERWARNA MERAH TETAPI SIMPUL U BERWARNA HITAM, SIMPUL N ADALAH ANAK KIRI DARI P, DAN P JUGA ADALAH ANAK KIRI DARI G. Dalam pada kasus ini, right rotation terhadap simpul G dilakukan; hasilnya adalah pohon dimana P menjadi ayah dari baik simpul N maupun simpul G. Simpul G pastilah berwarna hitam karena jika tidak, P tidak mungkin berwarna merah. Dengan demikian, yang perlu dilakukan adalah menukar warna antara P dan G sehingga sifat (4) terpenuhi. Sementara itu, sifat (5) tetap terjaga karena ketika sebelumnya hanya terdapat satu buah simpul hitam G, maka sekarang juga hanya terdapat satu buah simpul hitam P. Catatan : untuk P sebagai anak kanan, left dan right tinggal dipertukarkan. Penghapusan Pada BST biasa, penghapusan sebuah simpul dengan kedua anak yang bukan daun, dilakukan dengan pertama-tama mencari elemen dengan nilai maksimum pada upapohon kirinya atau elemen dengan nilai minimum pada upapohon kanannya, untuk kemudian memindahkan nilai tersebut ke simpul yang dibuang. Simpul yang nilainya disalin ini kemudian dibuang (simpul ini pasti memiliki anak-bukan-daun kurang dari dua). Karena proses penghapusan yang demikian tidaklah mengganggu validitas pohon Red-black, kasus yang perlu diperhatikan selanjutnya hanyalah penghapusan simpul dengan anak-bukan-daun sebanyaknya satu saja. Ketika sebuah simpul merah dibuang, kita dapat dengan mudahnya mengganti simpul tersebut dengan simpul anak yang pasti berwarna hitam. Dalam proses ini, sifat (3) dan (4) akan tetap terjaga karena perubahan pada lintasan yang terjadi hanyalah berkurangnya sebuah simpul merah yang dilalui. Kasus khusus lainnya adalah ketika simpul yang dibuang berwarna hitam dan anaknya berwarna merah. Dengan hanya memindahkan simpul tersebut akan berdampak kepada kerusakan sifat (4) dan (5), tetapi dengan pewarnaan ulang simpul anak menjadi hitam, masalah terselesaikan. Kasus sesungguhnya yang cukup kompleks untuk diselesaikan adalah ketika simpul yang ingin dihilangkan dan anaknya sama-sama berwarna hitam. Penyelesaian ini dimulai dengan menggantikan simpul yang akan dibuang dengan anaknya. Catatan : N −> simpul anak yang telah menggantikan simpul yang ingin dibuang; P −> ayah N; S −> saudara N; SL −> anak kiri S dan SR −> anak kanan S karena S tidak mungkin daun.

Warna putih dapat berarti hitam saja atau merah saja. Dalam bahasa C, simpul S dapat ditemukan dengan cara : struct node * sibling(struct node *n) { if (n == n->parent->left) return n->parent->right; else return n->parent->left; }

Fungsi replace_node menggantikan child ke tempat N. void delete_one_child(struct node *n) { /* * Precondition: n has at most one nonnull child. */ struct node *child = is_leaf(n->right) ? n->left : n->right; replace_node(n, child); if (n->color == BLACK) { if (child->color == RED) child->color = BLACK; else delete_case1(child); } free(n); }

Dengan perlakuan yang seperti ini, sifat (5) akan menjadi terlangkahi karena simpul yang dibuang berwarna hitam sehingga jumlah simpul hitam berkurang satu dan berakibat pada perbedaan panjang lintasan yang melalui simpul tersebut dan yang tidak. KASUS 1 : SIMPUL N MENJADI AKAR POHON RED-BLACK; dalam kasus ini, masalah selesai. Semenjak penghapusan ini mengurangi satu simpul hitam dari seluruh lintasan sekaligus, sifat (5) akan tetap terjaga. Dan akar yang baru berwarna hitam membuat seluruh sifat terpenuhi. Catatan : Pada kasus 2, 5, dan 6, diasumsikan bahwa N adalah anak kiri dari P. Jika N adalah anak kanan, left dan right tinggal dipertukarkan. KASUS 2 : S BERWARNA MERAH; dalam kasus ini, kita menukarkan warna antara P dan S, untuk lalu kemudian melakukan rotasi kiri pada P, menyebabkan S menjadi ayah P. KASUS 3 : P, S, DAN ANAK DARI S BERWARNA HITAM; dalam kasus ini, kita cukup mewarnai ulang S menjadi merah. Pohon yang dihasilkan menyebabkan semua lintasan melalui S, yang berarti pasti tidak melalui N, memiliki lebih sedikit satu simpul hitam sebanyak satu buah. Faktanya adalah, pembuangan ayah asli dari N juga mengurangi satu simpul hitam pada setiap lintasan yang melalui N, sehingga masalah ini menjadi terpecahkan. Akan tetapi, sekarang semua lintasan yang melalui P menjadi


6

memilikii kurang satu buah simpul hitam dibandinngkan dengann lintasan yanng tidak melaalui P, sehhingga sifatt (5) dilaanggar. Unttuk menyelesaikannya, dilakukan penyeimbanggan ulang terrhadap P dimuulai dari kasuss 1. KASUS 4 : S DAN ANAK DARI S BERWARNA HITAM H , TETAPPI P BERWAR RNA MERAH; dalam kasus ini, kita cuk kup menukarrkan warna anntara P dan S. Hal ini tiddak akan beerpengaruh teerhadap jumllah dari simppul hitam paada lintasan yang melaluii S, akan tetapi menambbahkan satu simpul padaa lintasan yaang melalui N untuk menggantikan m n simpul yaang dibuang.. KASUS 5 : S BERW WARNA HITAM M, SL BERWAR RNA MERAH, SR BERWAR RNA HITAM, DAN D N ADALLAH ANAK KIIRI; dalam kaasus ini, kita melakukan rootasi kanan paada S sehingggaSL menjadii ayah S dan saudara s baru dari d N. Pertuukaran warna juga dilakukan antara S dan d ayah barrunya. Seluruuh lintasan akkan mempunyyai jumlah simpul s hitam yang y tetap, akkan tetapi N kini k mempunnyai saudara yang mana anak kanannnya berwarnaa merah (kasus 6). Baaik N mauppun ayahnya tidak terpenggaruh oleh trannsformasi ini. KASUS 6 : S BERW WARNA HITAM M, SR BERWAR RNA MERAH, DAN D N ADALA AH ANAK KIRI DARI P; dalam m kasus ini, kita k melakukkan rotasi kirii pada P sehiingga S menjadi ayah P dan SR. Pertukaran P w warna kemudian dilakukaan antara P dan d S, semenntara SR dibuuat menjadi hitam. Upappohon yang terbentuk akkan tetap mempunyai m a akar yang berwarna b sam ma sehinggaa sifat (4) dann (5) tidaklah dilanggar. Akkan tetapi, N kini memppunyai tambaahan satu buuah leluhur yang y berwarnna hitam : mungkin m P yaang menjadi hitam atau tam mbahan S yanng juga hitam. Semenntara itu, linttasan yang tiidak melalui N mempunnyai dua buah kemungkinann : lintasan melalui m saudara baru N sehingga berarti b melaluii S dan P yaang mana hanya bertukar tem mpat dan warrna, sehingga liintasan tetap memilki jumlah simpul hitaam yang tetap. lintasan meelalui paman baru dari N, SR sehingga beerarti yang seemula melaluii S, ayah S, dann anak kanan S yang awalnnya merah; meenjadi melaluui lintasan baaru yang hanyya melewati S yang kini k warnanya mengikuti m ayaah lamanya dan d SR yang warnanya telah berubbah a adalah menjadi hiitam. Hasil akhirnya jumlah siimpul hitam m yang dilaalui berjumlah sama. s Yang manapun yaang terjadi, pada akhirnnya jumlah simpul hitaam pada linntasan tidaklah berubah sehingga sifatt (4) dan sifat (5) terjaga.

AV VL TREE[13] Pohon P AVL memiliki m struuktur yang menyerupai m B BST tettapi ditambahhkan dengan bbalance factorr. Balance facctor daari suatu simppul adalah keddalaman dari upapohon u kannan dik kurangi kedallaman dari uppapohon kiri sehingga pohhon yaang seimbangg adalah merreka yang memiliki m balannce factor bernilai -1, 0, atau 1.. Pohon yang tidak seimbaang ak kan mengalam mi rotasi. Penyisipann (Basis 0)

Gam mbar 4.11. Prosses Penyeimba angan

Jika P adalah a akar poohon tak seim mbang, L adaalah anak kiri, dan R adalahh anak kanan n, maka keem mpat kasus yangg harus ditanggani meliputi : KASUS KANAN-KANA AN ATAU KASU US KANAN-KIR RI :

BALANC CE FACTOR DA ARI P ADALAH H -2; jika balan nce factor dari d R adalah -1, maka rotasi kiri padaa P dilakukaan, sementaraa jika balancee factor dari R adalah +1, + maka rotaasi dua kali harus h dilakukkan, yakni peertama rotasi kkanan pada R lalu dilanjutkkan dengan rotasi r kiri pada P. KASUS KIRI-KIRI AT TAU KASUS KIR RI-KANAN:

BALANC CE FACTOR DARI P ADA ALAH +2; jika balance factor f dari L adalah +1, maka m rotasi kannan pada P dilakukan, seementara jikaa balance facctor maka rotasi dua kali haarus dari L adalah -1, m dilakukaan, yakni perttama rotasi kiri k pada L lalu dilanjutkkan dengan rotasi kanan pad da P. Penghapusaan (Basis -1 aatau 1)

Gambar G 4.12. Proses Penghap pusan dengan Penggantian P olleh S Inorderr Predecessor aatau Inorder Successor

AA A TREE[14] Pohon P AA addalah merupaakan variasi dari d pohon Reedblack dimana simpul meraah hanya dap pat ditambahkkan seebagai anak kanan k dengann demikian menyederhanak m kan prroses pemelihaaraan keseimbbangannya.

(aa) Kasus pada Pohon Red-bla ack


7

(b) Kasus paada Pohon AA Gambaar 4.13.

Karakteristik pohon K p AA : 1. Leveel dari daun addalah satu. 2. Leveel dari anak kiri k pastilah lebih kecil dari d ayahnnya. 3. Leveel dari anak kanan k dapat lebih kecil dari d atau sama dengan ayahnya. 4. Leveel dari cucu kanan k pastilah lebih kecil dari d kakekknya. 5. Setiaap simpul denngan level dii atas satu paasti mem miliki dua anakk. H Hanya ada duua macam opperasi untuk mempertahank m kan keeseimbangan pohon AA, yakni y skew dan d split. Skkew addalah rotasi kaanan yang dilaakukan ketikaa penyisipan atau peenghapusan menghasilkan m left horizontaal link (left red r linnk pada pohonn Red-black) sementara spplit adalah suatu peengkondisian rotasi kiri akkibat terbentuuknya dua buuah hoorizontal righht links (two consecutive red links paada poohon Red-blacck).

G Gambar 4.14. (a) Skew (b) Spplit

Penyisipan Penyisippan dilakukan seperti terhaddap BST standdar. Jika terjaddi sebuah horiizontal left linnk, operasi skkew akan dilakkukan; semenntara jika teerjadi dua buuah horizontall right links, operasi split akan dilakukkan bahkan mungkin m peninngkatan level dari akar baaru dari upapoohon ini. Penghapusaan Penghappusan dilakukkan sama sepperti pada BS ST, dimana suuksesor (yang pada BST dittemukan denggan cara menggambil lintasann melalui sem mua anak kiri dari d anak kanann simpul) dann predesesor (yang pada BST ditemukann dengan caraa mengambil lintasan melaalui semua anak kanan daari anak kiri simpul) adalah simpul denngan level 1, sehingga s muddah dilakukan. Sesudah penghapusann, langkah perttama yang harrus dilakukan untuk menjaga sifat pohon AA adalah menurunkan level darii semua sim mpul yang maana anaknya berada b pada dua d tingkat di bawah mereka, atau sim mpul-simpul yang kehilaangan anaknnya. Selanjutnyya, pada seluuruh level dillakukan operrasi skew dan split. s Mennurunkan leveel, jika diperluukan Mellakukan operaasi skew pada level l Mellakukan operaasi split pada leevel

[15] P TREE SPLAY Pohon P Splay adalah a merupaakan self-bala ancing BST yaang mana memiliki karakteristiik tambahan berupa elem men yaang baru diaksses dapat diakkses ulang den ngan cepat. Splaying Ketika simpul s X diakkses, operasi splay dilakukkan untuk mem mindahkannya ke posisi akaar. Adapun splay steps dipenngaruhi oleh tiiga buah fakto or berikut ini : X sebagai s anak kiri atau an nak kanan dari d simppul P. P seebagai akar, atauu jika bukan, P sebagai anaak kiri atau annak kanaan dari simpul G. Tipe-tipee splay steps : Zig Step : L Langkah ini diilakukan ketik ka P adalah akkar denggan cara rotaasi pada sisi antara a X dan P. Zig step dilakukkan hanya pada p akhir dari d operrasi splay kketika X memiliki m tingkat kedaalaman yang gganjil pada saat awal operassi. Zig--zig Step : L Langkah ini diilakukan ketik ka P bukan akkar dan baik X mauppun P adalah sama-sama annak kiri atau sama-saama anak kan nan. Langkah ini dilakkukan dengann cara rotasi pada sisi antaraa P dan G, lalu keemudian dilanjutkan denggan rotaasi pada sisi aantara X dan P. Zig-zig step adallah satu-satunnya perbedaaan antara pohhon Splaay dengan mettode rotate to root. Zig--zag Step : L Langkah ini diilakukan ketik ka P bukan akkar dan X adalah anaak kanan sem mentara P adaalah anakk kiri atau sebaliknya.. Langkah ini dilakkukan dengann cara rotasi paada sisi antaraa X dan P, lalu kemuddian dilanjutk kan dengan rottasi padaa sisi antara X dan G. Penyisipann Pertama--tama, X diccari pada poh hon Splay; jika tidak ditem mukan, maka aakan dicari sim mpul Y, ayah X. Langkah seelanjutnya adaalah melakuk kan operasi splay pada Y unttuk lalu kemuudian menyisiipkan X sebaagai akar dengaan cara yangg tepat. Deng gan demikian Y akan menjaadi anak kiri aatau anak kanaan dari X. Penghapusaan Lakkukan operasi ssplay pada sim mpul X. Lakkukan operasi tree rotation n pada anak kiri k perttama dari X sehingga anak kiri tersebbut tidakk memiliki annak kanan. Happus X dari pohhon dan gantik kan akar denggan anakk kiri pertamaa dari X. [16] SCAPEGOAT C TRE EE [17] TREAP R Treap T adalahh gabungan antara tree dan heap dan d merupakan pohhon Cartesiann dimana settiap key (dipiilih seecara acak) diiberikan priorritas numerik. Urutan inordder tra aversal dari simpul sam ma dengan urrutan key yaang terrurut. Struktuur pohon inii ditentukan oleh kebutuhhan baahwa pohon haruslah h heap--ordered : yaiitu nilai prioriitas


8

daari semua simppul bukan akaar harus lebih besar atau sam ma deengan nilai priioritas dari ayaahnya.

V. V KESIMPULAN Self-balancinng binary seearch tree memiliki m operrasi tam mbahan, yaiitu operasi pemeliharaan n, pada proses peenyisipan attaupun pengghapusan untuk u menjaaga strrukturnya agaar tetap teruruut dan seimbaang. Akan tetaapi, op perasi ini tidaaklah mengubbah nilai kom mpleksitas wakktu seecara keselurruhan dari proses peny yisipan mauppun peemeliharaan, atau a dengan kaata lain kompleksitasnya tetap O((log n). Nam mun demikiaan, proses lainnya l –sepeerti peencarian–, menjadi lebih ceepat dilaksanaakan yaitu hannya paada tingkat O(log O n) saja, dimana semu ula adalah O((n). Seebagai acuan, untuk n = 1.0000.000, log n = 19. Jadi, dapat diikatakan strukktur data yang g optimum unttuk su uatu proses peencarian adalaah dengan meenggunakan seelfba alancing binarry search treee.

Gambar 4.21. 4 Treap

Operasi pada Treap : O Proses peencarian sam ma seperti padda BST denggan tidak mem mperhatikan prioritas. p Penyisipaan key baru X pada Treap T dilakukkan dengan membangkittkan y, suatu s prioriitas sembaranng pada X. Selama X bukan b akar dan d memiliki prioritas lebbih kecil daari Z, ayahnnya, dilakukann tree rotatioon untuk mennukarkan possisi keduanyaa. Penghapuusan simpul X dilakukaan dengan cara adalah dauun; menghilaangkannya jika ia mengganttikannya denggan Z, anak tunggal X; attau menukarkkan posisinya dengan Z, suuksesor langsuung X dalam urutan, jika X memiliki dua d anak. Dalam kasus yaang terakhir, mungkin dipperlukan operrasi rotasi tam mbahan untuk menjaga sifatt heap-orderinng. Membagii Treap menjaadi dua bagiaan di mana yaang satu menjjadi lebih keccil dari suatu nilai key X dan d yang lainn lebih besar dapat dilakukkan dengan cara penyisipaan X dengan prioritas terkkecil. Proses ini akan mennjadikan X sebagai s akar,, upapohon kiri k sebagai bagian b yang lebih kecil, dan upapohhon kanan sebbagai bagian yang y lebih bessar. Menggabbungkan dua buah b Treap, dapat dilakukkan dengan mengasumsika m an bahwa nilaai terbesar paada Treap yaang satu lebihh kecil daripaada nilai terkeecil pada Trreap lainnyaa dan melaakukan operrasi penyisipaan X yang lebbih besar dari nilai maksimuum Treap yang satu tettapi lebih kecil k dari niilai minimum m Treap yangg lain dan meemiliki prioriitas maksimum m. Setelah penyisipan, p X akan menjadi daun dan mudah untukk dihilangkan. U Untuk hasil yang y lebih baaik, prioritas yang y lebih keecil dibberikan kepadda simpul yanng sering diakkses dengan cara meemberikan prioritas acak yang y lebih keccil dari prioriitas semula.

REFERENS R SI [1]] Liem, Inggrriani, “Diktat Struktur Data””, Program Sttudi Teknik Infformatika, Seekolah Teknik Elektro dan d Informatika,, Institut Teknollogi Bandung, 2008. 2 [2]] Munir, Rinaaldi, “Diktat K Kuliah IF2091 Struktur Diskrrit”, Program Stuudi Teknik Infoormatika, Sekollah Teknik Elekktro dan Informaatika, Institut Teeknologi Bandu ung, 2008. [3 3] http://taghyrr.wordpress.com m/2009/08/15/taahun-2010kapasitas-haarddisk-akan-tem mbus-3tb/ (Tanggal Akkses : 17 Desem mber 2009; 17.00) [4]] http://en.wikkipedia.org/wikki/Tree_%28data_structure%299 (Tanggal Akkses : 17 Desem mber 2009; 18.24) [5]] http://kuliahh.itb.ac.id/mod/rresource/view.p php?id=5216 (Tanggal Akkses : 17 Desem mber 2009; 20:50) [6]] http://en.wikkipedia.org/wikki/Binary_tree (Tanggal Akkses : 17 Desem mber 2009; 18.26) [7]] http://en.wikkipedia.org/wikki/Binary_search h_tree (Tanggal Akkses : 17 Desem mber 2009; 20.44) [8]] http://www.iinformatika.orgg/~fazat/IF2030 0/IF2030PohonBiner__bagian2.pdf (Tanggal Akkses : 17 Desem mber 2009; 20:52) [9]] http://en.wikkipedia.org/wikki/B-tree (Tanggal Akkses : 18 Desem mber 2009; 11.15) [10 0] http://wiki.answers.com/Q//What_is_a_ballanced_tree_in__da ta_structuress (Tanggal Akkses : 18 Desem mber 2009; 11.16 6) [1 11] http://en.wikkipedia.org/wikki/Selfbalancing_binary_search_trree (Tanggal Akkses : 17 Desem mber 2009; 20.46) [12 2] http://en.wikkipedia.org/wikki/Red-black_treee (Tanggal Akkses : 16 Desem mber 2009; 19.52) [13 3] http://en.wikkipedia.org/wikki/AVL_tree (Tanggal Akkses : 16 Desem mber 2009; 19.52) [14 4] http://en.wikkipedia.org/wikki/AA_tree (Tanggal Akkses : 16 Desem mber 2009; 19.51) [15 5] http://en.wikkipedia.org/wikki/Splay_tree (Tanggal Akkses : 16 Desem mber 2009; 19.51) [16 6] http://en.wikkipedia.org/wikki/Scapegoat_treee (Tanggal Akkses : 16 Desem mber 2009; 19.51) [17 7] http://en.wikkipedia.org/wikki/Treap (Tanggal Akkses : 16 Desem mber 2009; 19.52)


Lampiran 1

2. STRUKTUR DATA 2.1 GRAF Graf G didefinisikan sebagai pasangan himpunan (V, E), yang dalam hal ini : V = himpunan tidak-kosong dari simpul-simpul (vertices atau node) = { , , … , }, dan E = himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul = { , ,…, } atau dapat ditulis singkat notasi G = (V, E) [2].

Jenis-jenis Graf[2] Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis : Graf sederhana (simple graph) Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana. Graf tak-sederhana (unsimple-graph) Graf yang mengandung sisi ganda atau gelang dinamakan graf tak-sederhana. Ada dua macam graf tak-sederhana, yaitu graf ganda (multigraph) dan graf semu (pseudograph). Graf ganda adalah graf yang mengandung sisi ganda saja. Sisi ganda yang menghubungkan sepasang simpul bisa lebih dari dua buah. Graf semu adalah graf yang mengandung gelang (termasuk bila memiliki sisi ganda sekalipun). Sisi pada graf dapat menpunyai orientasi arah. Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas dua jenis : Graf tak-berarah (undirected graph) Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah. Pada graf takberarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. Jadi, ( , ) = ( , ) adalah sisi yang sama. Graf berarah (directed graph atau digraph) Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. Sisi berarah disebut busur (arc). Pada graf berarah, ( , ) dan ( , ) menyatakan dua buah busur yang berbeda, dengan kata lain ( , ) ≠ ( , ). Untuk busur ( , ), simpul dinamakan simpul asal (initial vertex) dan simpul dinamakan simpul terminal (terminal vertex).

Terminologi Dasar[2] Lintasan (Path) Lintasan yang panjangnya n dari simpul awal ke simpul tujuan di dalam graf G ialah barisan berselang-seling simpul-simpul dan sisi-sisi yang berbentuk , , , , ,…, , , sedemikian , = ,…, = = , , sehingga adalah sisi-sisi dari graf G. , Terhubung (Connected) Graf tak-berarah G disebut graf terhubung (connected graph) jika untuk setiap pasang simpul dan di dalam himpunan V terdapat lintasan dari ke (yang juga harus berarti ada lintasan dari ke ). Jika tidak, maka G disebut graf tak-terhubung (disconnected graph). Graf berarah G dikatakan terhubung jika graf tak-berarahnya terhubung (graf tak-berarah dari G diperoleh dengan menghilangkan arahnya).

2.2 POHON (TERMINOLOGI) Pohon bebas adalah graf tak-berarah terhubung yang tidak mengandung sirkuit, dengan sifat sebagai berikut : Misalkan G = (V, E) adalah graf tak-berarah sederhana dan jumlah simpulnya n. Maka, jika G adalah pohon bebas berlaku : Setiap pasang simpul di dalam G terhubung dengan lintasan tunggal, G terhubung dan memiliki m = n – 1 buah jumlah sisi, G tidak mengandung sirkuit, Penambahan satu sisi pada graf akan membuat hanya satu sirkuit, dan Semua sisi G adalah jembatan (jembatan adalah sisi yang bila dihapus menyebabkan graf terpecah menjadi dua komponen)[2]. Pohon berakar (yang selanjutnya disebut hanya pohon) adalah pohon bebas yang sebuah simpulnya diperlakukan sebagai akar dan sisi-sisinya diberi arah sehingga menjadi graf berarah [2]. Pohon sebagai suatu struktur data rekursif adalah himpunan terbatas, tidak kosong, dengan elemen dibedakan sebagai berikut : Sebuah elemen yang dibedakan dari yang lain −> AKAR Elemen yang lain (jika ada) dibagi-bagi menjadi beberapa sub-himpunan yang disjoin dan masing-masing sub-himpunan itu adalah pohon −> SUBPOHON[5]


Lampirann 2

semua siimpul pada su ubpohon kanann > Akar(P)

Gaambar 2.3. Poh hon Biner Teru urut

Gambar 2.1. 2 Pohon

Pohon yang setiap s simpul cabangnya c meempunyai paliing baanyak n buah anak a disebut pohon p n-ary[22].

Poohon Binerr[5] Pohon biner merupakan kaasus khusus pohon p n-ary jika n = 2 dan adalahh himpunan teerbatas yang : munngkin kosong, atau terdiiri atas sebuaah simpul yanng disebut ak kar dan dua buah him mpunan lain yaang disjoint yaang meruupakan pohonn biner, yang disebut sebagai sub pohon kiri dan sub poh hon kanan dari d pohoon biner tersebbut.

Po ohon Binerr Seimbangg[8] Pohon biner seimbang (baalanced binarry tree / B-trree) ad dalah pohon deengan : perbbedaan tinggi antara subpo ohon kiri denggan subppohon kanan m maksimum 1. perbbedaan banyaaknya simpull subpohon kiri k dan subpohon kannan maksimum m 1. Untuk menyeimbangkan tinggi upapohon (subpohoon) kirri dan tinggi upapohon kannan –yaitu beerbeda maksim mal 1– –, tinggi poohon secara keseluruhan harus, secara otomatis, dibuaat seminimal m mungkin. Unttuk memperoleh tin nggi minimum m, setiap araas (level) harrus menganduung jum mlah simpul sebanyak muungkin. Hal ini i dapat dibuat deengan cara meenyebarkan seetengah dari ju umlah simpull di up papohon kiri dan setengaah dari jumlaah simpul yaang merupakan sisaanya di upapohhon kanan[2].

Gambar 2.2.. Pohon Biner

Poohon Binerr Terurut[8]]

Gam mbar 2.4. Pohoon Biner Seimb bang

Pohon biner yang urutan anak-anaknya a penting disebbut poohon biner terrurut atau pohhon biner penncarian (orderred binnary tree / biinary search tree –BST–),, dan memenuuhi siffat : setiaap simpul dallam BST mem mpunyai sebuuah nilaii subppohon kiri dann subpohon kaanan merupakkan BST T jika P adalah sebuuah BST : semua siimpul pada subpohon s kirii < Akar(P)


Lampiran 3

RED-BLACK TREE / SYMMETRIC BINARY B-TREES[12] Penyisipan KASUS 1 : void insert_case1(struct node *n) { if (n->parent == NULL) n->color = BLACK; else insert_case2(n); } KASUS 2 : void insert_case2(struct node *n) { if (n->parent->color == BLACK) return; /* Tree is still valid */ else insert_case3(n); } KASUS 3 :

Gambar 4.2. Kasus 3 void insert_case3(struct node *n) { struct node *u = uncle(n), *g;

} else if ((n == n->parent->left) && (n>parent == g->right)) { rotate_right(n->parent); n = n->right; } insert_case5(n); } KASUS 5 :

Gambar 4.4. Kasus 5 void insert_case5(struct node *n) { struct node *g = grandparent(n); n->parent->color = BLACK; g->color = RED; if ((n == n->parent->left) && (n->parent == g->left)) { rotate_right(g); } else { /* (n == n->parent->right) and (n->parent == g->right) */ rotate_left(g); } }

Penghapusan

if ((u != NULL) && (u->color == RED)) { n->parent->color = BLACK; u->color = BLACK; g = grandparent(n); g->color = RED; insert_case1(g); } else { insert_case4(n); } }

KASUS 4 :

Gambar 4.3. Kasus 4 void insert_case4(struct node *n) { struct node *g = grandparent(n); if ((n == n->parent->right) && (n>parent == g->left)) { rotate_left(n->parent); n = n->left;

Gambar 4.5. Proses Penghapusan pada BST


Lampiran 4

KASUS 1 :

KASUS 4 :

void delete_case1(struct node *n) { if (n->parent != NULL) delete_case2(n); } KASUS 2 :

Gambar 4.8. Kasus 4 void delete_case4(struct node *n) { struct node *s = sibling(n); if ((n->parent->color == RED) && (s->color == BLACK) && (s->left->color == BLACK) && (s->right->color == BLACK)) { s->color = RED; n->parent->color = BLACK; } else delete_case5(n);

Gambar 4.6. Kasus 2 void delete_case2(struct node *n) { struct node *s = sibling(n); if (s->color == RED) { n->parent->color = RED; s->color = BLACK; if (n == n->parent->left) rotate_left(n->parent); else rotate_right(n->parent); } delete_case3(n);

}

KASUS 5 :

}

KASUS 3 :

Gambar 4.9. Kasus 5 void delete_case5(struct node *n) { struct node *s = sibling(n);

Gambar 4.7. Kasus 3 void delete_case3(struct node *n) { struct node *s = sibling(n); if ((n->parent->color == BLACK) && (s->color == BLACK) && (s->left->color == BLACK) && (s->right->color == BLACK)) { s->color = RED; delete_case1(n->parent); } else delete_case4(n);

if (s->color == BLACK) { /* this if statement is trivial, due to Case 2 (even though Case two changed the sibling to a sibling's child, the sibling's child can't be red, since no red parent can have a red child). */

// the following statements just force the red to be on the left of the left of the parent, // or right of the right, so case six will rotate correctly. if ((n == n->parent->left) && (s->right->color == BLACK) && (s->left->color == RED)) { //

}

this last test is trivial too due to cases 2-4. s->color = RED; s->left->color = BLACK; rotate_right(s); } else if ((n == n->parent->right) && (s->left->color == BLACK) &&


Lampiran 5

(s->right->color == RED)) {//

this last test is trivial too due to cases 2-4. s->color = RED; s->right->color = BLACK; rotate_left(s); } } delete_case6(n);

}

KASUS 6 :

Gambar 4.10. Kasus 6 void delete_case6(struct node *n) { struct node *s = sibling(n); s->color = n->parent->color; n->parent->color = BLACK; if (n == n->parent->left) { s->right->color = BLACK; rotate_left(n->parent); } else { s->left->color = BLACK; rotate_right(n->parent); } }


Lampiran 6

AA TREE[14]

Penyisipan

Penghapusan


Lampiran 7


Lampiran 8

SPLAY TREE[15] Splaying Tipe-tipe splay steps : Zig Step :

Gambar 4.20. Penghapusan Langkah 3

Gambar 4.15. Zig Step

Zig-zig Step :

Gambar 4.16. Zig-zig Step

Zig-zag Step :

Gambar 4.17. Zig-zag Step

Penghapusan




Dasar Kerja Pengaplikasian Self-balancing Binary Search Tree untuk Pencarian sebagai Struktur Data yang Lebih Mangkus dan Sangkir

Recommend Documents