An AVL tree is invented by Adelson-Velsky and Landis and it is the first such data structure to be invented. An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most.
In this program, we are going to share a C program to insert a node in AVL tree. If you are a beginner and want to start learning the C programming, then keep your close attention in this tutorial as I am going to share a C program to insert a node in AVL tree with the output.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 |
#include<stdio.h> #include<stdlib.h> struct Node { int key; struct Node *left; struct Node *right; int height; }; int max(int a, int b); int height(struct Node *N) { if (N == NULL) return 0; return N->height; } int max(int a, int b) { return (a > b)? a : b; } struct Node* newNode(int key) { struct Node* node = (struct Node*) malloc(sizeof(struct Node)); node->key = key; node->left = NULL; node->right = NULL; node->height = 1; return(node); } struct Node *rightRotate(struct Node *y) { struct Node *x = y->left; struct Node *T2 = x->right; x->right = y; y->left = T2; y->height = max(height(y->left), height(y->right))+1; x->height = max(height(x->left), height(x->right))+1; return x; } struct Node *leftRotate(struct Node *x) { struct Node *y = x->right; struct Node *T2 = y->left; y->left = x; x->right = T2; x->height = max(height(x->left), height(x->right))+1; y->height = max(height(y->left), height(y->right))+1; return y; } int getBalance(struct Node *N) { if (N == NULL) return 0; return height(N->left) - height(N->right); } struct Node* insert(struct Node* node, int key) { if (node == NULL) return(newNode(key)); if (key < node->key) node->left = insert(node->left, key); else if (key > node->key) node->right = insert(node->right, key); else // Equal keys are not allowed in BST return node; node->height = 1 + max(height(node->left), height(node->right)); int balance = getBalance(node); if (balance > 1 && key < node->left->key) return rightRotate(node); if (balance < -1 && key > node->right->key) return leftRotate(node); if (balance > 1 && key > node->left->key) { node->left = leftRotate(node->left); return rightRotate(node); } if (balance < -1 && key < node->right->key) { node->right = rightRotate(node->right); return leftRotate(node); } /* return the (unchanged) node pointer */ return node; } void preOrder(struct Node *root) { if(root != NULL) { printf("%d ", root->key); preOrder(root->left); preOrder(root->right); } } int main() { struct Node *root = NULL; root = insert(root, 10); root = insert(root, 20); root = insert(root, 30); root = insert(root, 40); root = insert(root, 50); root = insert(root, 25); printf("Preorder traversal of the constructed AVL" " tree is \n"); preOrder(root); return 0; } |
Preorder traversal of the constructed AVL tree is
30 20 10 25 40 50
Reference: https://en.wikipedia.org/wiki/AVL_tree
If you like FreeWebMentor and you would like to contribute, you can write an article and mail your article to [email protected] Your article will appear on the FreeWebMentor main page and help other developers.
