In-place balancing of Binary Search Tree stored in array

Question

Lets assume I have a BST that is not balanced. The BST is stored in array, where root is at index 0 and left and right children of node on index k are on indices 2k and 2k + 1 respectively. For example a tree:

      5                            4
     /                            / \
    3        --balancing-->      2   5
   /\                           / \
  2  4                         1   3
 /
1

will be stored in array [5, 3, nil, 2, 4, nil, nil, 1, nil, ...] and I would like to balance it so that max height of result search tree is minimal(=there are not more levels than needed to store the data).
It could be for example a tree where there are no gaps between values in the array and all nil values are "pushed" to the back (note: this tree definition is actually more restrictive than my goal in previous paragraph). For example above [4, 2, 5, 1, 3, nil, ...].
Is there such algorithm? If not, is there similar algorithm balancing the tree at least "good".

Additional information:
- the algorithm need to be in-place, only O(1) extra memory is allowed
- there is an algorithm mentioned in this question, however it relies on swapping pointers (the array would need to be 2^n big)
- there was a very similar question, sadly the accepted answer is just general talk about trees. (I do not have the meta-data for AVL balanced tree, do I? If I am mistaken, please prove me wrong)
- acceptable answer can also be that there is no such algorithm, if it is that case, please include some references/proof or logical assumption

IMO O(1) space rules out recursion of O(log n) levels (my guess being balancing does need space proportional log n, at least). In general, rebalancing will take moving on the order of n nodes. Not having any balancing information for each node sure limits the choice of algorithms, if not notions of balance. "Self-balanced trees" I seem to remember rely on imbalances introduced locally and resolved, if not locally, then on a path between root and (newly)imbalanced node. What, searches aside, is the tree used for? Are "appends" to be supported, insertions in arbitrary places, deletions? — greybeard, Oct 24 '14 at 22:38
@greybeard Ofcourse, stack allocations for recursion are allowed (Day-Stout-Warren would be log n otherwise). To be precise, I am trying to find alternative Scapegoat tree rebalance method. Thus insertions, deletions and other operations are allowed on whole tree while the subtree(the target here) to be rebalanced can be viewed as completely static. — wondra, Oct 25 '14 at 11:42

In-place balancing of Binary Search Tree stored in array

0 Answers0