CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3
  1. #1
    Join Date
    May 2016
    Posts
    9

    Question Add the ability to Search And Delete , in this AVL tree code

    hello guys

    how can i add the ability to delete and search in this AVL code ?


    Code:
    #include<iostream>
    #include<cstdio>
    #include<sstream>
    #include<algorithm>
    #define pow2(n) (1 << (n))
    using namespace std;
    
    /*
     * Node Declaration
     */
    struct avl_node
    {
        int data;
        struct avl_node *left;
        struct avl_node *right;
    }*root;
    
    /*
     * Class Declaration
     */
    class avlTree
    {
        public:
            int height(avl_node *);
            int diff(avl_node *);
            avl_node *rr_rotation(avl_node *);
            avl_node *ll_rotation(avl_node *);
            avl_node *lr_rotation(avl_node *);
            avl_node *rl_rotation(avl_node *);
            avl_node* balance(avl_node *);
            avl_node* insert(avl_node *, int );
            void display(avl_node *, int);
            void inorder(avl_node *);
            void preorder(avl_node *);
            void postorder(avl_node *);
            avlTree()
            {
                root = NULL;
            }
    };
    
    /*
     * Main Contains Menu
     */
    int main()
    {
        int choice, item;
        avlTree avl;
        while (1)
        {
            cout<<"\n---------------------"<<endl;
            cout<<"AVL Tree Implementation"<<endl;
            cout<<"\n---------------------"<<endl;
            cout<<"1.Insert Element into the tree"<<endl;
            cout<<"2.Display Balanced AVL Tree"<<endl;
            cout<<"3.InOrder traversal"<<endl;
            cout<<"4.PreOrder traversal"<<endl;
            cout<<"5.PostOrder traversal"<<endl;
            cout<<"6.Exit"<<endl;
            cout<<"Enter your Choice: ";
            cin>>choice;
            switch(choice)
            {
            case 1:
                cout<<"Enter value to be inserted: ";
                cin>>item;
                root = avl.insert(root, item);
                break;
            case 2:
                if (root == NULL)
                {
                    cout<<"Tree is Empty"<<endl;
                    continue;
                }
                cout<<"Balanced AVL Tree:"<<endl;
                avl.display(root, 1);
                break;
            case 3:
                cout<<"Inorder Traversal:"<<endl;
                avl.inorder(root);
                cout<<endl;
                break;
            case 4:
                cout<<"Preorder Traversal:"<<endl;
                avl.preorder(root);
                cout<<endl;
                break;
            case 5:
                cout<<"Postorder Traversal:"<<endl;
                avl.postorder(root);
                cout<<endl;
                break;
            case 6:
                exit(1);
                break;
            default:
                cout<<"Wrong Choice"<<endl;
            }
        }
        return 0;
    }
    
    /*
     * Height of AVL Tree
     */
    int avlTree::height(avl_node *temp)
    {
        int h = 0;
        if (temp != NULL)
        {
            int l_height = height (temp->left);
            int r_height = height (temp->right);
            int max_height = max (l_height, r_height);
            h = max_height + 1;
        }
        return h;
    }
    
    /*
     * Height Difference
     */
    int avlTree::diff(avl_node *temp)
    {
        int l_height = height (temp->left);
        int r_height = height (temp->right);
        int b_factor= l_height - r_height;
        return b_factor;
    }
    
    /*
     * Right- Right Rotation
     */
    avl_node *avlTree::rr_rotation(avl_node *parent)
    {
        avl_node *temp;
        temp = parent->right;
        parent->right = temp->left;
        temp->left = parent;
        return temp;
    }
    /*
     * Left- Left Rotation
     */
    avl_node *avlTree::ll_rotation(avl_node *parent)
    {
        avl_node *temp;
        temp = parent->left;
        parent->left = temp->right;
        temp->right = parent;
        return temp;
    }
    
    /*
     * Left - Right Rotation
     */
    avl_node *avlTree::lr_rotation(avl_node *parent)
    {
        avl_node *temp;
        temp = parent->left;
        parent->left = rr_rotation (temp);
        return ll_rotation (parent);
    }
    
    /*
     * Right- Left Rotation
     */
    avl_node *avlTree::rl_rotation(avl_node *parent)
    {
        avl_node *temp;
        temp = parent->right;
        parent->right = ll_rotation (temp);
        return rr_rotation (parent);
    }
    
    /*
     * Balancing AVL Tree
     */
    avl_node *avlTree::balance(avl_node *temp)
    {
        int bal_factor = diff (temp);
        if (bal_factor > 1)
        {
            if (diff (temp->left) > 0)
                temp = ll_rotation (temp);
            else
                temp = lr_rotation (temp);
        }
        else if (bal_factor < -1)
        {
            if (diff (temp->right) > 0)
                temp = rl_rotation (temp);
            else
                temp = rr_rotation (temp);
        }
        return temp;
    }
    
    /*
     * Insert Element into the tree
     */
    avl_node *avlTree::insert(avl_node *root, int value)
    {
        if (root == NULL)
        {
            root = new avl_node;
            root->data = value;
            root->left = NULL;
            root->right = NULL;
            return root;
        }
        else if (value < root->data)
        {
            root->left = insert(root->left, value);
            root = balance (root);
        }
        else if (value >= root->data)
        {
            root->right = insert(root->right, value);
            root = balance (root);
        }
        return root;
    }
    
    /*
     * Display AVL Tree
     */
    void avlTree::display(avl_node *ptr, int level)
    {
        int i;
        if (ptr!=NULL)
        {
            display(ptr->right, level + 1);
            printf("\n");
            if (ptr == root)
            cout<<"Root -> ";
            for (i = 0; i < level && ptr != root; i++)
                cout<<"        ";
            cout<<ptr->data;
            display(ptr->left, level + 1);
        }
    }
    
    /*
     * Inorder Traversal of AVL Tree
     */
    void avlTree::inorder(avl_node *tree)
    {
        if (tree == NULL)
            return;
        inorder (tree->left);
        cout<<tree->data<<"  ";
        inorder (tree->right);
    }
    /*
     * Preorder Traversal of AVL Tree
     */
    void avlTree::preorder(avl_node *tree)
    {
        if (tree == NULL)
            return;
        cout<<tree->data<<"  ";
        preorder (tree->left);
        preorder (tree->right);
    
    }
    
    /*
     * Postorder Traversal of AVL Tree
     */
    void avlTree::postorder(avl_node *tree)
    {
        if (tree == NULL)
            return;
        postorder ( tree ->left );
        postorder ( tree ->right );
        cout<<tree->data<<"  ";
    }

  2. #2
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: Add the ability to Search And Delete , in this AVL tree code

    For info about avl deletion, see https://en.wikipedia.org/wiki/AVL_tree

    For searching, this is the same as searching any other tree. The only thing special re an avl tree is the balancing when inserting/deleting.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  3. #3
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: Add the ability to Search And Delete , in this AVL tree code

    If you don't store the height of a subtree in their corresponding root node, you are going to have catastrophic (insertion) performance. Right now, the calculation of the tree's height is O(n) where n is the amount of elements in that sub tree. Every time you do an insertion, you calculate the height of your tree, followed by the height of each subtree you are inserting into.

    This would give you an average cost of O(nlog(n)) per insertion (!). To put this in perspective, that's the same complexity as sorting every element on every insert. Not a single container in the STL has an insert cost higher than O(n) worst case.

    Code:
    #define pow2(n) (1 << (n))
    Why do you need this, and more importantly, why is it a macro?
    Is your question related to IO?
    Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
    It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured