Posts tagged with “math”

Fast positions in left-complete, array based binary trees

A recent question I came across when working with static left complete binary search trees.

  • How to quickly calculate the position of the k'th element in the sorted order?

Suppose our search tree is as follows

nodes = [ 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 ]

              8
      4               12
  2       6       10      14
1   3   5   7   9   11  13  15

Then the position of the 3'rd element is 9, position of 7th element is 11.

Now lets modify the question a bit further.

Calculate the position of the k'th element in the sorted order, for the subtree at position p and height h 

k_child(p, h, k)

So for the subtree at position 3 (the element 12), and height 2 (a tree with a single node has height 0), the 3'rd element is at position 13 ( the element 11).
For p=3, h=1, k=3, the 3'rd element is at position 7.

Generally this is done using a while loop and the fact that the left and right child positions can be calculated by 2*p, 2*p+1 and takes O(b^2), where b is the number of bits in the numbers we are working with (typically 32 bit integers)

We can do a lot better, in O(b) as shown with the following C++ code snippet

#define k_child(p, h, k)        (((p<<h)|(k>>1))/(k&(~(k-1))))

Note: The division will be optimized to bit shifts as we are dividing by a power of 2.

It's a cute little puzzle which takes a bit of time to figure out but hopefully putting this out there will help others too :D