# Strongly weight-balanced deterministic skip lists

In section 2.2 of Cache-Oblivious B-Trees, Strongly Weight-Balanced Search Trees are defined as:

For some constant $d$, every node $v$ at height $h$ has $\Theta(d^h)$ descendants.

They claim:

Search trees that satisfy Properties 1 and 2 include weight-balanced B-trees, deterministic skip lists, and skip lists in the expected sense.

Other papers also claim that deterministic skip lists are strongly weight-balanced, including Concurrent Cache-Oblivious B-Trees and Cache-Oblivious Streaming B-trees.

I can't figure out why deterministic skip lists have this property. The original paper on deterministic skip-lists notes that

As we see from Fig. 1, there exists a one-to-one correspondence between 1-2 skip lists and 2-3 trees.

It seems to me, however, that 2-3 trees are not strongly weight-balanced, since a node at height $h$ can have anywhere from $2^h$ to $3^h$ descendants.

• That sounds like a legitimate issue. The mentioned papers all share a coauthor, so it could be a consistent oversight. Have you emailed the authors? Oct 3 '10 at 1:54
• how critical to the proofs is the tight range for the numnber of descendants ? Oct 3 '10 at 8:23
• @Per - I have now emailed the shared coauthor. @Suresh - I am not sure, but the authors choose to base their structures on weight-balanced B-trees, so my question is not about the validity of the main results. Oct 3 '10 at 12:49
• Please be careful not to subject an author to a public embarrassment inadvertently. cf. meta.cstheory.stackexchange.com/questions/214/… Oct 3 '10 at 16:58
• @Tsuyoshi: Since the importance of this possible error is very minor (it does not, as far as I can tell, affect the claimed results of the papers cited in any way), and since most of the "errors" I find in published work are just errors in my own understanding, I thought it would be better to ask here first. Even if this is an error, it is so minor that I suspect it would not lead to any author embarrassment. Oct 3 '10 at 19:07