AVL Tree. Just for execrcise.

AVL

#include <cstdlib>
#include <cstdio>
#include <cassert>
#include <utility>
#include <algorithm>


struct AVLTreeNode
{
	int height;
	AVLTreeNode *left;
	AVLTreeNode *right;
	int key;
};

AVLTreeNode *avl_create_new_node(int key, AVLTreeNode *left, AVLTreeNode *right)
{
	AVLTreeNode *result = new AVLTreeNode {};
	result->key = key;
	result->left = left;
	result->right = right;	
	result->height = 1;

	return result;
}

struct AVLTree
{
	AVLTreeNode *rootNode;
};


void avl_init(AVLTree **self)
{
	*self = new AVLTree {};
	(*self)->rootNode = nullptr;
}

void avl_free(AVLTree **self)
{
	// ... (free all nodes)
	//	delete (*self)->rootNode;
	delete *self;
	*self = nullptr;
}

int avl_node_height(AVLTreeNode *node)
{
	if (!node)
		return 0;
	return node->height;
}

AVLTreeNode *avl_insert_node(AVLTreeNode *tree, int key);

void avl_insert(AVLTree *self, int key)
{
	self->rootNode = avl_insert_node(self->rootNode, key);
}

int get_balance_factor(AVLTreeNode *tree)
{
	if (tree == nullptr)
		return 0;

	return avl_node_height(tree->left) - avl_node_height(tree->right);
}

AVLTreeNode *avl_rotate_ll(AVLTreeNode *node_to_rotate);
AVLTreeNode *avl_rotate_lr(AVLTreeNode *node_to_rotate);
AVLTreeNode *avl_rotate_rr(AVLTreeNode *node_to_rotate);	
AVLTreeNode *avl_rotate_rl(AVLTreeNode *node_to_rotate);	


AVLTreeNode *avl_insert_node(AVLTreeNode *tree, int key)
{
	if (tree == nullptr)
	{
		printf("created new node with key %d\n", key);
		return avl_create_new_node(key, nullptr, nullptr);
	}

	if (key < tree->key)
		tree->left = avl_insert_node(tree->left, key);
	else
		tree->right = avl_insert_node(tree->right, key);

	// Update height of this node
	tree->height = std::max(avl_node_height(tree->left), avl_node_height(tree->right)) + 1;

	// printf("new height %d\n", tree->height);

	// Check balancing
	int balance_factor = get_balance_factor(tree);

	std::printf("after insertion %d key, balance factor of node %d is: %d\n", key, tree->key, balance_factor);

	// Find out what case from four possible: ll, rr, lr, rl.

	assert(balance_factor > -3 && balance_factor < 3); // -2..2 should be a vaild range 

	enum UnbalanceKind { UK_Unknown, UK_LL, UK_LR, UK_RR, UK_RL, UK__END };
	const char *UnbalanceKindNames[UK__END] = {"UNKNOWN", "LL", "LR", "RR", "RL"};

	unsigned unbalance_kind_happened = UK_Unknown;

	if (balance_factor == -2)
	{
		// right subtree has grown up
		if (key < tree->right->key)
		{
			unbalance_kind_happened = UK_RL;
		}
		else
		{
			unbalance_kind_happened = UK_RR;
		}
	}
	else if (balance_factor == +2)
	{
		if (key > tree->left->key)
		{
			unbalance_kind_happened = UK_LR;
		}
		else
		{
			unbalance_kind_happened = UK_LL;
		}
	}

	if (unbalance_kind_happened == UK_Unknown)
	{
		// No balance needed
		return tree;
	}

	// std::printf("Unbalancing kind happened: %s\n", UnbalanceKindNames[unbalance_kind_happened]);

	switch(unbalance_kind_happened)
	{
		case UK_LL:
		{
			tree = avl_rotate_ll(tree);
			break;
		}
		case UK_LR:
		{
			tree = avl_rotate_lr(tree);
			tree = avl_rotate_ll(tree);
			break;
		}
		case UK_RR:
		{
			tree = avl_rotate_rr(tree);
			break;
		}
		case UK_RL:
		{
			tree = avl_rotate_rl(tree);
			tree = avl_rotate_rr(tree);
			break;
		}
		default: assert(false); // logic error
	}


	return tree;
}

AVLTreeNode *avl_rotate_ll(AVLTreeNode *node_to_rotate)
{
	auto *intermediate = node_to_rotate->left;

	printf("**rotating LL**\n");

	AVLTreeNode *c_saved = intermediate->right;
	intermediate->right = node_to_rotate;
	node_to_rotate->left = c_saved;

	node_to_rotate->height = std::max(avl_node_height(node_to_rotate->left), 
									avl_node_height(node_to_rotate->right)) + 1;
	intermediate->height = std::max(avl_node_height(intermediate->left), 
									avl_node_height(intermediate->right)) + 1;

	// Now should be balanced with new head *intermediate*

	return intermediate;
}

