Answer to Question #245106 in C++ for Zayn

Question

Write a program that creates the following functions
1)function to implement avl tree
2)function to insert data in avl tree
3)function to Delete data from avl tree
4)function that searches data from the avl if its present or not
5)a display function

Note:
No global declarations
1)Call the functions in main using menu
2)Implement default, copy and parameterized constructor
3)Implement destructor

Answer 1

#include<stdio.h>
#include<stdlib.h>

//Function to get maximum of two integers
int max(int a, int b)
{
    return (a > b)? a : b;
}


// An AVL tree node
struct AVLNode
{
    int data;
    struct AVLNode * left;
    struct AVLNode * right;
    int height;
};

class Tree {
public:
    AVLNode * root;
    
    Tree() {
        root = NULL;
    }
    Tree(int val) {
        root->data = val;
        root->left = root->right = NULL;
        root->height = 0;
    }

    Tree(struct AVLNode * r) {
        root->data = r->data;
        root->left = r->left;
        root->right = r->right;
        root->height = r->height;
    }
    ~Tree() {
        printf("Inside destructor");
        root->data = -1;
        root->left = root->right = NULL;
        root->height = -1;
    }
};

//Function to get the height of the tree rooted at N

int height(struct AVLNode * node){

    if (node == NULL)
        return -1;
    return node->height;
}

// Function that allocates a new node with the given data and NULL left and right pointers.
struct AVLNode * newNode(int data) {
    struct AVLNode * tmp = (struct AVLNode *)malloc(sizeof(struct AVLNode));
    tmp->data   = data;
    tmp->left   = NULL;
    tmp->right  = NULL;
    // new node is initially added as leaf and height of leaf is 0
    tmp->height = 0;
    return(tmp);
}

// Function to right rotate subtree rooted at q
struct AVLNode * rightRotate(struct AVLNode * q)
{
    struct AVLNode * p;
    struct AVLNode * hold;

    printf("Right Rotation is Required\n");

    p = q->left;
    hold = p->right;
    p->right = q;
    q->left = hold;

    // Update heights
    q->height = max(height(q->left), height(q->right))+1;
    p->height = max(height(p->left), height(p->right))+1;

    // Return new root
    return p;
}

// Function to left rotate subtree rooted at p
struct AVLNode * leftRotate(struct AVLNode * p)
{
    struct AVLNode * q;
    struct AVLNode * hold;

    printf("Left Rotation is Required\n");

    q = p->right;
    hold = q->left;
    q->left = p;
    p->right = hold;

    //  Update heights
    p->height = max(height(p->left), height(p->right))+1;
    q->height = max(height(q->left), height(q->right))+1;

    // Return new root
    return q;
}

