Welcome to weblogs.com.pk Sign in | Join | Help

AVL Tree

In the last project I needed AVL Tree inspired data structure. The base class library doesn't expose any thing that could be extended so I setup a Test Project to establish some building blocks. AVL Tree is a self balancing binary search tree, the first of this kind. The basic idea is after adding the node into the Binary Search Tree, the parent node is checked recursively till root node for either left or right sub-trees have similar height or not; and if not; required rotation is done to balance the heights. The height of the node is its distance in term of children from the root. Here is the first test case for an AVL Tree; that we need to satisfy, and using Visual Studio’s auto class/method generation we end up with such an AVL Tree class.

testclass

Given AVL Tree is a specialized Binary Search Tree and Binary Search Tree is specialized Binary Tree; lets setup this class hierarchy and make these classes Generics aware

classes-1

Now that we have signatures of the required classes; lets start adding some code into them. First of all for the BinaryTreeNode<T>; lets also add Parent property that will be helpful for us next. Lets also add Height property that will tell the number of generation that exists as children and grand children of that specific node. It can be easily coded using recursion.

binarytreenode

For the BinaryTree<T> abstract class; we can add BreadthFirst and DepthFirst methods that for traversing the binary tree. I am using C#’s Action<T> delegate; so we can reuse it in the same class for Clear() and in inherited classes.

binarytree

For the BinarySearchTree<T>; we need to override Contains and Remove from our abstract BinaryTree<T> class. Also note that we have specialized the “T” with condition that it should implement IComparable so that we can add it in our Binary Search Tree (BST) according to the algorithm of BST. The Add(T) method is kept virtual so we can override it subclass; AvlTree later. This method returns the newly added node. The rest is implementation detail that one can learn in Data Structure books or Wikipedia; I am also sharing the whole project through Github so you can look it up there as well

For the AvlTree, the BreadthFirst() is just now calling the BreadthFirst from BinaryTree<T> base class with the delegate that simply populates the List and return it as an array later. Its not production ready approach as its duplicating the data; and we can / should implement Iterators Pattern For the Add; we simply will class base class Add that will insert the data into the tree and returns the node. The parent node the newly added node is now need to check and balance upto the root node for the AVL Tree to work as expected, that we will do next.

bst

For the AvlTree, we need a balanceFactor(Node) that will tell us if the given node is “left heavy” or “right heavy”; it can do this now easily using the “Height” property that we have already established. If the balanceFactor() returns >1 then the node is left heavy and if <-1 then it is right heavy and we need to “balance” it using rotateLeft, rotateRight, rorateLeftRight or rotateRightLeft. If balanceFactor is –1, 0 or 1; then the difference of height between left and right is just one generation / height that we can ignore. These are AVL tree technical specifications that one can read about on Wikipedia etc.

avl-1

  • Single rotations (rotateLeft and rotateRight) are done to the given node.
  • Double rotations are done to the child node and then the given node; for rotateLeftRight; we rotateLeft the left child first and then rotateRight the given node; and for rotateRightLeft we do rotateRight the right child and then rotateLeft the given node

For the single rotation; we select the pivot node and then swap the parents and children according to the rotation type. Double rotations can be implemented calling single rotation methods accordingly.

avl-2

  • The node being rotated parent has the child link to it that gets dormant after the rotation. We are not setting this in the rotation methods instead it is left as responsibility of the caller of these methods as they “know” either to change left or right child of the parent and can refer the parent node easily before calling these rotation methods

Now for the balance() we need to call balanceFactor() to check if the node is left or right heavy.

  • If its left heavy and balanceFactor of its left node is also left heavy then we will simply do rotateRight else we need to do rotateLeftRight
  • If its right heavy and balanceFactor if its right node is left heavy then we will do rotateRightLeft else we will simply do rotateLeft

We also need to set the appropriate child of the parent after the rotation and need to keep balancing parent node recursively till we reach the root node. The root node also need to balance if required

avl-3

As you can see; using the modern languages and their framework libraries; we can implement such classic data structures and build upon these to more exciting data structures. The project is available at https://github.com/khurram-aziz/HelloDataStructures

Published Sunday, November 05, 2017 7:52 PM by khurram
Filed under:

Comments

No Comments

New Comments to this post are disabled