Wednesday, May 4, 2011

Prepare for a move - algorithm

Most of the algorithm is like solving a puzzle, it is interesting, but it lacks of math. I came across an algorithm problem, which is interesting to me, at least more math involved.

Given a complete binary search tree in form of array. Write a sort function to sort the given array in O(n)time complexity and constant memory.

________100
_____50_______150
___25___75__125___200

then array is {100 50 150 25 75 125 200}

the trick is the tree is a full binary tree.

if the node is left most node: its index = (0 + parent node's index) / 2
if the node is right most node: its index = (n + parent node's index) / 2
other nodes: its index = (parent's index + grandparent's index) / 2

with this formula, it is easy to pin point the location.

No comments: