A quick AVL tree implementation in c.

avl.c

#define _XOPEN_SOURCE 500 /* Enable certain library functions (strdup) on linux. See feature_test_macros(7) */

#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <string.h>
#include <assert.h>

struct avl_node_s {
	struct avl_node_s *left;
	struct avl_node_s *right;
	int value;
};

typedef struct avl_node_s avl_node_t;

struct avl_tree_s {
	struct avl_node_s *root;
};

typedef struct avl_tree_s avl_tree_t;


/* Create a new AVL tree. */
avl_tree_t *avl_create() {
	avl_tree_t *tree = NULL;

	if( ( tree = malloc( sizeof( avl_tree_t ) ) ) == NULL ) {
		return NULL;
	}

	tree->root = NULL;

	return tree;
}

/* Initialize a new node. */
avl_node_t *avl_create_node() {
	avl_node_t *node = NULL;
	
	if( ( node = malloc( sizeof( avl_node_t ) ) ) == NULL ) {
		return NULL;
	}

	node->left = NULL;
	node->right = NULL;
	node->value = 0;

	return node;	
}

/* Find the height of an AVL node recursively */
int avl_node_height( avl_node_t *node ) {
	int height_left = 0;
	int height_right = 0;

	if( node->left ) height_left = avl_node_height( node->left );
	if( node->right ) height_right = avl_node_height( node->right );

	return height_right > height_left ? ++height_right : ++height_left;
}

/* Find the balance of an AVL node */
int avl_balance_factor( avl_node_t *node ) {
	int bf = 0;

	if( node->left  ) bf += avl_node_height( node->left );
	if( node->right ) bf -= avl_node_height( node->right );

	return bf ;
}

/* Left Left Rotate */
avl_node_t *avl_rotate_leftleft( avl_node_t *node ) {
 	avl_node_t *a = node;
	avl_node_t *b = a->left;
	
	a->left = b->right;
	b->right = a;

	return( b );
}

/* Left Right Rotate */
avl_node_t *avl_rotate_leftright( avl_node_t *node ) {
	avl_node_t *a = node;
	avl_node_t *b = a->left;
	avl_node_t *c = b->right;
	
	a->left = c->right;
	b->right = c->left; 
	c->left = b;
	c->right = a;

	return( c );
}

/* Right Left Rotate */
avl_node_t *avl_rotate_rightleft( avl_node_t *node ) {
	avl_node_t *a = node;
	avl_node_t *b = a->right;
	avl_node_t *c = b->left;
	
	a->right = c->left;
	b->left = c->right; 
	c->right = b;
	c->left = a;

	return( c );
}

/* Right Right Rotate */
avl_node_t *avl_rotate_rightright( avl_node_t *node ) {
	avl_node_t *a = node;
	avl_node_t *b = a->right;
	
	a->right = b->left;
	b->left = a; 

	return( b );
}

/* Balance a given node */
avl_node_t *avl_balance_node( avl_node_t *node ) {
	avl_node_t *newroot = NULL;

	/* Balance our children, if they exist. */
	if( node->left )
		node->left  = avl_balance_node( node->left  );
	if( node->right ) 
		node->right = avl_balance_node( node->right );

	int bf = avl_balance_factor( node );

	if( bf >= 2 ) {
		/* Left Heavy */	

		if( avl_balance_factor( node->left ) <= -1 ) 
			newroot = avl_rotate_leftright( node );
		else 
			newroot = avl_rotate_leftleft( node );

	} else if( bf <= -2 ) {
		/* Right Heavy */

		if( avl_balance_factor( node->right ) >= 1 )
			newroot = avl_rotate_rightleft( node );
		else 
			newroot = avl_rotate_rightright( node );

	} else {
		/* This node is balanced -- no change. */

		newroot = node;
	}

	return( newroot );	
}

/* Balance a given tree */
void avl_balance( avl_tree_t *tree ) {

	avl_node_t *newroot = NULL;

	newroot = avl_balance_node( tree->root );

	if( newroot != tree->root )  {
		tree->root = newroot; 
	}
}

