avl tree delete question

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

Quote:

---

Originally Posted by 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

---

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.