AVL

avl.c

#include<stdio.h>
#include<stdlib.h>

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

int height_of (struct node *node) {
	if (!node)
		return 0;
	return node->height;
}

int max (int a, int b) {
	return (a > b) ? a : b;
}

/// \brief Initializes a new node allocated _on the heap_
struct node *init_node (int key) {
	struct node *node = malloc(sizeof(struct node));
	node->key = key;
	node->left = NULL;
	node->right = NULL;
	node->height = 1;
	return node;
}

struct node *right_rotate (struct node *y) {
	struct node *x = y->left;
	struct node *T2 = x->right;

	// Perform rotation
	x->right = y;
	y->left = T2;

	// Update heights
	y->height = max(height_of(y->left), height_of(y->right)) + 1;
	x->height = max(height_of(x->left), height_of(x->right)) + 1;

	// Return new root
	return x;
}

struct node *left_rotate (struct node *x) {
	struct node *y = x->right;
	struct node *T2 = y->left;

	y->left = x;
	x->right = T2;

	// Update heights
	x->height = max(height_of(x->left), height_of(x->right)) + 1;
	y->height = max(height_of(y->left), height_of(y->right)) + 1;

	return y;
}

int get_balance (struct node *node) {
	if (!node)
		return 0;
	return height_of(node->left) - height_of(node->right);
}

struct node *do_balance (struct node *node, int key) {
	node->height = 1 + max(height_of(node->left), height_of(node->right));
	int balance = get_balance(node);

	if (balance > 1 && key < node->left->key) {
		return right_rotate(node);
	}

	if (balance < -1 && key > node->right->key) {
		return left_rotate(node);
	}

	if (balance > 1 && key > node->left->key) {
		node->left = left_rotate(node->left);
		return right_rotate(node);
	}

	if (balance < -1 && key < node->right->key) {
		node->right = right_rotate(node->right);
		return left_rotate(node);
	}

	return node;
}

struct node *insert (struct node *node, int key) {
	if (!node)
		return init_node(key);

	if (key < node->key)
		node->left = insert(node->left, key);
	else if (key > node->key)
		node->right = insert(node->right, key);
	else
		return node;

	do_balance(node, key);

	/*
	 * Algorithm:
	 *
	 * insert node
	 *      init_node                                       same
	 *      recursive insertion                             inserted but not balanced
	 *      check if we are done aka are we balanced
	 *          True  -> return node;
	 *          False -> balance
	 */

	return node;
}

void preorder_print (struct node *root) {
	if (!root) return;
	printf("%d ", root->key);
	preorder_print(root->left);
	preorder_print(root->right);
}

int main () {
	struct node *root = 0;

	root = insert(root, 10);
	root = insert(root, 20);
	root = insert(root, 30);
	root = insert(root, 40);
	root = insert(root, 50);
	root = insert(root, 25);
	root = insert(root, 42);



/* The constructed AVL Tree would be
			30
		   / \
		  20 40
         / \  \
        10 25 50
*/

	printf("Preorder traversal of the constructed AVL tree is \n");
	preorder_print(root);

	return 0;
}