Updating balance of AVL Tree after rotation is made

Page 1 of 1

1 Replies - 3757 Views - Last Post: 09 October 2009 - 12:56 PM

#1 skwo   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 29
  • Joined: 19-September 09

Updating balance of AVL Tree after rotation is made

Posted 30 September 2009 - 11:05 PM

Hi there!
I'm trying to implement AVL Trees. For now I bother only about addition.
I experience problems with the balance. After I added node, I traverse the tree back to the root, updating balance of each node I visit (if I came from left son the balance will be decreased by one, otherwise increased by one). The moment the balance of one of the nodes becomes 0, I stop and the tree is balanced. But if the balance becomes +/-2 I need to do a rotation. Assuming that I did on of the rotations, how do I calculate the new balance of the subtree? Should I also calculate the new balance of the parent of non-balanced subtree?

Thanks a lot!

Is This A Good Question/Topic? 0
  • +

Replies To: Updating balance of AVL Tree after rotation is made

#2 Guest_Neumann*


Reputation:

Re: Updating balance of AVL Tree after rotation is made

Posted 09 October 2009 - 12:56 PM

View Postskwo, on 30 Sep, 2009 - 10:05 PM, said:

how do I calculate the new balance of the subtree?

Balance = height(left subtree) - height(right subtree). The height algorithm is extremely simple, so I assume that if you're working with AVL trees you know how to implement it.

Quote

Should I also calculate the new balance of the parent of non-balanced subtree?

Yes, you should re-calculate the balance of all the nodes you had to visit while performing the addition. You should visit them in the reverse order, starting with the parent of the inserted node. Because the addition is recursive it is very simple to do this.

For example, the addition can look something like this:

addNode (root, item)
  if root is null
	root = item
  else
	add the item to the correct subtree
	if height(t.left) - height(t.right) = 2
	  perform the correct rotations

Was This Post Helpful? 1
Page 1 of 1