FIX to Fully-Functional Succinct Trees

Level: Serious

The complexities we claim for dynamic trees are not all correct. We cannot obtain O(log n / loglog n) time for all those operations. This stems from errors in Section 7, which is only sketched in the paper but whose results we used for Table 1. In particular, the use of n(i,j) to solve degree, child, and child_rank is flawed. Lemma 7.2 is also wrong, yet we can recover many of the O(log n / loglog n) claimed complexities by resorting to [6] and mixing it with our structure.

A correct and complete description now appears in the journal version of the paper, accepted in 2012 to appear in ACM TALG. There we also describe, for example, how to deamortize splits due to insertions and deletions.