Hierarchikus bináris keresőfa
Hierarchical Binary Search Tree
Keywords:
binary search tree, multilevel recursion, n-tuples, HBST, /, bináris keresőfa, többszintű rekurzió, rendezett n-es, HBKFAbstract
The memory-efficient storage and lexicographical sorting of n-tuples (multi-dimensional data records) pose a significant challenge in modern data processing. This paper introduces a novel hybrid data structure, the Hierarchical Binary Search Tree (HBST), which combines the advantages of prefix trees and binary trees to eliminate the redundancy of repetitive data prefixes. Due to its structural design, the HBST radically optimizes space complexity in narrow value ranges while guaranteeing fast, logarithmic-time search and insertion.
Kivonat
A nagyméretű, többdimenziós adatrekordok (rendezett n-esek) memóriahatékony tárolása és lexikografikus rendezése komoly kihívás a modern adatfeldolgozásban. Jelen tanulmány egy új hibrid adatszerkezetet, a hierarchikus bináris keresőfát (HBKF) mutatja be, amely a prefix-fák és a bináris fák előnyeit ötvözve küszöböli ki az ismétlődő adatelőtagok okozta redundanciát. A struktúra felépítéséből adódóan a HBKF szűk értéktartományok esetén radikálisan optimalizálja a tárkomplexitást, miközben mindvégig garantálja a gyors, logaritmikus idejű keresést és beszúrást.
References
[1] Sedgewick R., Wayne K. Algorithms, (4. kiadás) Addison-Wesley Professional, 2011.
[2] Charras C., Lecroq T. Handbook of Exact String Matching Algorithms, College Publications, 2004.
[3] Fredkin E. Trie memory, Communications of the ACM, 1960, 3(9), 490-499.
[4] Bentley J. L. Multidimensional binary search trees used for associative searching, Communications of the ACM, 1960, 18(9), 509-517.
[5] Bentley J., Sedgewick R. Fast algorithms for sorting and searching strings, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, ACM, 1997, 360-369.
[6] Varga I.: Hierarchical Binary Search Tree. GitHub repository, https://github.com/VargaImre79/HBST (Utolsó letöltés: 2026.08.26).
[7] Dwork C., Roth A., The Algorithmic Foundations of Differential Privacy. Foundations and Trends in Theoretical Computer Science, 2014, 9 (3-4), 211-487.
[8] Khanaa V., Thooyamani K.P., Protecting Privacy When Disclosing Information: K Anonymity and its Enforcement through Suppression. International Journal of Computing Algorithm, 2012, 1 (1), 19-22.
