Representing dynamic binary trees succinctly
J. Ian Munro, Venkatesh Raman, Adam J. Storm · Symposium on Discrete Algorithms · 2001
We introduce a new updatable representation of binary trees. The structure requires the information theoretic minimum 2n + O(n) bits and supports basic navigational operations in constant time and subtree size in O(lg n). In contrast to the linear update costs of previously proposed succinct representations, our representation supports updates in O(lg2n) amortized time.