Red-Black Tree

Melanjutkan kelompok struktur data hirarkis, kuliah kali ini membahas varian lain binary search tree yang dikenal sebagai Red-Black Tree. Struktur ini  dibahas sebagai varian BST disamping AVL Tree yang memungkinkan rebalancing guna mencapai performance O(log n). Selain itu struktur ini dapat menjadi cara untuk mengimplementasikan 2-3 Tree (2-3 Tree adalah varian dari keluarga (a,b)-tree dimana B-Tree berada di dalamnya sebagai salah satu varian). Red-Black Tree juga sering digunakan dalam mengimplementasikan sejumlah abstraksi yang lebih tinggi lainnya.

Red-Black Tree adalah suatu binary search tree dengan tambahan 4 property: (1) node berwarna merah atau hitam; (2) root berwarna hitam; (3) node merah tidak boleh memiliki anak node merah ; (4) dalam lntasan dari suatu internal node ke semua leaf node di bawahnya, node hitam sama jumlahnya. Dengan property ini suatu Red-Black Tree dengan jumlah node n menjamin jumlah tinggi tree minimum log(n+1) dan maksimum 2.log(n+1).

Agar operasi penyisipan dapat dilakukan secara O(log n), algoritma penyisipan data pada awalnya dilakukan sebagaimana pada BST yaitu O(log n) dan node baru tersebut berwarna merah, dilanjutkan dengan operasi untuk membuatnya kembali menjadi Red-Black Tree apabila dari penyisipan terjadi pelanggaran pada satu atau beberapa dari keempat sifat di atas. Materi kuliah ini membahas kasus-kasus yang terjadi dan algoritma penanganan dari setiap kasus. Untuk penghapusan, awalnya terjadi hal yang sama dengan apa yang dilakukan pada BST.  Selanjutnya, berdasarkan kasus-kasus yang terjadi dilakukan algoritma untuk mengembalikan menjadi Red-Black Tree kembali jika terjadi pelanggaran terhadap sifat-sifat tsb. Algoritma-algoritma tersebut memiliki performance worst-case O(log n) sehingga secara keseluruhan tetap O(log n).

Kelemahan Red-Black Tree dibandingkan AVL Tree adalah tinggi tree yang dihasilkan worst case 2 log (n+1) sementara AVL Tree 1.44 log(n+2), tetapi dengan adanya lebih banyak kasus-kasus yang bisa terjadi dengan penanganan yang lebih sederhana memungkinan Red-Black Tree memiliki real performance yang lebih baik.

Slide kuliah dapat didownload di sini.

Binary Heap dan Priority Queue

Kembali ke struktur data hirarkis, terdapat satu struktur binary tree yang bernama binary heap. Suatu binary heap adalah binary tree yang didalamnya tersimpan data dengan cara pengurutan tertentu: dalam binary heap dengan kaidah “minheap” data pada setiap parent dalam tree harus tidak boleh lebih besar dari data pada anak-anaknya. Dengan demikian root dari tree berisi bilangan terkecil dari semua bilangan dalam tree. Dalam binary heap dengan kaidah “maxheap”, parent tidak boleh lebih kecil dari anak-anaknya sehingga root berisi bilangan terbesar dari semua bilangan dalam tree.

Semantara itu, dalam kuliah mengenai struktur hirarkis dibahas definisi complete binary tree. Suatu complete binary tree adalah suatu binary tree yang memiliki bentuk khusus sehingga menjadi satu-satunya binary tree yang dapat direpresentasikan hanya dengan array tanpa kehilangan informasi strukturnya (siapa ayah, siapa anak-akannya, dapat diketahui melalui fungsi antara indeks di dalam array tsb).

