Summary: in this tutorial, you will learn about AVL tree and how to implement AVL tree in C.
Introduction to AVL tree
An AVL tree is a height-balanced binary search tree, where the balance factor is calculated as follows:
Balance Factor = height(left subtree) – height(right subtree)
In an AVL tree, the balance factor of every node is no more than 1. In practice, the balance factor is often stored at each tree’s node. However, a node’s balance factor can be also computed from the heights of its subtrees.
The AVL stands for Adelson-Velskii and Landis, who are the inventors of the AVL tree.
An AVL tree with N nodes, the complexity of any operations including search, insert and delete takes O(logN) time in the average and worst cases. Notice that for the binary search tree, it takes O(N) time in the worst case and O(logN) time in the average case.
In an AVL tree, you may have to re-balance the tree after performing insert and delete operations to keep the tree height-balanced.
AVL tree implementation in C
AVL tree header file avltree.h:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | #ifndef AVLTREE_H_INCLUDED #define AVLTREE_H_INCLUDED typedef struct node { int data; struct node* left; struct node* right; int height; } node; void dispose(node* t); node* find( int e, node *t ); node* find_min( node *t ); node* find_max( node *t ); node* insert( int data, node *t ); node* delete( int data, node *t ); void display_avl(node* t); int get( node* n ); #endif // AVLTREE_H_INCLUDED |
AVL Tree source code file avltree.c
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 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 | #include <stdio.h> #include "avltree.h" /* remove all nodes of an AVL tree */ void dispose(node* t) { if( t != NULL ) { dispose( t->left ); dispose( t->right ); free( t ); } } /* find a specific node's key in the tree */ node* find(int e, node* t ) { if( t == NULL ) return NULL; if( e < t->data ) return find( e, t->left ); else if( e > t->data ) return find( e, t->right ); else return t; } /* find minimum node's key */ node* find_min( node* t ) { if( t == NULL ) return NULL; else if( t->left == NULL ) return t; else return find_min( t->left ); } /* find maximum node's key */ node* find_max( node* t ) { if( t != NULL ) while( t->right != NULL ) t = t->right; return t; } /* get the height of a node */ static int height( node* n ) { if( n == NULL ) return -1; else return n->height; } /* get maximum value of two integers */ static int max( int l, int r) { return l > r ? l: r; } /* perform a rotation between a k2 node and its left child note: call single_rotate_with_left only if k2 node has a left child */ static node* single_rotate_with_left( node* k2 ) { node* k1 = NULL; k1 = k2->left; k2->left = k1->right; k1->right = k2; k2->height = max( height( k2->left ), height( k2->right ) ) + 1; k1->height = max( height( k1->left ), k2->height ) + 1; return k1; /* new root */ } /* perform a rotation between a node (k1) and its right child note: call single_rotate_with_right only if the k1 node has a right child */ static node* single_rotate_with_right( node* k1 ) { node* k2; k2 = k1->right; k1->right = k2->left; k2->left = k1; k1->height = max( height( k1->left ), height( k1->right ) ) + 1; k2->height = max( height( k2->right ), k1->height ) + 1; return k2; /* New root */ } /* perform the left-right double rotation, note: call double_rotate_with_left only if k3 node has a left child and k3's left child has a right child */ static node* double_rotate_with_left( node* k3 ) { /* Rotate between k1 and k2 */ k3->left = single_rotate_with_right( k3->left ); /* Rotate between K3 and k2 */ return single_rotate_with_left( k3 ); } /* perform the right-left double rotation notes: call double_rotate_with_right only if k1 has a right child and k1's right child has a left child */ static node* double_rotate_with_right( node* k1 ) { /* rotate between K3 and k2 */ k1->right = single_rotate_with_left( k1->right ); /* rotate between k1 and k2 */ return single_rotate_with_right( k1 ); } /* insert a new node into the tree */ node* insert(int e, node* t ) { if( t == NULL ) { /* Create and return a one-node tree */ t = (node*)malloc(sizeof(node)); if( t == NULL ) { fprintf (stderr, "Out of memory!!! (insert)\n"); exit(1); } else { t->data = e; t->height = 0; t->left = t->right = NULL; } } else if( e < t->data ) { t->left = insert( e, t->left ); if( height( t->left ) - height( t->right ) == 2 ) if( e < t->left->data ) t = single_rotate_with_left( t ); else t = double_rotate_with_left( t ); } else if( e > t->data ) { t->right = insert( e, t->right ); if( height( t->right ) - height( t->left ) == 2 ) if( e > t->right->data ) t = single_rotate_with_right( t ); else t = double_rotate_with_right( t ); } /* Else X is in the tree already; we'll do nothing */ t->height = max( height( t->left ), height( t->right ) ) + 1; return t; } /* remove a node in the tree */ node* delete( int e, node* t ) { printf( "Sorry; Delete is unimplemented; %d remains\n", e ); return t; } /* data data of a node */ int get(node* n) { return n->data; } /* Recursively display AVL tree or subtree */ void display_avl(node* t) { if (t == NULL) return; printf("%d",t->data); if(t->left != NULL) printf("(L:%d)",t->left->data); if(t->right != NULL) printf("(R:%d)",t->right->data); printf("\n"); display_avl(t->left); display_avl(t->right); } |
C AVL tree program main.c
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 | #include <stdio.h> #include "avltree.h" int main() { node *t , *p; int i; int j = 0; const int max = 10; printf("--- C AVL Tree Demo ---\n"); t = NULL; printf("Insert: "); for( i = 0; i < max; i++, j = ( j + 7 ) % max ) { t = insert( j, t ); printf("%d ",j); } printf(" into the tree\n\n"); display_avl(t); dispose(t); return 0; } |
In this tutorial, we have introduced you AVL tree data structure and how to implement AVL tree in C.