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