Scribd Logo
Upload

Welcome to Scribd!

  • 25 views

    Experiment 9 Que.1-Write A Program To Implement A AVL Tree. Ans.1 - Source Code

    Uploaded by

    abhishek
    This document provides code to implement an AVL tree. It includes functions to insert nodes, rotate the tree for balance, calculate height and balance factor differences, and display the tree. The main function inserts sample values into an empty AVL tree, then calls the display function to output the balanced tree.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Experiment 9 Que.1-Write A Program To Implement A AVL Tree. Ans.1 - Source Code

    Uploaded by

    abhishek
    25 views4 pages
    This document provides code to implement an AVL tree. It includes functions to insert nodes, rotate the tree for balance, calculate height and balance factor differences, and display the tree. The main function inserts sample values into an empty AVL tree, then calls the display function to output the balanced tree.

    Original Description:

    asthetic projects

    Original Title

    TEMLTE

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document provides code to implement an AVL tree. It includes functions to insert nodes, rotate the tree for balance, calculate height and balance factor differences, and display the tree. The main function inserts sample values into an empty AVL tree, then calls the display function to output the balanced tree.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    25 views4 pages

    Experiment 9 Que.1-Write A Program To Implement A AVL Tree. Ans.1 - Source Code

    Uploaded by

    abhishek
    This document provides code to implement an AVL tree. It includes functions to insert nodes, rotate the tree for balance, calculate height and balance factor differences, and display the tree. The main function inserts sample values into an empty AVL tree, then calls the display function to output the balanced tree.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 4

    CHANDIGARH UNIVERSITY SUB-CODE:CSP-232

    GHARUAN, MOHALI SUB-DS LAB

    EXPERIMENT 9
    Que.1- Write a program to implement a AVL tree.
    Ans.1- SOURCE CODE:
    #include<iostream>
    using namespace std;
    struct node
    { int data;
    node *left;
    node *right;
    }*root;
    class avlTree
    { public:
    avlTree()
    {root = NULL;}
    int height(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; }
    int diff(node *temp)
    {
    int l_height = height (temp->left);
    int r_height = height (temp->right);
    int b_factor= l_height - r_height;
    return b_factor; }
    PAGE-1
    node *rr_rotation(node *parent)
    { node *temp;
    temp = parent->right;
    parent->right = temp->left;
    temp->left = parent;
    return temp;
    }
    node *ll_rotation(node *parent)
    { node *temp;
    temp = parent->left;
    parent->left = temp->right;
    temp->right = parent;
    return temp;
    }
    node *lr_rotation(node *parent)
    { node *temp;
    temp = parent->left;
    parent->left = rr_rotation (temp);
    return ll_rotation (parent);
    }
    node *rl_rotation(node *parent)
    {
    node *temp;
    temp = parent->right;
    parent->right = ll_rotation (temp);
    return rr_rotation (parent);
    }
    node *balance(node *temp)
    {
    int bal_factor = diff (temp);
    if (bal_factor > 1)
    PAGE-4
    {
    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;
    }
    node *insert(node *root, int value)
    {
    if (root == NULL)
    {
    root = new 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);
    }
    Abhishek Verma PAGE-3
    18BCS2567
    else if (value >= root->data)
    { root->right = insert(root->right, value);
    root = balance (root);
    }
    return root;
    }
    void display(node *ptr, int level)
    { if (ptr!=NULL)
    { display(ptr->right, level + 1);
    printf("\n");
    if (ptr == root)
    cout<<"Root -> ";
    for (int i = 0; i < level && ptr != root; i++) OUTPUT:
    cout<<" ";
    cout<<ptr->data;
    display(ptr->left, level + 1);
    }
    } };
    int main()
    { avlTree avl;
    root = avl.insert(root,12);root = avl.insert(root,18);
    root = avl.insert(root,21);root = avl.insert(root,78);
    root = avl.insert(root,56);root = avl.insert(root,99);
    cout<<"UID:18BCS2567\nNAME:Abhishek Verma\n";
    cout<<"Balanced AVL Tree:"<<endl;
    avl.display(root, 1);
    return 0; }

    PAGE-4

    You might also like