Basic Data Structures: AVL Trees

Basic Data Structures : AVL Trees

Now to AVL trees, another neat data structure to store lists of information.. This my friends is a courtesy of communism (gasp!) yes, AVL trees were invented by these soviet guys: Georgy Adelson-Velsky and E. M. Landis; for the history lesson and more theory you can check WikipediA – AVL Tree.

Microsoft .Net has an AVL tree library:  class SortetSet<T> but it is always nice to understand the origins and the logic behind.

AVL Tree
AVL Tree

What is an AVL tree

And AVL tree is much like a Balanced Binary Search Tree. A Binary Search Tree (BST) has the following properties:

  • Each node has a value;
  • Each node has a left node which stores only values of lesser value than the node’s value.
  • Each node has a right node which stores only values of greater value than the node’s value

An AVL tree is a self-balancing BST with the following properties:

  • The heights of the two children sub-trees of any node differ at most one.
  • Search, Insert and Delete methods all take O(log n) time in both the average and worse cases
  • Insert and Delete may require the tree to be re-balanced by one or more rotations.

Without further ado: the code

You will find comments in the code detailing the steps needed to balance and rotate nodes.

//define the binary Node 

Class BinaryNode
{
       public int data { get; set; }
        //This node will store nodes with lesser value than the data field
        public BinaryNode left;
       //this node will store nodes with greater values than the data field
        public BinaryNode right;
       //Initialize the Node
        public BinaryNode(int data)
        {
            this.data = data;
            left = null;
            right = null;
            visited = false;
        }
    }

   //this class manages the AVL tree, as you can see is based on as BST 

  Class BinaryTree
  {
        public BinaryNode head; //the tree
       //to keep track of how many nodes we have in the tree
        public int counter;
        public bool isBalanced()
        {
            int left = height(head.left);
            int right = height(head.right);
            //in a balanced tree the difference in height between
           // the left sub-tree height and the right sub-tree it is at most one
            return Math.Abs(left – right) <= 1 ? true : false;
        }
        public int height(BinaryNode n)
        {
            if (n == null)
            {
               //if the value is null, return -1 and the node will be subtracted from the total
                return -1;
            }
            int theleft = height(n.left)+1;
            int theright = height(n.right)+1;
            //the height of a node is the MAX value of the sub-trees
            return Math.Max(theleft , theright  );
        }
        //Class Constructor
        public BinaryTree(BinaryNode n)
        {
            head = n;
        }
        public BinaryNode Delete( BinaryNode root, BinaryNode n)
        {
            if (n == null | root == null)
            {
                return null;
            }
            if (n.data < root.data)
            {
                root.left = Delete(root.left, n);
            }
            if (n.data > root.data)
            {
                root.right = Delete(root.right, n);
            }
            // when deleting a node, then you need to shift Nodes around
            if (root.data == n.data)f
            {
                if (root.left == null && root.right == null)
                {
                    root = null;
                    return root;
                }
                else
                {
                    // Rotate nodes
                    if (root.left  == null)
                {
                        BinaryNode temp = root;
                        root = root.right;
                        temp = null;
                        return root;
                    }
                    else if (root.right == null)
                    {
                        BinaryNode temp = root;
                        root = root.left;
                        temp = null;
                    }
                    else
                    {
                        //rotate to right?… but we may need to go check the depth..
                        BinaryNode min = GetMin(root.right);
                        root.data = min.data;
                        root.right = Delete(root.right,min);
                    }
                }
            }
            return root;
        }
       //This function will return the lowest node in a sub-tree
        private BinaryNode GetMin(BinaryNode root)
        {
            if (root.left == null)
            {
                return root;
            }
            return GetMin(root.left);
        }
        private int HeightDifference(BinaryNode Node)
        {
            return height(Node.left) – height(Node.right);
         }
       //Balancing a node
        private BinaryNode Balance(BinaryNode Node)
        {
           // AVL Steps:
           // 1.- Find the height difference between sub-trees
           // 2.- If  -1 <= difference <= 1 then you are good, otherwise, you need to rotate
           // 3.- Nodes at the top have higher values than the bottom, so the root should store the highest
           //      height, while leaf nodes at bottom would store a height of 1
            int heightDifference= HeightDifference(Node);
            //if the balance factor is > 1 it means the left is deeper than the right
           if (heightDifference> 1)
           {
               //if the node to the left is deeper, then rotate to the left twice
               if (HeightDifference(Node.left) > 0 )
               {
                   //rotate left-left
                   Node = RotateLL(Node);
               }
               else  //there is nothing under it
               {
                   //rotate left – right
                   Node = RotateLR(Node);
               }
           }
           else if (heightDifference< -1)  // a negative value means the right is deeper than the left
           {
               //now let’s check the depth of the right node
               if (HeightDifference(Node.right) > 0) // the right is deeper lets rotate right then left
               {
                   //rotate right – left
                   Node = RotateRL(Node);
               }
               else //there is nothing under
               {
                    //rotate right – right
                   Node = RotateRR(Node);
               }
           }
            return Node;
        }
      //Rotating Nodes, there are 4 cases: right-right, right-left, left-left and left-right
      // right-right: all nodes are to the right of the parent, the pivot becomes the new parent and
      // the original parent becomes the child of the pivot
      // left-left: all nodes are to the left of the parent
      // right-left: pivot is the right child of the parent
      // left-right: pivot is the left child of the parent
        private BinaryNode RotateRR(BinaryNode Node)
        {
            BinaryNode Pivot = Node.right;
            Node.right = Pivot.left;
            Pivot.left = Node;
            return Pivot;
        }
        private BinaryNode RotateLL(BinaryNode Node)
        {
            BinaryNode Pivot = Node.left;
            Node.left = (Pivot == null ? null : Pivot.right);
            Pivot.right = Node;
            return Pivot;
        }
        private BinaryNode RotateLR(BinaryNode Node)
        {
            BinaryNode Pivot = Node.left;
            Node.left = RotateRR(Pivot);
            return RotateLL(Node);
        }
        private BinaryNode RotateRL(BinaryNode Node)
        {
            BinaryNode Pivot = Node.right;
            Node.right = RotateLL(Pivot);
            return RotateRR(Node);
        }
       // Insert with balance
        public void Insert(BinaryNode root, BinaryNode n)
        {
            if (root == null)
            {
                root = n;
                counter++;
            }
            else
            {
                if (root.data > n.data)
                {
                    if (root.left == null)
                    {
                        root.left = n;
                        counter++;
                    }
                    else
                    {
                        Insert(root.left, n);
                       //After inserting, then balance the tree
                        Balance(root.left);
                    }
                }
                else
                {
                    if (root.right == null)
                    {
                        root.right = n;
                        counter++;
                    }
                    else
                    {
                        Insert(root.right, n);
                       //After inserting, then balance the tree
                        Balance(root.right);
                    }
                }
            }
        }
       // This method searches for the value in the tree
        public BinaryNode Find(BinaryNode root, BinaryNode n)
        {
            BinaryNode found;
            if (n == null | root == null)
            {
                return null;
            }
            if (root.data == n.data)
            {
                return root;
            }
            if (root.data > n.data)
            {
                found = Find(root.left, n);
            }
            else
            {
                found = Find(root.right, n);
            }
            return found;
        }
       //use this method to display the data in order
        public void InOrderTransversal()
        {
            BinaryNode temp = head;
            DisplayInOrder(temp);
        }
        //use this method to display the data in order
        public void DisplayInOrder(BinaryNode n)
        {
            if (n == null)
            {
                return;
            }
            DisplayInOrder(n.left);
            Console.WriteLine(“{0}”, n.data);
            DisplayInOrder(n.right);
        }
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s