Konsep binary heap ini dikombinasikan dengan konsep complete binary tree tersebut menghasilkan suatu struktur priority queue yang memiliki performance O(log n). Tanpa itu, suatu priority queue memerlukan operasi O(n), ie. , dengan sorted array memerlukan enqueue O(n) dequeue O(1) atau unsorted array memerlukan enqueue O(1) dan dequeue O(n). Yang menarik, perbaikan performance dari O(n) menjadi O(log n) hanya pada konsep abstraksinya saja semetara representasinya tetap sama-sama dengan array.

Operasi enqueue (menginsert data ke dalam queue) pada struktur ini bisa mencapai O(log n) dengan suatu proses PercolateUp dan operasi dequeue (meremove data terkecil untuk minheap / data terbesar untuk maxheap) dengan proses PercolateDown. Kedua algoritma ini beriterasi secara worse case antara root dengan leaf tanpa mengganggu node-node lainnya.

Manfaat selain sebagai suatu priority queue, struktur ini mengilhami algoritma sorting yang bernama heapsort yang memiliki performance O(n log n) seanding dengan quicksort dan mergesort. Heapsort mengurutkan data mirip seperti selection-sort namun jika selection-sort melakukan pencarian data minimum secara sikuensial (O(n)) pada data , heapsort hanya melakukan dequeue secara O(log n). Di awal  priority queue yang semula berisi semua data yang tersusun membentuk heap dengan suatu proses heapify yang bersifat O(n log n).

Selain itu, terdapat sejumlah manfaat lainnya yaitu dalam struktur pendukung proses external data sorting.

Slide materi kuliah ini dapat didownload di sini.

Hash Table

Hingga saat ini sudah sekian struktur yang telah dipelajari untuk bisa menyimpan data dan mencari atau menghapusnya kembali, mulai dari struktur tabel (biasa baik unsorted array maupun sorted array), struktur linear linked list, struktur hirarkis (BST, AVL, BTree), hingga graph.

Semua struktur itu memiliki performance yang terkait dengan jumlah data N. Struktur array unsorted memerlukan O(1) untuk menyimpan data tapi dalam pencarian kembali data dan menghapus data memerlukan O(n). Pada struktur sorted array sebaliknya, menyimpan dan menghapus dengan O(n), tetapi pencarian data memerlukan O(log n) (yaitu menggunakan algoritma Binary Search). Sementara, struktur hirarkis memungkinan semua proses dapat dilakukan secara O(log n).

Dalam kuliah ini dibahas struktur yang memungkinkan secara teoritis semua operasi itu dilakukan secara O(1) atau konstan tidak bergantung jumlah data yang bernama hash table. Bagaimana itu bisa terjadi? Hash table menggunakan suatu fungsi (disebut fungsi hash) untuk menentukan dimana penempatan data dalam tabel berdasarkan komputasi atas key data tersebut. Komputasi fungsi hanya bergantung pada harga key itu saja dan idealnya fungsi tsb harus memetakan setiap kemungkinan key ke dalam bilangan nomor entry pada tabel untuk menaruh data. Tabel sendiri merupakan array biasa. Apakah itu selalu bisa terjadi? Tentu saja sepanjang fungsi hash memenuhi keunikan penempatan itu.

Kenyataannya sulit (atau bahkan tidak mungkin) mendapatkan fungsi hash ideal tersebut terutama jika key data unpredictable. Karena itu maka pembahasan materi kuliah ini berpokok pada metoda-metoda untuk menangani situasi jika penempatan data tidak dapat dilakukan secara unik yaitu terjadi tabrakan di suatu posisi. Cara penangan tabrakan atau collison ini dibedakan antara open-hashing dan close-hashing. Open-hashing menangani collision dengan memperluas entry tabel tersebut dengan menaruh data kedua, ketiga, dst (yang collision di posisi tsb.) ke dalam “bucket”. Biasanya bucket diimplementasikan sebagai linked-list untuk memungkinkan kedinamisan ukuran bucket. Close-hashing menangani collision dengan mencarikan posisi alternatif untuk data yang collision itu masih di tabel yang sama (tidak ke luar tabel). Ada tiga kelompok cara untuk mencarikan posisi alternatif, atau yang disebut “probing” ini: linear probing, quaratic probing, dan double hashing. Semua cara penanganan collision itu haruslah bisa menjaga agar operasi pada hash table tetap konstan atau “mendekati konstan”.