// Function to print Preorder traversal of the tree
void preorder(struct AVLNode *root)
{
    if(root != NULL)
    {
        printf("%d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

// Get Balance factor of node N
int getBalance(struct AVLNode * N)
{
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}


// Recursive function to insert a data in the subtree rooted
// with node and returns the new root of the subtree.
struct AVLNode * insert(struct AVLNode * node, int data)
{
    int balance;
    /* 1.  Perform the normal BST insertion */
    if (node == NULL)
        return(newNode(data));

    if (data < node->data)
        node->left  = insert(node->left, data);
    else if (data > node->data)
        node->right = insert(node->right, data);
    else // Equal Data are not allowed in BST by definition
        return node;

    /* 2. Update height of this ancestor node */
    node->height = 1 + max(height(node->left),height(node->right));

    /* 3. Get the balance factor of this ancestor node to check whether this node became unbalanced */
    balance = getBalance(node);

    // If this node becomes unbalanced, then there are 4 cases

    // Left Left Case
    if (balance > 1 && data < node->left->data)
        return rightRotate(node);

    // Right Right Case
    if (balance < -1 && data > node->right->data)
        return leftRotate(node);

    // Left Right Case
    if (balance > 1 && data > node->left->data)
    {
        node->left =  leftRotate(node->left);
        return rightRotate(node);
    }

    // Right Left Case
    if (balance < -1 && data < node->right->data)
    {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    /* return the (unchanged) node pointer */
    return node;
}

struct AVLNode * minvalNode(struct AVLNode * node)
{
    struct AVLNode * current = node;

    // loop down to find the leftmost leaf
    while(current->left != NULL)
        current = current->left;

    return current;
}


// Recursive function to delete a node with given key
// from subtree with given root. It returns root of
// the modified subtree.
struct AVLNode* deleteNode(struct AVLNode* root, int key)
{
    struct AVLNode * temp;
    int balance;

    // STEP 1: PERFORM STANDARD BST DELETE

    if(root == NULL)
        return root;

    // If the key to be deleted is smaller than the root's key, then it lies in left subtree
    if(key < root->data)
        root->left = deleteNode(root->left, key);

    // If the key to be deleted is greater than the root's key, then it lies in right subtree
    else if(key > root->data)
        root->right = deleteNode(root->right, key);

    // if key is same as root's data, then, this is the node to be deleted
    // This node may have 0 child or 1 child or 2 child nodes
    else
    {
        // node with only one child or no child
        if( (root->left == NULL) || (root->right == NULL) )
        {
            if(root->left)
                temp = root->left;
            else
                temp = root->right;

            // No child case...If there was no left child above else portion will be executed and
            //if right child is also NULL, temp will become NULL which is the case of NO CHILD NODE
            if(temp == NULL)
            {
                temp = root;
                root = NULL;
            }
            else // One child case
             *root = *temp; // Copy the contents of the non-empty child
            free(temp);
        }
        else
        {
            // node with two children: Get the inorder successor (smallest in the right subtree)
            temp = minvalNode(root->right);

            // Copy the inorder successor's data to this node
            root->data = temp->data;

            // Delete the inorder successor
            root->right = deleteNode(root->right, temp->data);
        }
    }

    // If the tree had only one node then return
    if (root == NULL)
      return root;

    // STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
    root->height = 1 + max(height(root->left), height(root->right));

    // STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to check whether this node became unbalanced)
    balance = getBalance(root);

    // If this node becomes unbalanced, then there are 4 cases

    // Left Left Case
    if (balance > 1 && getBalance(root->left) >= 0)
        return rightRotate(root);

    // Left Right Case
    if (balance > 1 && getBalance(root->left) < 0)
    {
        root->left =  leftRotate(root->left);
        return rightRotate(root);
    }

    // Right Right Case
    if (balance < -1 && getBalance(root->right) <= 0)
        return leftRotate(root);

    // Right Left Case
    if (balance < -1 && getBalance(root->right) > 0)
    {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    return root;
}

bool search(struct AVLNode* root, int val) {
    if(root == NULL) {
        return false;
    }
    if(root->data == val) {
        return true;
    }
    if(root->data > val) return search(root->left, val);
    else return search(root->right, val);
}

int main()
{
    Tree r;
    int x;
        // Constructing Tree
    x = 60;
    printf("Inserting %d\n",x);
    r.root = insert(r.root, x);
    printf("Preorder traversal of the constructed AVL tree is \n");
    preorder(r.root);
    printf("\n");

    x= 50;
    printf("Inserting %d\n",x);
    r.root = insert(r.root, x);
    printf("Preorder traversal of the constructed AVL tree is \n");
    preorder(r.root);
    printf("\n");

    x= 30;
    printf("Inserting %d\n",x);
    r.root = insert(r.root, x);
    printf("Preorder traversal of the constructed AVL tree is \n");
    preorder(r.root);
    printf("\n");

    x= 70;
    printf("Inserting %d\n",x);
    r.root = insert(r.root, x);
    printf("Preorder traversal of the constructed AVL tree is \n");
    preorder(r.root);
    printf("\n");

    x= 80;
    printf("Inserting %d\n",x);
    r.root = insert(r.root, x);
    printf("Preorder traversal of the constructed AVL tree is \n");
    preorder(r.root);
    printf("\n");

    x=20;
    printf("Inserting %d\n",x);
    r.root = insert(r.root, x);
    printf("Preorder traversal of the constructed AVL tree is \n");
    preorder(r.root);
    printf("\n");

    x=25;
    printf("Inserting %d\n",x);
    r.root = insert(r.root, x);
    printf("Preorder traversal of the constructed AVL tree is \n");
    preorder(r.root);
    printf("\n");

    x=100;
    printf("Inserting %d\n",x);
    r.root = insert(r.root, x);
    printf("Preorder traversal of the constructed AVL tree is \n");
    preorder(r.root);
    printf("\n");

    x=90;
    printf("Inserting %d\n",x);
    r.root = insert(r.root, x);
    printf("Preorder traversal of the constructed AVL tree is \n");
    preorder(r.root);
    printf("\n");


    if(search(r.root, 100)) {
        printf("Found 100\n");
    }
    else {
        printf("100 Not Found\n");
    }

    if(search(r.root, 10000)) {
        printf("Found 10000\n");
    }
    else {
        printf("10000 Not Found\n");
    }


    x=90;
    printf("Deleting %d\n",x);
    r.root = deleteNode(r.root, x);
    printf("Preorder traversal of the constructed AVL tree is \n");
    preorder(r.root);
    printf("\n");

    return 0;
}