Geek Answers Handbook

AVL Tree Balancing

I'm having problems balancing AVL Trees. I was looking for high and low steps for how to balance them, and I just can’t get anything.

I know that there are 4 types:

  • Single rotation left
  • Single right rotation
  • Double rotation left-right
  • Double rotation left and right

But I just can't get how to choose which one and which node to apply to !

Any help would be greatly appreciated!

+4
source share
2 answers

This is a Java implementation, and you get an idea of ​​the algorithm:

private Node<T> rotate(Node<T> n) { if(n.getBf() < -1){ if(n.getRight().getBf() <= 0){ return left(n); } if(n.getRight().getBf() > 0){ return rightLeft(n); } } if(n.getBf() > 1){ if(n.getLeft().getBf() >= 0){ return right(n); } if(n.getLeft().getBf() < 0){ return leftRight(n); } } return n; }

Separate methods for 4 turns:

 /** * Performs a left rotation on a node * * @param n The node to have the left rotation performed on * @return The new root of the subtree that is now balanced due to the rotation */ private Node<T> left(Node<T> n) { if(n != null){ Node<T> temp = n.getRight(); n.setRight(temp.getLeft()); temp.setLeft(n); return temp; } return n; } /** * Performs a right rotation on a node * * @param n The node to have the right rotation performed on * @return The new root of the subtree that is now balanced due to the rotation */ private Node<T> right(Node<T> n) { if(n != null){ Node<T> temp = n.getLeft(); n.setLeft(temp.getRight()); temp.setRight(n); return temp; } return n; } /** * Performs a left right rotation on a node * * @param n The node to have the left right rotation performed on * @return The new root of the subtree that is now balanced due to the rotation */ private Node<T> leftRight(Node<T> n) { n.setLeft(left(n.getLeft())); Node<T> temp = right(n); return temp; } /** * Performs a right left rotation on a node * * @param n The node to have the right left rotation performed on * @return The new root of the subtree that is now balanced due to the rotation */ private Node<T> rightLeft(Node<T> n) { n.setRight(right(n.getRight())); Node<T> temp = left(n); return temp; }
+2
source

The key invariant in the AVL tree is that the balance coefficient of each node is -1, 0, or +1. Here, the "balance factor" is the difference in height between the left and right subtrees. +1 means the left subtree is one higher than the right subtree, -1 means the left subtree is shorter than the right subtree, and 0 means the subtrees are the same size. This information is usually cached at each node.

When you get a node with a balance ratio of -2 or +2, you will need to make a turn. Here one possible setting is possible when a turn is required:

  u (-2) / \ A v (-1) / \ BC

If we fill the heights of these trees, we get

  uh + 2 / \ h-1 A vh + 1 / \ h-1 BC h

If this happens, then with one correct rotation you will get

  v h+1 / \ hu C h / \ h-1 AB h-1

And hey! The tree is balanced. A mirror image of this tree could also be fixed with one rotation to the left.

All rotations of AVL trees can be determined simply by listing possible balance factors in a small range, and then determining which rotations should be applied at each step. I will leave this as an exercise for the reader. :-) If you just want to find the answers, the WL article on AVL trees has a nice image that summarizes all the twists you might need to apply.

Hope this helps!

0
source

More articles:


All Articles