AVL-Tree

AVL-Tree copied to clipboard

I have a question regarding the last part of remove() if a Node containing the value to remove is not found. Here's what you've written:

  else
      t = (t.left != null) ? t.left : t.right;

  if(t != null) {
      int leftHeight = t.left != null ? t.left.height : 0;
      int rightHeight = t.right!= null ? t.right.height : 0;
      t.height = Math.max(leftHeight,rightHeight) + 1;
  }
  return t;

My question is: If a Node containing the value to remove is not found, why would one make the root of the Tree being returned equal to the left or right child, depending on if the left-child is null? If a Node containing the value searched for isn't found, shouldn't the tree remain unchanged, as well as the height of the root Node?

I may have completely missed something, and if so I apologize.

Kyle -

No problem, thanks for taking the time to ask. Unfortunately I haven't looked at that code in quite some time. But I think you're right that root should not be modified if remove returns null. Why modify the tree if nothing was actually removed?

The remove method implementation was not written from scratch; it is basically the one from here. So it's certainly possible there are bugs.

I'll take a pull request for any fixes, as long as there is a suitable explanation and/or test cases to go along with it...