Adaptive Binary Search Tree for Integers Sets with Few Holes

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 implemented 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 Programming (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 improve CP solvers performances for problems with large domains.