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:
Post a Comment