15 Mar, 2015

AVL trees are great, but it's very easy to be intimidated by AVL tree rotations for a beginner. Gaining an intuitive understanding of AVL trees is important. The supposedly "hard" part is the AVL tree rotations. Initially, it can seem all a bit random. But, I hope to demystify it for you.

What is an AVL tree?

An AVL tree is very similar to binary trees. A binary tree is a data structure in which each element

(1) is the child of another element (also called the parent node),

(2) and can have at most 2 children.

The one exception to this rule is the root element (or node). The root node does not have any parent and is the first or top-most node in the binary tree.

A Binary Search Tree is a clever modification of the binary tree by adding a certain condition. For example, I'll say that all the children of a node whose value is less than the node in question will be placed to its left. Similarly, all nodes greater than it will be placed to the right.

The great thing about a binary search tree is that it's very easy to find an element. Try searching for the node 5 starting from the root node. You'll notice that starting at the root, you don't have to traverse the right sub-tree since 5 is less than 10. We go down the left sub-tree leading us to 8. Again, 5 is less than 8, so we traverse the left child of 8 to reach 5. This is the power of binary search trees(BST).

Why did I say AVL trees are great at the beginning?

AVL trees solve a problem that plagues binary search trees: a BST can become unbalanced. Let's say I've a BST and I want to randomly add numbers from 1 - 100. If the first number that I add is 1, the root node becomes 1. All the other elements now add along the right sub-tree of the root node.

As you can see, the tree above is unbalanced. The height of the sub-trees are displayed in the image. The left and right sub-tree heights of the root is 0 and 3 respectively. The disadvantage of an unbalanced tree is that you tend to lose the primary advantage of a BST, i.e., reduced number of comparisons to find an element. In the worst case, you could even end up with comparing all elements in the BST which is what we are trying to avoid.

AVL is the solution

AVL trees are BST's at their core, but have an additional condition imposed upon it.

AVL property:

How is this achieved?

After the insertion of a new element in to the AVL tree, we check if the AVL property is satisfied. If not, we modify the tree so that it becomes an AVL tree again. These modifications are usually called AVL tree rotations because, intuitively, that's what they are.

(Read the rest in Part 2)

What is an AVL tree?

An AVL tree is very similar to binary trees. A binary tree is a data structure in which each element

(1) is the child of another element (also called the parent node),

(2) and can have at most 2 children.

The one exception to this rule is the root element (or node). The root node does not have any parent and is the first or top-most node in the binary tree.

A Binary Search Tree is a clever modification of the binary tree by adding a certain condition. For example, I'll say that all the children of a node whose value is less than the node in question will be placed to its left. Similarly, all nodes greater than it will be placed to the right.

The great thing about a binary search tree is that it's very easy to find an element. Try searching for the node 5 starting from the root node. You'll notice that starting at the root, you don't have to traverse the right sub-tree since 5 is less than 10. We go down the left sub-tree leading us to 8. Again, 5 is less than 8, so we traverse the left child of 8 to reach 5. This is the power of binary search trees(BST).

Why did I say AVL trees are great at the beginning?

AVL trees solve a problem that plagues binary search trees: a BST can become unbalanced. Let's say I've a BST and I want to randomly add numbers from 1 - 100. If the first number that I add is 1, the root node becomes 1. All the other elements now add along the right sub-tree of the root node.

As you can see, the tree above is unbalanced. The height of the sub-trees are displayed in the image. The left and right sub-tree heights of the root is 0 and 3 respectively. The disadvantage of an unbalanced tree is that you tend to lose the primary advantage of a BST, i.e., reduced number of comparisons to find an element. In the worst case, you could even end up with comparing all elements in the BST which is what we are trying to avoid.

AVL is the solution

AVL trees are BST's at their core, but have an additional condition imposed upon it.

AVL property:

Every node in an AVL tree must satisfy the property that the heights of its left sub-tree and its right sub-tree can differ at most only by 1. This ensures that the tree is always balanced.

How is this achieved?

After the insertion of a new element in to the AVL tree, we check if the AVL property is satisfied. If not, we modify the tree so that it becomes an AVL tree again. These modifications are usually called AVL tree rotations because, intuitively, that's what they are.

(Read the rest in Part 2)