Slide materi kuliah ini dapat diperoleh di sini.

Graph

Graph adalah istilah untuk suatu model stuktur data yang bersifat interkoneksi n-ke-n. Beberapa di antara kita mengadaptasinya ke bahasa Indonesia menggunakan istilah geraf atau graf. Dalam matematika diskret graph merupakan pokok bahasan penting yang membahas analisis & teori serta algoritma terkait  dengannya. Dalam kuliah Struktur Data, hal-hal tersebut diperdalam dengan bahasan bagaimana model itu diterjemahkan menjadi struktur data yang dapat diimplementasikan. Pada dasarnya ada tiga cara implementasi graph: adjacent matrix, edge list, dan adjacent vertex list. Masing-masing memiliki keunggulannya sendiri terkait dengan query yang dilakukan pada cara-cara tsb.

Bagian kedua adalah pembahasan ulang algoritma-algoritma graph dengan pembahasan dikaitkan dengan analisisnya terkait ketiga struktur di atas. Pertama yang dibahas adalah algoritma BFS (Breadth First Search) yang dapat digunakan untuk pencarian shortest path pada unweighted graph. Kedua adalah algoritma Dijkstra untuk pencarian single-source shortest paths pada weighted graph. Algoritma ketiga adalah pencarian minimum spanning tree (MST) dengan algoritma Kruskal dan algoritma Prim pada wieghted graph. Ke empat adalah melakukan topological sorting pada suatu directed acyclic graph.

Secara umum, kondisi graph sangat menentukan pemilihan cara implementasinya. Untuk dense graph (atau graph dengan interkoneksi yang tinggi antara verteks), adjacent matrix memberikan performance yang baik sementara kebalikannya sparse graph (graph dengan interkoneksi yang rendah) akan lebih efisien jika menggunakan adjacent vertex list. Edge list lebih efisien untuk algoritma yang mentraverse seluruh edge seperti Algoritma Kruskal pada masalah MST.

Slide materi ini dapat didownload di sini.

B+Tree

Masih dalam kelompok struktur data hirarkis, kuliah hari ini membahas B+Tree. Struktur data ini semula adalah varian dari struktur data (a,b)-Tree, namun dalam perkembangannya struktur ini digunakan secara spesifik sebagai struktur data eksternal (i.e., indexed file) dan kemudian dalam DBMS relasional untuk mengorganisasikan index key dari tabel basis data.

Sebagai struktur data eksternal B+Tree biasanya berupa n-ary tree dengan n bilangan yang cukup besar. Dengan demikian untuk n=100, data dalam jumlah jutaan dapat diorganisasikan dalam B+Tree yang memiliki tinggi = 3. Dengan bentuknya yang landai demikian memungkinkan data diakses secara cepat dengan hanya melalui pembacaan 3 buah node B+Tree sebelum membaca blok datanya . 

Dalam kuliah telah dibahas mekanisme yang terjadi saat masuknya key data ke dalam struktur B+Tree serta saat suatu key data dihapuskan dari struktur tsb. Saat masuknya data baru ke dalam tabel, key data dan referensi data dalam tabel disimpan dalam node leaf struktur B+Tree. Terdapat kapasitas maksimum setiap node sehingga saat key baru dimasukan sementara node sudah mencapai kapasitas maksimum, akan terjadi mekanisme “split”. Demikian pula, saat terjadi penghapusan data yang berakibat key pada node berkurang, apabila jumlah key melalui batas minimal kapasitas, maka akan terjadi mekanisme “merge” atau kalau tidak “redistribusi” isi node. Mekanisme-mekanisme itu memaintain struktur B+Tree tetap memenuhi kaidah sebagai suatu B+Tree agar setiap operasi dapat dilakukan secara O(log n) dengan basis logaritma bilangan yang besar.

