Implementing Binary Search Trees in GP 2 (Extended Abstract)
Abstract
We present an approach to implement binary search trees in the rule-based graph programming language GP 2. Our implementation uses GP 2's rooted graph transformation rules to be fast and supports insertion, deletion and query operations. We argue that the worst-case runtime for each of the operations is O(n) for a tree with n nodes. In addition, we expect that, on average, the operations run in time O(log(n)). Hence the implementation would match the time complexity of binary search trees implementations in imperative languages.
Fields of Study & Subjects
Graph Theory and Algorithms
Model-Driven Software Engineering Techniques
Semantic Web and Ontologies
Publication details
- Journal / source
- Electronic Proceedings in Theoretical Computer Science
- Volume
- 440
- Pages
- 6–12
- Publication date
- 6 January 2026
- Language
- EN