AVLTreeNode *avl_rotate_lr(AVLTreeNode *node_to_rotate)
{
	// In this kind of rotation, *node_to_rotate* is not changed

	printf("**rotating LR**\n");

	auto *saved_intermediate = node_to_rotate->left;
	node_to_rotate->left = saved_intermediate->right;

	saved_intermediate->right = node_to_rotate->left->left;
	node_to_rotate->left->left = saved_intermediate;

	saved_intermediate->height = std::max(avl_node_height(saved_intermediate->left),
										avl_node_height(saved_intermediate->right)) + 1;
	auto *new_intermediate = saved_intermediate->left;
	node_to_rotate->left->height = std::max(avl_node_height(new_intermediate->left),
										avl_node_height(new_intermediate->right)) + 1;
	node_to_rotate->height = std::max(avl_node_height(node_to_rotate->left),
										avl_node_height(node_to_rotate->right)) + 1;
	// now it should be in LL state

	return node_to_rotate;
}

AVLTreeNode *avl_rotate_rr(AVLTreeNode *node_to_rotate)
{
	printf("**rotating RR**\n");

	auto *intermediate = node_to_rotate->right;
	auto *c_saved = intermediate->left;
	intermediate->left = node_to_rotate;
	node_to_rotate->right = c_saved;

	// btw, node_to_rotate becomes new intermediate awhile itermediate becomes new parent
	node_to_rotate->height = std::max(avl_node_height(node_to_rotate->left), 
									avl_node_height(node_to_rotate->right)) + 1;
	intermediate->height = std::max(avl_node_height(intermediate->left), 
									avl_node_height(intermediate->right)) + 1;

	// Now should be balanced with new head *intermediate*

	return intermediate;
}

AVLTreeNode *avl_rotate_rl(AVLTreeNode *node_to_rotate)
{
	// In this kind of rotation, *node_to_rotate* is not changed

	printf("**rotating RL**\n");

	auto *saved_intermediate = node_to_rotate->right;
	node_to_rotate->right = saved_intermediate->left;
	
	saved_intermediate->left = node_to_rotate->right->right;
	node_to_rotate->right->right = saved_intermediate;

	// now it should be in RR state	

	saved_intermediate->height = std::max(avl_node_height(saved_intermediate->left),
										avl_node_height(saved_intermediate->right)) + 1;
	auto *new_intermediate = saved_intermediate->right;
	node_to_rotate->right->height = std::max(avl_node_height(new_intermediate->left),
										avl_node_height(new_intermediate->right)) + 1;
	node_to_rotate->height = std::max(avl_node_height(node_to_rotate->left),
										avl_node_height(node_to_rotate->right)) + 1;
	

	return node_to_rotate;
}

void avL_visit_preorder(AVLTreeNode *root)
{
    if(root != NULL)
    {
        printf("%d ", root->key);
        avL_visit_preorder(root->left);
        avL_visit_preorder(root->right);
    }
}

void avl_print_tree_preorder(AVLTree *tree)
{
	avL_visit_preorder(tree->rootNode);
	printf("\n");
}

int main(int argc, char const *argv[])
{
	AVLTree *tree;

	avl_init(&tree);

	avl_insert(tree, 10);
	avl_insert(tree, 20);
	avl_insert(tree, 30);
	avl_insert(tree, 40);	
	avl_insert(tree, 50);		
	avl_insert(tree, 25);

	avl_print_tree_preorder(tree);

	avl_free(&tree);

	return 0;
}

Output:

created new node with key 10
created new node with key 20
after insertion 20 key, balance factor of node 10 is: -1
created new node with key 30
after insertion 30 key, balance factor of node 20 is: -1
after insertion 30 key, balance factor of node 10 is: -2
rotating RR
created new node with key 40
after insertion 40 key, balance factor of node 30 is: -1
after insertion 40 key, balance factor of node 20 is: -1
created new node with key 50
after insertion 50 key, balance factor of node 40 is: -1
after insertion 50 key, balance factor of node 30 is: -2
rotating RR
after insertion 50 key, balance factor of node 20 is: -1
created new node with key 25
after insertion 25 key, balance factor of node 30 is: 1
after insertion 25 key, balance factor of node 40 is: 1
after insertion 25 key, balance factor of node 20 is: -2
rotating RL
rotating RR
30 20 10 25 40 50