Slide materi ini dapat di download di sini.

AVL Tree (Balanced Binary Search Tree)

Worst Case dari BST terjadi saat bentuk tree yang tidak balance, misalnya jika sederetan data terurut diinsert ke dalamnya akan membentuk cabang yang berbentuk rantai panjang (tanpa pencabangan lain). Situasi ini mengakibatkan operasi searching pada BST menjadi O(n), tidak sebagaimana yang diharapkan yaitu O(log n). Adelson-Velskii dan Landis mempelajari mekanisme tambahan pada operasi-operasi insert/delete pada BST sehingga BST selalu kembali ke dalam situasi “balanced”. Untuk memungkinkan mekanisme tsb bekerja secara O(log n) maka didefinisikan AVL tree sebagai BST dengan tinggi subtree kiri dan subtree kanan dari setiap node di dalamnya berbeda tidak boleh lebih dari 1 (jadi, jika HL dan HR adalah masing-masing tinggi subtree kiri dan kanan, maka HL – HR| ≤ 1).

Mekanisme rebalancing pada operasi insert dilakukan dengan mencari subtree terkecil yang mengalami “kerusakan” sesaat insert dilakukan. Di posisi itu dilakukan “operasi rotasi” yang dilakukan secara O(1). Ada empat jenis rotasi Single Right Rotation (SRR), Single Left Rotation (SLR), Double Right Rotation (DRR), dan Double Left (Rotation) sesuai dengan kondisi “kerusakan yang terjadi. Setelah rotasi yang dilakukan, subtree tersebut kembali menjadi AVL-tree dengan tinggi yang sama dengan tinggi sebelum insert. Dengan demikian, rotasi hanya dilakukan satu kali saja. Karena menentuan subtree terkecil mana yang terjadi kerusakan adalah operasi backtrack dari leaf ke arah root, maka mekanisme rebalancing ini menjadi operasi O(log n).  Mekanisme rebalancing pada operasi remove mirip dengan yang dilakukan pada insert kecuali operasi rotasi bisa terjadi beberapa kali karena setelah suatu rotasi di suatu subtree dilakukan, karena tinggi subtree kemudian menjadi berkurang, maka subtree yang lebih besar di atasnya harus diperiksa pula karena kemungkinan juga tidak balanced. Namun, operasi keseluruhan tetap adalah O(log n).

Animasi dari AVL Tree dapat dilihat disini dan slide materi kuliah disini.

Binary Search Tree (BST)

Sebagaimana yang sudah kita bahas, pengorganisasian data dalam array memungkinkan pencarian O(log n) dengan menggunakan algoritma binary search, namun dengan syarat data terurut. Untuk menjaga data selalu terurut saat terjadi perubahan data: insert, delete, dan update, diperlukan operasi penggeseran O(n). Masalah lainnya adalah keterbatasan ukuran array.

Binary tree dapat digunakan untuk mengorganisasikan data dengan pencarian data O(log n) tanpa adanya keterbatasan seperti pada array dan namun operasi perubahan data dapat dilakukan secara O(log n) juga. Binary tree pertama yang memungkinkan hal ini adalah Binary Search Tree ( BST). BST adalah binary tree yang mana data di dalamnya tersusun sedemikian rupa sehingga pada setiap subtree di dalamnya berlaku setiap data di subtree kiri < data root subtree < setiap data di subtree kanan.

Dengan asumsi tree yang terbentuk adalah “segitiga” membesar ke bawah, pencarian data adalah menelusuri ke cabang data itu berada sehingga berjalan secara O(log n). Jika data masuk ke dalam BST secara acak, operasi penyisipan ke dalam BST tersebut dilakukan dengan penelusuran dari root hingga leaf tempat seharusnya data tsb berada sehingga terjadi secara O(log n). Operasi penghapusan dilakukan dengan pencarian data di dalam BST lalu dilakukan penghapusan menggunakan langkah-langkah yang sesuai dengan kasus dari 3 kasus yang bisa terjadi. Operasi penghapusan dapat dilakukan secara O(log n).

