Avl tree node insertion in c

C program for Avl tree node insertion. Here problem description and other solutions.

//C Program
//AVL Tree insertion
#include <stdio.h>
#include <stdlib.h>

// Avl tree node
struct Node
{
    // Data value of tree
    int data;
    // Used to hold the height of current node
    int height;
    // Indicate left and right subtree
    struct Node *left;
    struct Node *right;
};
// Get the height of given node
int height(struct Node *node)
{
    if (node == NULL)
    {
        return 0;
    }
    return node->height;
}
// Get the max value of given two numbers
int max_height(int a, int b)
{
    if (a > b)
    {
        return a;
    }
    else
    {
        return b;
    }
}
// Create a new Avl Tree node
struct Node *new_node(int data)
{
    // Create a tree node
    struct Node *node = (struct Node *) malloc(sizeof(struct Node));
    if (node != NULL)
    {
        // Set initial node values
        node->data = data;
        node->height = 1;
        node->left = NULL;
        node->right = NULL;
    }
    else
    {
        printf("\nMemory overflow");
    }
    return node;
}
// Perform the Right rotate operation
struct Node *right_rotate(struct Node *node)
{
    // Get left child node
    struct Node *left_node = node->left;
    //Get left node right subtree
    struct Node *right_subtree = left_node->right;
    // update the left and right subtree 
    left_node->right = node;
    node->left = right_subtree;
    // Change the height of modified node
    node->height = max_height(
      height(node->left), height(node->right)) + 1;
    left_node->height = max_height(
      height(left_node->left), height(left_node->right)) + 1;
    return left_node;
}
// Perform the Left Rotate operation
struct Node *left_rotate(struct Node *node)
{
    // Get right child node
    struct Node *right_node = node->right;
    // Get right node left subtree
    struct Node *left_subtree = right_node->left;
    // update the left and right subtree 
    right_node->left = node;
    node->right = left_subtree;
    // Change the height of modified node
    node->height = max_height(
      height(node->left), height(node->right)) + 1;
    right_node->height = max_height(
      height(right_node->left), height(right_node->right)) + 1;
    return right_node;
}
// Get the balance factor
int get_balance_factor(struct Node *node)
{
    if (node == NULL)
    {
        return 0;
    }
    return height(node->left) - height(node->right);
}
// Recursively, add a node in AVL tree
// Duplicate keys (data) are not allowed
struct Node *add_node(struct Node *node, int data)
{
    if (node == NULL)
    {
        // return a new node
        return new_node(data);
    }
    if (data < node->data)
    {
        node->left = add_node(node->left, data);
    }
    else if (data > node->data)
    {
        node->right = add_node(node->right, data);
    }
    else
    {
        // When given key data already exists
        return node;
    }
    // Change the height of current node
    node->height = 1 + max_height(
      height(node->left), height(node->right));
    // Get balance factor of a node
    int balance_factor = get_balance_factor(node);
    // LL Case
    if (balance_factor > 1 && data < node->left->data)
    {
        return right_rotate(node);
    }
    // RR Case 
    if (balance_factor < -1 && data > node->right->data)
    {
        return left_rotate(node);
    }
    // LL Case
    if (balance_factor > 1 && data > node->left->data)
    {
        node->left = left_rotate(node->left);
        return right_rotate(node);
    }
    // RR Case 
    if (balance_factor < -1 && data < node->right->data)
    {
        node->right = right_rotate(node->right);
        return left_rotate(node);
    }
    return node;
}
// Print the tree in preorder form
void preorder(struct Node *root)
{
    if (root != NULL)
    {
        printf("%d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}
// Print the tree in inorder form
void inorder(struct Node *root)
{
    if (root != NULL)
    {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}
// Print the tree in postorder form
void postorder(struct Node *root)
{
    if (root != NULL)
    {
        postorder(root->left);
        postorder(root->right);
        printf("%d ", root->data);
    }
}
int main()
{
    struct Node *root = NULL;
 


    root = add_node(root, 4);
    root = add_node(root, 7);
    root = add_node(root, 5);
    root = add_node(root, 19);
    root = add_node(root, 17);
    root = add_node(root, 13);
    root = add_node(root, 11);
    root = add_node(root, 3);
    root = add_node(root, 2);
    root = add_node(root, -3);
    /*
      Resultant  AVL Tree
      -----------------
             7
            /  \ 
           /    \
          4      17
         / \     / \
        2   5  13  19
       / \     /
     -3   3   11
    */
    printf("Resultant AVL Tree");
    printf("\nPreorder  : ");
    preorder(root);
    printf("\nInorder   : ");
    inorder(root);
    printf("\nPostorder : ");
    postorder(root);
    return 0;
}

Output

Resultant AVL Tree
Preorder  : 7 4 2 -3 3 5 17 13 11 19
Inorder   : -3 2 3 4 5 7 11 13 17 19
Postorder : -3 3 2 5 4 11 13 19 17 7


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved