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