Slide kuliah ini dapat didownload di sini.

Struktur Data Hirarkis (Tree) (Bag. 2)

Materi pembahasan kuliah hari ini masih meneruskan bagian akhir yang belum tuntas dibahas pada kuliah yang lalu yang berisikan topik-topik algoritma non-rekursif untuk tree traversal, level-order traversal, representasi array pada complete binary tree.
Apabila dalam kuliah sebelumnya tree traversal dilakukan dengan algoritma rekursif, dalam sesi kuliah ini dilakukan dengan algoritma non-rekursif dengan bantuan stack. Level order traversal adalah traversal lain yang dapat dilakukan dengan bantuan queue.
Binary Tree secara normal direpresentasikan dengan struktur dinamis (selerti linked-list namun dua pointer ke subtree kiri dan ke subtree kanan) namun kusus untuk complete binary tree direpresentasikan dengan array tanpa kehilangan informasi strukturalnya. Dalam implementasi array ini hubungan struktural antara data masih terekam sebagai hubungan aritmatis bolak-balik antara indeks parent dengan indeks children dalam array tsb.

Struktur Data Hirarkis (Tree)

Materi Abstract Data Type (ADT) berikutnya adalah struktur data hirarkis atau dalam istilah lebih teknisnya struktur data pohon/tree. Struktur data ini diperlukan untuk bisa menyimpan kumpulan data yang mana setiap elemen data memiliki hubungan hirarkis satu sama lainnya misalnya struktur organisasi, taksonomi makhluk hidup, pohon silsilah keluarga, struktur isi direktori dalam sistem file komputer, dll. Secara umum dalam struktur data tree setiap elemen data (selanjutnya disebut node) memiliki link/hubungan/pointer ke sejumlah node lainnya tanpa terjadinya siklus (Siklus adalah situasi yang terjadi jika hubungan berantai dari suatu node pada suatu ketika kembali lagi ke node itu sendiri. Untuk kasus adanya siklus akan dibahas dalam struktur data graph yang akan dibahas di bagian akhir semester).

Materi struktur data tree dalam beberapa minggu kuliah ini akan berfokus pada struktur data tree khusus yaitu binary tree, yaitu pencabangan pada setiap node maksimum hanya boleh ada dua cabang. Selanjutnya setiap cabang dibedakan antara cabang kiri dan cabang kanan.

Slide kuliah ini sudah dapat didownload disini.

Sebagaimana yang telah dibahas di kelas yang lalu (ada di slide sebelumnya), stack dapat digunakan untuk pemeriksaan pasangan tanda kurung. Tanpa stack, algoritma nonrekursif membutuhkan kompleksitas O(n2). Algoritma rekursif bisa mencapai O(n) namun dengan penggunaan stack internal.

Dalam kuliah ini satu contoh lagi dibahas mengenai manfaat stack. Problemnya adalah melakukan komputasi berdasar ekspresi aritmatika yang diberikan. Problem ini dalam buku teks dibahas dalam konteks “Kalkulator Sederhana”. Namun, solusi yang dibahas, secara umum ditemukan juga dalam sebagian implementasi compiler/interpreter.

Algoritma komputasi menggunakan stack yang mampu menghasilkan kompleksitas O(n), dengan n jumlah token dalam ekspresi. Algoritma terdiri atas dua tahap: (1) konversi infiks menjadi posfiks, dan (2) komputasi ekspresi posfiks. 

Slide materi kuliah dapat didownload disini (versi ini sudah hasil revisi akibat adanya sejumlah kesalahan dan ditambah dua halaman slide untuk menambah kejelasannya).

Categories

Calendar

August 2017
M T W T F S S
« Dec    
 123456
78910111213
14151617181920
21222324252627
28293031