In a relaxed radix balanced (RRB) tree, how is the height determined in practice?

89 views Asked by At

In a traditional radix-balanced tree, the height of the tree can be determined quickly by counting the leading zeros of the number of elements of the tree, and indexes to children can be determined by taking successive chunks of bits from the element index.

However, consider a radix-balanced tree which is almost full. Now make that tree into a relaxed radix balanced tree, so that the tree is no longer "densely packed". This would require that the tree have additional height to accommodate all the elements which could only just barely have been contained by a fully-packed radix tree.

This means that the height of the tree is no longer given by clz(size), and the index into the first child is no longer taken from the first k nonzero bits of the element index (with k the log2 of the tree's branching factor). Instead we'd need start with a more significant chunk of bits in the index (which would be all be zero), and begin a linear search for the element in subtree number 0, "spilling over" into subtree number 1 if the first subtree didn't contain it.

Thus whether the tree "spills over" to a greater height depends on the size of the tree and the density of its packing.

In practice, how is this condition detected? (Obviously performance is important because these structures are designed for inner-loop usage!)

0

There are 0 answers