Self-Organizing Data Structures

Abstract. We survey results on self-organizing data structures for the search problem and concentrate on two very popular structures: the un-sorted linear list, and the binary search tree. For the problem of main-taining unsorted lists, also known as the list update problem, we present results on the competitiveness achieved by deterministic and random-ized on-line algorithms. For binary search trees, we present results for both on-line and o-line algorithms. Self-organizing data structures canbe used to build very eective data compression schemes. We summarize theoretical and experimental results.