Order Statistic Tree: Struktur Data Domain Partition Search Tree Termodifikasi

Zaidurrohman, Prof. Dr. Suprapto, M.I.Kom

2026 | Skripsi | ILMU KOMPUTER

Pada tahun 2023, diusulkan sebuah struktur data bernama Domain Partition Search Tree, yang disingkat DPS Tree. DPS Tree merupakan salah satu bentuk binary search tree. Menggunakan skema partisi domain, DPS Tree dijamin selalu memiliki kedalaman logaritmik tanpa memerlukan skema balancing sebagaimana bentuk binary search tree lain. Dari segi pengimplementasian kode program pada penelitian terdahulu, DPS Tree tidak dapat digunakan untuk menyimpan nilai duplikat dan tidak dapat dikenai operasi rank dan select.

Dalam penelitian ini dikembangkan struktur data Order Statistic Tree, yaitu sebuah struktur data hasil modifikasi terhadap struktur data DPS Tree agar dapat menyimpan nilai duplikat dan dapat dikenai operasi rank dan select. Modifikasi utamanya adalah menambahkan dua atribut baru pada node, yaitu atribut count dan size. Atribut count pada suatu node menyimpan banyaknya nilai duplikat yang disimpan node tersebut, sedangkan atribut size pada suatu node menyimpan banyaknya data yang tersimpan pada subtree yang berakar di node tersebut.

Dengan modifikasi yang dilakukan, Order Statistic Tree dapat digunakan untuk menyimpan nilai duplikat dan dapat dikenai operasi rank dan select. Order Statistic Tree memiliki kompleksitas memori O(n) pada kasus terburuk, \Omega(1) pada kasus terbaik, dan \Theta(min(n, |R|)) pada kasus rata-rata, sedangkan kompleksitas waktunya O(min(n, log |R|)) pada kasus terburuk, \Omega(1) pada kasus terbaik, dan \Theta(min(log n, log |R|)) pada kasus rata-rata, di mana |R| adalah ukuran domain pada root.

In 2023, Nurrokhman proposed a data structure called the Domain Partition Search Tree, abbreviated as DPS Tree. The DPS Tree is a form of binary search tree that utilizes a domain partitioning scheme, ensuring logarithmic depth without the need for balancing mechanisms found in other binary search tree variants. Based on the implementation in previous research, the DPS Tree was unable to store duplicate values or perform rank and select operations. 

This research develops the Order Statistic Tree, a modified version of the DPS Tree capable of storing duplicate values and supporting rank and select operations. The primary modification involves adding two new attributes to each node: count and size. The count attribute stores the number of duplicate values held by that specific node, while the size attribute represents the total number of data points stored within the subtree rooted at that node. 

As a result of these modifications, the Order Statistic Tree successfully handles duplicates and executes rank and select operations. The data structure maintains a memory complexity of O(n) in the worst case, \Omega(1) in the best case, and \Theta(min(n, |R|)) on average, where |R| denotes the domain size at the root. Its time complexity is O(min(n, log |R|)) in the worst case, \Omega(1) in the best case, and \Theta(min(log n, log |R|)) on average.

Kata Kunci : struktur data, kompleksitas, pohon biner, order statistic