top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

write c# code about AVL tree contain

+2 votes
450 views

write c# code about AVL tree contains :
1. add node
2. delete node
3. balance
4. replace node
and then print nodes from left leave !

posted Feb 19, 2015 by As M Ob

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

0 votes

AVL Tree is a self balancing binary tree data structure. It has a very efficient Insert, Delete, and Find times. In terms of the depth of an AVL tree on both sides, it differs at most by 1 level. At any other time where difference in height/depth is greater than 1 or less than -1, rebalancing occurs

Sample Code

class Program
    {
        static void Main(string[] args)
        {
            AVL tree = new AVL();
            tree.Add(2);
            tree.Add(1);
            tree.Add(0);
            tree.Add(-1);
            tree.Add(-2);
            tree.Add(3);
            tree.Add(5);
            tree.Add(4);

            tree.DisplayTree();
        }
    }
    class AVL
    {
        class Node
        {
            public int data;
            public Node left;
            public Node right;
            public Node(int data)
            {
                this.data = data;
            }
        }
        Node root;
        public AVL()
        {
        }
        public void Add(int data)
        {
            Node newItem = new Node(data);
            if (root == null)
            {
                root = newItem;
            }
            else
            {
                root = RecursiveInsert(root, newItem);//root = null so we dont lose track of the root and we assign a new root if necessary
            }
        }
        private Node RecursiveInsert(Node current, Node n)
        {
            if (current == null)//base case, we reach this when we go left or right until current is null
            {
                current = n;
                return current;
            }
            else if (n.data < current.data)//if the new node is less than the current node
            {
                current.left = RecursiveInsert(current.left, n);//go left
                current = balance_tree(current);//calling balance after recursion
            }
            else if (n.data > current.data)//if the new node is greater than the current node
            {
                current.right = RecursiveInsert(current.right, n);
                current = balance_tree(current);
            }
            return current;
        }
        private Node balance_tree(Node current)
        {
            int b_factor = balance_factor(current);
            if (b_factor > 1)
            {
                if (balance_factor(current.left) > 0)
                {
                    current = RotateLL(current);
                }
                else
                {
                    current = RotateLR(current);
                }
            }
            else if (b_factor < -1)
            {
                if (balance_factor(current.right) > 0)
                {
                    current = RotateRL(current);
                }
                else
                {
                    current = RotateRR(current);
                }
            }
            return current;
        }
        public void Delete(int target)
        {
             Delete(root, target);
        }
        public void Find(int key)
        {
            if (Find(key, root).data == key)
            {
                Console.WriteLine("{0} was found!", key);
            }
            else
            {
                Console.WriteLine("Nothing found!");
            }
        }
        private Node Find(int target, Node current)
        {

                if (target < current.data)
                {
                    if (target == current.data)
                    {
                        return current;
                    }
                    else
                    return Find(target, current.left);
                }
                else
                {
                    if (target == current.data)
                    {
                        return current;
                    }
                    else
                    return Find(target, current.right);
                }

        }
        public void DisplayTree()
        {
            InOrderDisplayTree(root);
            Console.ReadLine();
        }
        private void InOrderDisplayTree(Node current)
        {
            if (current != null)
            {
                InOrderDisplayTree(current.left);
                Console.Write("({0}) ", current.data);
                InOrderDisplayTree(current.right);
            }
        }
        private int max(int l, int r)//returns maximum of two integers
        {
            return l > r ? l : r;
        }
        private int getHeight(Node current)
        {
            int height = 0;
            if (current != null)
            {
                int l = getHeight(current.left);
                int r = getHeight(current.right);
                int m = max(l, r);
                height = m + 1;
            }
            return height;
        }
        private int balance_factor(Node current)
        {
            int l = getHeight(current.left);
            int r = getHeight(current.right);
            int b_factor = l - r;
            return b_factor;
        }
        private Node RotateRR(Node parent)
        {
            Node pivot = parent.right;
            parent.right = pivot.left;
            pivot.left = parent;
            return pivot;
        }
        private Node RotateLL(Node parent)
        {
            Node pivot = parent.left;
            parent.left = pivot.right;
            pivot.right = parent;
            return pivot;
        }
        private Node RotateLR(Node parent)
        {
            Node pivot = parent.left;
            parent.left = RotateRR(pivot);
            return RotateLL(parent);
        }
        private Node RotateRL(Node parent)
        {
            Node pivot = parent.right;
            parent.right = RotateLL(pivot);
            return RotateRR(parent);
        }
        private Node Delete(Node current, int target)
        {
            Node parent;
            if (current == null)
            { return null; }
            else
            {
                //left subtree
                if (target < current.data)
                {
                    current.left = Delete(current.left, target);
                    if (balance_factor(current) == -2)
                    {
                        if (balance_factor(current.left) <= 0)
                        {
                            current = RotateRR(current);
                        }
                        else
                        {
                            current = RotateRL(current);
                        }
                    }
                }
                //right subtree
                else if (target > current.data)
                {
                    current.right = Delete(current.right, target);
                    if (balance_factor(current) == 2)
                    {
                        if (balance_factor(current.right) <= 0)
                        {
                            current = RotateLL(current);
                        }
                        else
                        {
                            current = RotateLR(current);
                        }
                    }
                }
                //if target is found
                else
                {
                    if (current.right != null)
                    {
                        //delete its inorder successor
                        parent = current.right;
                        while (parent.left != null)
                        {
                            parent = parent.left;
                        }
                        current.data = parent.data;
                        current.right = Delete(current.right, parent.data);
                        if (balance_factor(current) == 2)//rebalancing
                        {
                            if (balance_factor(current.left) <= 0)
                            {
                                current = RotateLL(current);
                            }
                            else { current = RotateLR(current); }
                        }
                    }
                    else
                    {
                        return current.left;
                    }
                }
            }
            return current;
        }
    }
answer Feb 19, 2015 by Salil Agrawal
Similar Questions
+2 votes

Develop a C# Windows Form Application that allows users to do all of the following.
Read a List of patient's information from a text file (*.txt), the input text file is selected from the Open File Dialog.
Your program should accept any text file with the following format:
a. The file contains columns with Basic information about patients.
b. Columns may be separated by spaces and/or tabs.
c. The first line in the file is the column header.
d. After the header, each line represents a Patient (name, address, phone#, Bdate, gander ,wheight, height and blood type).
e. Successfully imported patients are displayed on a data grid view in a second form and added to a patient list.

  1. The user will be able to display on The Grid view :
    a) Female patients.
    b) Patients with age<45 year. c) Save Over weighted patients on a text file .  Note: To find over weighted patients you have to calculate the BMI value. BMI=Weight/ (Height*Height). If BMI <18.5 >>>>> under weighted.
    18.5<=BMI<=25 >>>>>>>Normal.
    BMI>25 >>>>>>>>>>>> Over Weighted.
...