Treaps - A Balanced and Efficient Data Structure
DOI:
https://doi.org/10.32628/CSEIT241015Keywords:
Treap, Binary Search Tree, Heap, Maxheap, Data StructureAbstract
Treaps, blending Binary Search Trees (BST) and Heaps, present a distinctive data structure combining search accuracy with randomized prioritization. This paper explores Treap fundamentals, operations, and implementation details, emphasizing their adeptness in maintaining equilibrium during dynamic operations. The Treap structure, succinctly outlined, features nodes with keys, priorities, and left/right children. Operations like insertion, deletion, and search are demystified, showcasing Treaps' inherent balancing mechanisms. Treap split and join operations, crucial for partitioning and merging based on keys, are explored alongside real-world use cases, underscoring Treaps' versatility. Backed by Java implementation and the TreapAnalyzer class, this research provides concise insights into Treap efficiency. Experimental results, graphically depicted, affirm Treaps' prowess, making them a compelling choice for developers seeking balance and efficiency in computational tasks.
References
- https://www.cs.cmu.edu/~scandal/papers/treaps-spaa98.pdf
- M. R. Brown and R. E. Tarjan. A fast merging algorithm. Journal of the Association for Computing Machinery, 26(2):211–226, Apr. 1979
- S. Carlsson, C. Levcopoulos, and O. Petersson. Sublinear merging and natural merge sort. In Proceedings of the International Symposium on Algorithms SIGAL’90, pages 251–260, Tokyo, Japan, Aug. 1990.
- R. Seidel and C. R. Aragon. Randomized search trees. Algorithmica, 16:464–497, 1996.
- F. K. Hwang and S. Lin. A simple algorithm for merging two disjoint linearly ordered sets. SIAM Journal of Computing, 1:31–39, Mar. 1972.
- https://en.wikipedia.org/wiki/Treap
- https://www.geeksforgeeks.org/treap-a-randomized-binary-search-tree/
- https://cp-algorithms.com/data_structures/treap.html
Downloads
Published
Issue
Section
License
Copyright (c) IJSRCSEIT

This work is licensed under a Creative Commons Attribution 4.0 International License.