Tuesday, March 24, 2015

Basic Data Stuctures : AVL Tress

Now to AVL trees, another neat data structure to store lists if information.. This my friends is a courtesy of communism (gasp!) yes, AVL trees were invented by Georgy Adelson-Velsky and E. M. Landis for the history lesson and graphics you can check it the information at WikipediA - AVL Tree.

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

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);

        }
    }


Posted by at No comments:

Thursday, March 12, 2015

Basic Data Structures: Linked Lists

In a return to basics - and plenty of nothing to do - I implemented my own little linked list. Given the state of modern computing I have never really needed to implement a linked list, .Net framework has excellent libraries that manage lists and arrays, however, I guess it is always useful to understand the algorithms and foundations of computer science/

Lets start with what is a linked list:


A linked list is a data structure consisting nodes which together represent a sequence. Each node contains at least data and a reference to the next node. Hours and hours have been spent writing about linked lists, so no point on rehashing it again. For more information, you can use the google machine or check Wikepedia's page on the subject. http://en.wikipedia.org/wiki/Linked_list

Now the code

Declaring the node

Nothing fancy, straight forward thing

 public class Node
    {
        public object data;
        //recursive portion of this.
        public Node next;

        public Node(object data)
        {
            this.data = data;
        }
    }

Linked List


  public class myLinkedList
    {
        public Node head;
        Node current;
        
        public void Add(Node n)
        {
            //self explanatory, but just in case
            // if the top has not been initialized, then do it
            if (head == null)
            {
                head = n;
                current = n;
            }
            else
            {
                //if there something there, then just add the new 
                // node to the end, notice you first set the next property, 
                // then set current
                current.next = n;
                current = current.next;
            }

        }

        public void InsertAtTop(Node n)
        {
            current = head;
            //check to make sure there is something 
            // there
            if (n == null) { return; }

            n.next = current;
            head = n;

        }

        public void Insert(Node n)
        {

            //check to make sure there is something 
            // there
            if (n == null) { return; }

            //this operation would check if where should I add a value on the list.
            current = head;
            //check the first element..
            if ((int)current.data >= (int)n.data)
            {
                n.next = current;
                head = n;
                return;
            }

            //if the first element was ok, then move to the rest
            current = current.next;

            while (current != null)
            {
                if ((int)current.data <= (int)n.data)
                {
                    n.next = current.next;
                    current.next = n;
                    return;
                }
                current = current.next;
            }
            //now if I got here then this should be the last item on the list
            current.next = n;

        }

        public string ReverseAndParse()
        {
            string temp = "";

            current = head;
            while (current.next != null)
            {
                temp = string.Concat(current.data.ToString(), temp);
                current = current.next;
            }

            //add the last item...
            temp = string.Concat(current.data.ToString(), temp);
            return temp;
        }

        public string Parse()
        {
            string temp = "";

            current = head;
            while (current.next != null)
            {
                temp = string.Concat(temp, current.data.ToString());
                current = current.next;
            }

            //add the last item...
            temp = string.Concat(temp, current.data.ToString());
            return temp;
        }

        public void DisplayItems()
        {
            Node n = head;

            while (n.next != null)
            {
                Console.WriteLine("Node : {0}", n.data);
                n = n.next;
            }
            //display the lastone
            Console.WriteLine("Node : {0}", n.data);
        }

        public void RemoveDuplicates()
        {
            current = head;
            while (current.next != null)
            {
                Node n = current;

                while (n.next != null)
                {
                    if (n.next.data.Equals(current.data))
                    {
                        n.next = n.next.next;
                    }
                    else
                    {
                        n = n.next;
                    }
                }
                current = current.next;
            }

        }

        public Node Split(object x, Node node)
        {
            Node ihead = node;
            Node tail = node;



            while (node.next != null)
            {
                Node next = node.next;
                if ((int)node.data < (int)x)
                {
                    node.next = ihead;
                    ihead = node;
                }
                else
                {
                    tail.next = node;
                    tail = node;
                }

                node = next;
            }

            //we need the last record
            if ((int)node.data < (int)x)
            {
                node.next = ihead;
                ihead = node;
            }
            else
            {
                tail.next = node;
                tail = node;
            }


            tail.next = null;
            // bottom.next = top;

            this.head = ihead;
            return ihead;

        }

        public Node addNodes(Node first, Node second, int CarryOver)
        {
            Node n = new Node(CarryOver);
            int value = (int)(first == null ? 0 : (int)first.data) + (second == null ? 0 : (int)second.data) + CarryOver;

            n.data = (value >= 10 ? (value - 10) : value);

            if (first != null || second != null)
            {
                Node New = (addNodes((first.next == null ? null : first.next), (second.next == null ? null : second.next), (value / 10)));
                if (New != null)
                {
                    Add(New);
                }
            }

            return n;

        }

        public Node BreakAndFix()
        {
            current = head;

            // Node breaker = new Node(current.next.next.data);
            Node breaker = current.next.next;


            while (current.next != null)
            {
                current = current.next;
            }

            //break it here

            current.next = head.next.next;

            Node slow = head;
            Node fast = head;

            while (fast != null && fast.next != null)
            {
                slow = slow.next;
                fast = fast.next.next;
                if (slow.Equals(fast))
                {
                    break;
                }
            }

            if (fast == null || fast.next == null)
            {
                return null;
            }

            slow = head;

            while (slow != fast)
            {
                slow = slow.next;
                fast = fast.next;
            }

            return fast;
        }
    }
Posted by at No comments:
Subscribe to: Posts (Atom)