/* Insert a new node. */
void avl_insert( avl_tree_t *tree, int value ) {
	avl_node_t *node = NULL;
	avl_node_t *next = NULL;
	avl_node_t *last = NULL;

	/* Well, there must be a first case */ 	
	if( tree->root == NULL ) {
		node = avl_create_node();
		node->value = value;

		tree->root = node;

	/* Okay.  We have a root already.  Where do we put this? */
	} else {
		next = tree->root;

		while( next != NULL ) {
			last = next;

			if( value < next->value ) {
				next = next->left;

			} else if( value > next->value ) {
				next = next->right;

			/* Have we already inserted this node? */
			} else if( value == next->value ) {
				/* This shouldn't happen. */	
			}
		}

		node = avl_create_node();
		node->value = value;

		if( value < last->value ) last->left = node;
		if( value > last->value ) last->right = node;
		
	}

	avl_balance( tree );
}

/* Find the node containing a given value */
avl_node_t *avl_find( avl_tree_t *tree, int value ) {
	avl_node_t *current = tree->root;

	while( current && current->value != value ) {
		if( value > current->value )
			current = current->right;
		else
			current = current->left;
	}

	return current;
}

/* Do a depth first traverse of a node. */
void avl_traverse_node_dfs( avl_node_t *node, int depth ) {
	int i = 0;

	if( node->left ) avl_traverse_node_dfs( node->left, depth + 2 );

	for( i = 0; i < depth; i++ ) putchar( ' ' );
	printf( "%d: %d\n", node->value, avl_balance_factor( node ) );

	if( node->right ) avl_traverse_node_dfs( node->right, depth + 2 );
}

/* Do a depth first traverse of a tree. */
void avl_traverse_dfs( avl_tree_t *tree ) {
	avl_traverse_node_dfs( tree->root, 0 );
}

int main( int argc, char **argv ) {
	avl_tree_t *tree = NULL;
	int i = 0; 
	int r = 0;


	tree = avl_create();

	/* Insert 1-20 in random order -- this is suboptimal, but easy */
	srand( time( NULL ) );

	for( i = 0; i < 20; i++ ) {
		do {
			r = rand() % 20 + 1;
		} while( avl_find( tree, r ) );

		avl_insert( tree, r );
	}

	avl_traverse_dfs( tree );

	return 0;
}

Another code kata.

License?

No removal :(

Maybe I don't clearly understand your code.
It seems that it must travel the entire tree for blance after each insert. So is it complexity O(n) for each insert?

@ChenYao2333 do you like my implementation? Open to suggestions
https://gist.github.com/quirinpa/dadb3b65135615ed73d11c8d05dee42e

Any improvement on in-place balancing?

I test your algorithm with 1000000 input and it just freeze my screen , the best so far is 1.24 s for that amount of input

@tringuyen1123 Recursive calls caused stack overflow. Welcome to computer programming in C :)

@tconnel welcome to algorithm world, AVL trees are balanced so height should be < 1.44 log2(n + 2). For 1 000 000 elements max height should be < 29. Default stack size on windows 512kb - 1mb and 29 recursion calls not enough to cause stack overflow. There is another problem in the algo. @ChenYao2333 already mentioned a main issue of this implementation. Because nodes don't keep their height during insertion height should be recalculated each time. So that's why it's not "A quick AVL tree implementation in c" but "The slowest AVL tree implementation in c".

Duplicate value insertion will cause an infinite loop. Why not return from there ?

@JKornev well said. I stand corrected.

I am looking for a function to delete nodes! OTL

This isn't an AVL tree it's just a generic BST with balance and height functions. Plus the recursive calls will kill the stack for large data sets, such as described by other users.

I have done a benchmark test to this code, it takes 8331ms to insert 16 * 1024 randomly distributed int32_t values generated by mt19937 (gcc-13, -O2), it's totally a SLOW AVL tree implementation!

#include <kerbal/container/vector.hpp>
#include <kerbal/test/runtime_timer.hpp>
#include <kerbal/random/mersenne_twister_engine.hpp>
#include <iostream>


int main( int argc, char **argv ) {

	typedef kerbal::type_traits::integral_constant<std::size_t, 16 * 1024> N;

	kerbal::container::vector<int> v;
	{
		v.resize(N::value);
		kerbal::random::mt19937 eg;
		eg.generate_n(&v[0], N::value);
		
		//kerbal::algorithm::iota(v.begin(), v.end(), 0);
	}

	avl_tree_t *tree = avl_create();

	{
		kerbal::test::runtime_timer t;
		for (N::value_type i = 0; i < N::value; ++i) {
			avl_insert(tree, v[i]);
		}
		std::cout << t.count() << std::endl;
	}

	return 0;
}