Inserting in an AVL Tree

Procedure :

• Use the same method used for inserting in a BST.

• Set the height of new nodes to either 1 or 0. (1 used in code below)

• Calculate the height and balance factor of each node.

• If the balance factor is not -1, 0 or 1, the tree is imbalanced.

• Perform required rotation.

struct Node *insert(struct Node *ptr, int data) {

	if (ptr == NULL) {
		// Create a new node and assign required values
		struct Node *newNode;
		newNode = (struct Node *)malloc(sizeof(struct Node));
		newNode -> data = data;
		newNode -> left = newNode -> right = NULL;
		newNode -> height = 1;
		return newNode;
	}

	if (data < ptr -> data) 
		ptr -> left = insert(ptr -> left, data);
	else if (data > ptr -> data)
		ptr -> right = insert(ptr -> right, data);

	// Assign height as the max height of left subtree and right subtree
	ptr -> height = nodeHeight(ptr);

	// Check balance factor and perform rotation
	if (balanceFactor(ptr) == 2 && balanceFactor(ptr -> left) == 1) 
		return LLRotation(ptr);
	else if (balanceFactor(ptr) == 2 && balanceFactor(ptr -> left) == -1)
		return LRRotation(ptr);
	else if (balanceFactor(ptr) == -2 && balanceFactor(ptr -> right) == 1)
		return RLRotation(ptr);
	else if (balanceFactor(ptr) == -2 && balanceFactor(ptr -> right) == -1)
		return RRRotation(ptr);

	return ptr;

}

Utility Functions :

int nodeHeight(struct Node *ptr) {
	
	int leftHeight, rightHeight;
	leftHeight = ptr && ptr -> left ? ptr -> left -> height : 0;
	rightHeight = ptr && ptr -> right ? ptr -> right -> height : 0;
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;

}

int balanceFactor(struct Node *ptr) {

	int leftHeight, rightHeight;
	leftHeight = ptr && ptr -> left ? ptr -> left -> height : 0;
	rightHeight = ptr && ptr -> right ? ptr -> right -> height : 0;
	return leftHeight - rightHeight;

}

Contributed by Nitin Ranganath