Sunday, July 27, 2014

AVL Trees

A Tree is a type of data structure made up of nodes.  Each node stores something of value.  There's also some type of hierarchical relationship amongst the nodes such that one node is the parent of its children. 

Trees are typically drawn with circles and lines.  The circles represent the nodes of the tree.  The lines represent the relationships between a parent node and its children.

Binary Trees are a special type of tree in that each node can have at most two children.

A Binary Search Tree is a Binary Tree that conforms to the following conditions:
  • All nodes stored in the left subtree of a node have values that are less than that node.
  • All nodes stored in the right subtree of a node have values that are greater than that node.

The cost of performing an operation on a Binary Search Tree - like find, insert, and remove - are approximately Θ(log n), where n is the number of nodes in the tree.  If the tree is unbalanced, however, the cost of performing an operation regresses to Θ(n).  That's because the tree has essentially become a linked list.
AVL Trees are a special type of Binary Search Tree.  Whenever we insert a node into or remove a node from an AVL Tree we have to perform a balance check on all the nodes.  A node becomes unbalanced if the absolute difference in height between its left and right subtree is more than 1.

The height of a tree is the length of the longest path from the root to a leaf.

The height of a node v in a tree T can also be defined recursively like so:
  • If v is an external (ie. leaf) node, then the height of v is 0
  • Otherwise, the height of v is one plus the maximum height of a child of v.

A tree with one node has a height of 0. An empty tree has a height of -1.

The following tree has a height of 3.


When an AVL Tree becomes unbalanced we have to rearrange the nodes by rotating them so that the AVL Tree becomes balanced again.  There are two types of rotations, single rotations and double rotations.  Which rotation you use depends on where the extra node is.  There are four possible places where the extra node may be:

  • The extra node could be in left subtree of the unbalanced node's left subtree
 When this happens we do a single left rotation.

  • The extra node could be in the right subtree of the unbalanced node's right subtree
When this happens we do a single right rotation.

  • The extra node could be in the left subtree of the unbalanced node's right subtree
 When this happens we do a left rotation and then a right rotation.  That is, we do a double rotation.

  • The extra node could be in the right subtree of the unbalanced node's left subtree
When this happens we do a right rotation and then a left rotation.  That is, we do a double rotation.

Let's go through some examples.  We'll start by inserting the numbers 1 through 7 into an AVL Tree.

Insert 1

Recall that every time we insert a node into an AVL Tree we have to do a balance check.  So even though there's only one node in the tree it will be good practice just to confirm that the tree is indeed balanced



Note: In the rest of these images I'll use the color Lavender for the height of the left subtree and the color Red for the right subtree.  I'm doing this as a visual reminder.  L for left-lavender.  R for right-red.  I'll also highlight newly inserted nodes with the color Yellow and unbalanced nodes with the color Pink.  Heights will be in Green.

The above also showcases that all leaf nodes - nodes with no subtrees - have a height of 0.

Insert 2

Next, we'll check that the tree is balanced 




Looks good so far.  Let's continue.
Insert 3

Is the AVL Tree balanced?
Uh oh!  The balance factor of one of the nodes isn't a -1, 0, or 1.  That means we need to do a rotation.  But which one should we do?  

The way I do it, and this is something I came up with as I couldn't really find anything online that explained how and when to rotate, you start with the unbalanced node (in pink) and work back to the excess node (in Yellow).
In this case the excess node is in the right subtree of the unbalanced node's right subtree.  Now when we have two of the same paths like this that means we just need to do a single rotation.  The path also tells us whether to do a left or a right rotation.  In this case, it's a single right rotation.


And here's what the tree looks like after we rotate.


 Just to prove that the AVL Tree was re-balanced
 
Insert 4
Check that AVL Tree is balanced.


Since the AVL Tree is balanced we can continue.

Insert 5.

Is the AVL Tree balanced?  Nope.

Again, since the excess node is in the right subtree of the unbalanced node's right subtree we do a single right rotation.


And here's what the AVL Tree looks like after the rotation.

Prove that the AVL Tree was re-balanced

Insert 6

 The following shows that the AVL Tree has become unbalanced
 Excess node is in the right subtree of the unbalanced node's right subtree.
Therefore we need to do a single right rotation.


Here's what the AVL Tree looks like after the rotation.

 Proof that AVL Tree was re-balanced.

Insert 7
Balance Check
AVL Tree is not balanced.
Here's what the AVL Tree looks like after the single right rotation.


So far we've only looked at doing single rotations.  Now let's look at two double rotation examples.

Suppose you had the following AVL Tree.


You're probably wondering how this AVL Tree was created.  That is, what sequence of values were inserted into the AVL Tree to get the above result.  The answer is 8, 2, 9, 1, and 3.  It goes by levels.  So at Level 0 there is just the root node.  At Level 1 there is 2 and 9.  Level 2 has 1 and 3.

Insert 4
Next we check the balance of the AVL Tree, but you can probably already guess it's going to be unbalanced since this is an example problem.

This time around, though, the excess node is on the the right subtree of the unbalanced node's left subtree.


Since the paths aren't the same that means we need to do a double rotation.  Again, this is just the way I view it. With double rotations you start at the excess node and work backwards to the unbalanced node performing each rotation that you come across.  In this case the first rotation we come across is a right rotation.


Here's what the AVL Tree looks like after the rotation.

Unfortunately we're not done yet as we still need to do the following left rotation.

Here's what the final result looks like after performing the double rotation.

Let's do one more double rotation example.  Suppose you had the following AVL Tree.


This tree was obtained by inserting the values 7, 5, 25,  3, 10, 50, 8, 20, and 30.

When we insert the value 15 the AVL Tree becomes unbalanced.

This time the excess node is in the left subtree of the unbalanced node's right subtree.

Since the paths aren't the same that means we need to do a double rotation.

Working backwards from the excess node to the unbalanced node, we see that we need to do a left rotation first...

...which gives us the following.


Then we do a right rotation.


Here's what the AVL Tree looks like after doing the double rotation.

If you'd like to experiment more with inserting nodes into and/or removing nodes from an AVL Tree there are Java Applets online that you can play around with.  Here's one that I found from Dr. Stan Matwin.

In order to get the Applet to work you may need to open the Java Control Panel by running the Configure Java application.


Go to the Security tab.


Click the Edit Site List... button which opens the following an Exception Site List window.


Click the Add button. Copy and Paste the URL address of the website containing the Applet.


When you click OK you'll get the following Security Window message.  Just click Continue.


References

No comments:

Post a Comment