avl tree delete question

[nik]

Hi,

when I delete a node in the tree should I call the rebalance function for the node that takes the place of the deleted node or for the parent of the deleted node?

thanks in advance

[iMalc]

Hi,

when I delete a node in the tree should I call the rebalance function for the node that takes the place of the deleted node or for the parent of the deleted node?

thanks in advance

The depends on whether the removal of that node from where it was, caused the height of the subtrees of where it was moved to, to differ by two. If not then no, if it did then yes.

There are easy ways to find out on your own too. You could not call it and then call a validation routine to see if the height properly is still correctly maintained, or you could call it and see if any rotations occur.