The task is to implement an AVL tree with operations such as insertion and in-order traversal to display the elements in sorted order.<\/p>\n\n\n\n
Here\u2019s a complete C program to implement an AVL tree:<\/p>\n\n\n
\n#include <stdio.h>\n#include <stdlib.h>\n\n\/\/ Structure for an AVL tree node\nstruct AVLNode {\n int key;\n struct AVLNode *left;\n struct AVLNode *right;\n int height;\n};\n\n\/\/ Function to get the height of the node\nint height(struct AVLNode *N) {\n if (N == NULL) return 0;\n return N->height;\n}\n\n\/\/ Function to get the maximum of two integers\nint max(int a, int b) {\n return (a > b) ? a : b;\n}\n\n\/\/ Function to create a new AVL node\nstruct AVLNode* newNode(int key) {\n struct AVLNode* node = (struct AVLNode*)malloc(sizeof(struct AVLNode));\n node->key = key;\n node->left = NULL;\n node->right = NULL;\n node->height = 1; \/\/ New node is initially added at leaf\n return node;\n}\n\n\/\/ Right rotate the subtree rooted with y\nstruct AVLNode* rightRotate(struct AVLNode *y) {\n struct AVLNode *x = y->left;\n struct AVLNode *T2 = x->right;\n\n \/\/ Perform rotation\n x->right = y;\n y->left = T2;\n\n \/\/ Update heights\n y->height = max(height(y->left), height(y->right)) + 1;\n x->height = max(height(x->left), height(x->right)) + 1;\n\n \/\/ Return new root\n return x;\n}\n\n\/\/ Left rotate the subtree rooted with x\nstruct AVLNode* leftRotate(struct AVLNode *x) {\n struct AVLNode *y = x->right;\n struct AVLNode *T2 = y->left;\n\n \/\/ Perform rotation\n y->left = x;\n x->right = T2;\n\n \/\/ Update heights\n x->height = max(height(x->left), height(x->right)) + 1;\n y->height = max(height(y->left), height(y->right)) + 1;\n\n \/\/ Return new root\n return y;\n}\n\n\/\/ Get the balance factor of the node\nint getBalance(struct AVLNode *N) {\n if (N == NULL) return 0;\n return height(N->left) - height(N->right);\n}\n\n\/\/ Function to insert a key in the subtree rooted with node and returns the new root of the subtree\nstruct AVLNode* insert(struct AVLNode* node, int key) {\n \/\/ 1. Perform the normal BST insert\n if (node == NULL) return newNode(key);\n\n if (key < node->key) {\n node->left = insert(node->left, key);\n } else if (key > node->key) {\n node->right = insert(node->right, key);\n } else {\n return node; \/\/ Duplicates are not allowed\n }\n\n \/\/ 2. Update the height of this ancestor node\n node->height = 1 + max(height(node->left), height(node->right));\n\n \/\/ 3. Get the balance factor of this ancestor node to check whether it became unbalanced\n int balance = getBalance(node);\n\n \/\/ If this node becomes unbalanced, then there are 4 cases\n\n \/\/ Left Left Case\n if (balance > 1 && key < node->left->key) {\n return rightRotate(node);\n }\n\n \/\/ Right Right Case\n if (balance < -1 && key > node->right->key) {\n return leftRotate(node);\n }\n\n \/\/ Left Right Case\n if (balance > 1 && key > node->left->key) {\n node->left = leftRotate(node->left);\n return rightRotate(node);\n }\n\n \/\/ Right Left Case\n if (balance < -1 && key < node->right->key) {\n node->right = rightRotate(node->right);\n return leftRotate(node);\n }\n\n \/\/ return the (unchanged) node pointer\n return node;\n}\n\n\/\/ Function for in-order traversal\nvoid inOrder(struct AVLNode *root) {\n if (root != NULL) {\n inOrder(root->left);\n printf("%d ", root->key);\n inOrder(root->right);\n }\n}\n\n\/\/ Main function\nint main() {\n struct AVLNode *root = NULL;\n\n int n, key;\n printf("Enter the number of elements to insert: ");\n scanf("%d", &n);\n\n printf("Enter %d elements:\\n", n);\n for (int i = 0; i < n; i++) {\n scanf("%d", &key);\n root = insert(root, key);\n }\n\n printf("In-order traversal of the AVL tree:\\n");\n inOrder(root);\n printf("\\n");\n\n return 0;\n}\n\n<\/pre><\/div>\n\n\nExplanation of the Code<\/h3>\n\n\n\n\n- Node Structure<\/strong>:\n
\n- Each node has a key, pointers to its left and right children, and a height attribute.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
- Height and Balance Functions<\/strong>:\n
\n- The
height<\/code> function returns the height of a node.<\/li>\n\n\n\n- The
getBalance<\/code> function calculates the balance factor of a node (left height – right height).<\/li>\n<\/ul>\n<\/li>\n\n\n\n- Rotations<\/strong>:\n
\n- The program implements right and left rotations to maintain the AVL tree properties.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
- Insertion<\/strong>:\n
\n- The
insert<\/code> function adds a new key while ensuring the tree remains balanced after each insertion.<\/li>\n<\/ul>\n<\/li>\n\n\n\n- In-Order Traversal<\/strong>:\n
\n- The
inOrder<\/code> function prints the keys in ascending order by recursively traversing the left subtree, then the current node, and finally the right subtree.<\/li>\n<\/ul>\n<\/li>\n\n\n\n- Main Function<\/strong>:\n
\n- The main function allows the user to input multiple elements, inserting each into the AVL tree and then performing an in-order traversal to display the sorted elements.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n
Input and Output Example<\/h3>\n\n\n\nInput<\/h4>\n\n\n\ncodeEnter the number of elements to insert: 7
Enter 7 elements:
10 20 30 40 50 25 5
<\/code><\/pre>\n\n\n\nOutput<\/h4>\n\n\n\ncodeIn-order traversal of the AVL tree:
5 10 20 25 30 40 50
<\/code><\/pre>\n\n\n\nExplanation of the Output<\/h3>\n\n\n\n
In this case, the user inserts the elements into the AVL tree. The in-order traversal outputs the keys in sorted order, demonstrating that the tree maintains its properties as a binary search tree.<\/p>\n\n\n\n
Conclusion<\/h3>\n\n\n\n
This C program effectively implements an AVL tree, allowing for efficient insertion and in-order traversal. The balancing mechanism ensures that operations remain efficient even as elements are added, making AVL trees a robust choice for maintaining ordered data. You can experiment with different sets of inputs to see how the AVL tree adjusts itself and maintains balance.<\/p>\n