Adaptive Binary Search Tree for Integers Sets with Few Holes

Ruixin Wang; Nicolas Barnier

doi:10.37420/j.eeer.2024.002

Elect Elect Eng Res ›› 2024, Vol. 4 ›› Issue (1) :10 -21. DOI: 10.37420/j.eeer.2024.002

Adaptive Binary Search Tree for Integers Sets with Few Holes

Ruixin Wang ¹^,^*
, Nicolas Barnier ²

Author information +

History +

PDF (1880KB)

Abstract

We present the Adaptive Compact Tree (AC-Tree), a data structure similar to a self-balancing binary search tree (BST) that improves storage and operations for sets of integers with few “holes”. AC-Trees can be imple- mented on top of any classic BST (e.g. AVL trees [3]), holding discontiguous intervals at each node to obtain a compact representation only requiring O(k) storage and supporting efficient O(log k) operations, with k the number of intervals. These properties can improve the performances of applications, like Constraint Program- ming (CP) solvers, that incrementally remove values and intervals on domains initially consisting of one large interval. First experiments show that AC-Trees outperform classic self-balancing BSTs in most cases and im- prove CP solvers performances for problems with large domains.

Keywords

self-balancing binary search tree / adaptive data structure / compact representation

Cite this article

Download citation ▾

Ruixin Wang, Nicolas Barnier. Adaptive Binary Search Tree for Integers Sets with Few Holes. Elect Elect Eng Res, 2024, 4(1): 10-21 DOI:10.37420/j.eeer.2024.002

登录浏览全文

4963

注册一个新账户忘记密码

References

Publishing order | Descend order by publishing year | Descend order by cited within

[1]	Barnier N., & Brisset P. (2001). FaCiLe: A Functional Constraint Library. In CICLOPS - Colloqui- um on Implementation of Constraint and Logic Programming Systems, CP’ 01 Workshop, Paphos, Cyprus, December 2001.

[2]	Cormen T. H., Leiserson C. E., Rivest R. L., & Stein C. (2009). Introduction to Algorithms (3rd ed.). The MIT Press. Chapter 14, pp. 339-355.

[3]	Knuth D. E. (1998). The Art of Computer Programming: Sorting and Searching (Vol. 3). Pearson Ed- ucation.

[4]	Leroy X., Doligez D., Frisch A., Garrigue J., Rémy D., & Vouillon J. (2013). The OCaml System (Release 4.01): Documentation and User’s Manual. Institut National de Recherche en Informatique et en Automatique.

[5]	Pfaff B. (2004). Performance Analysis of BSTs in System Software. ACM SIGMETRICS Perfor- mance Evaluation Review, 32(1), 410-411.

[6]	Pothitos N. (2013). Naxos Solver.

[7]	Pothitos N., & Stamatopoulos P. (2010). Flexible Management of Large-Scale Integer Domains in CSPs. In Artificial Intelligence: Theories, Models and Applications: 6th Hellenic Conference on AI, SETN 2010, Athens, Greece, pp. 405-410. Springer.

[8]	Schulte C., & Carlsson M. (2006). Finite Domain Constraint Programming Systems. In Handbook of Constraint Programming, Chapter 14, pp. 495-526. Elsevier.