AVL Tree Insertion

Here given code implementation process.

//C Program
//AVL Tree insertion
#include <stdio.h>

#include <stdlib.h>

//Avl tree node
struct Node
{
	//Data value of tree
	int data;
	//used to hold the height of current node
	int height;
	//Indicate left and right subtree
	struct Node *left;
	struct Node *right;
};
//Get the height of given node
int height(struct Node *node)
{
	if (node == NULL)
	{
		return 0;
	}
	return node->height;
}
//Get the max value of given two numbers
int max_height(int a, int b)
{
	if (a > b)
	{
		return a;
	}
	else
	{
		return b;
	}
}
//Create a new Avl Tree node
struct Node *new_node(int data)
{
	//Create a tree node
	struct Node *node = (struct Node *) malloc(sizeof(struct Node));
	if (node != NULL)
	{
		//Set initial node values
		node->data = data;
		node->height = 1;
		node->left = NULL;
		node->right = NULL;
	}
	else
	{
		printf("\nMemory overflow");
	}
	return node;
}
// Perform the Right rotate operation
struct Node *right_rotate(struct Node *node)
{
	//Get left child node
	struct Node *left_node = node->left;
	//Get left node right subtree
	struct Node *right_subtree = left_node->right;
	//update the left and right subtree 
	left_node->right = node;
	node->left = right_subtree;
	//Change the height of modified node
	node->height = max_height(height(node->left), height(node->right)) + 1;
	left_node->height = max_height(height(left_node->left), height(left_node->right)) + 1;
	return left_node;
}
// Perform the Left Rotate operation
struct Node *left_rotate(struct Node *node)
{
	// Get right child node
	struct Node *right_node = node->right;
	//Get right node left subtree
	struct Node *left_subtree = right_node->left;
	//update the left and right subtree 
	right_node->left = node;
	node->right = left_subtree;
	//Change the height of modified node
	node->height = max_height(height(node->left), height(node->right)) + 1;
	right_node->height = max_height(height(right_node->left), height(right_node->right)) + 1;
	return right_node;
}
// Get the balance factor
int get_balance_factor(struct Node *node)
{
	if (node == NULL)
	{
		return 0;
	}
	return height(node->left) - height(node->right);
}
// Recursively, add a node in AVL tree
// Duplicate keys (data) are not allowed
struct Node *add_node(struct Node *node, int data)
{
	if (node == NULL)
	{
		//return a new node
		return new_node(data);
	}
	if (data < node->data)
	{
		node->left = add_node(node->left, data);
	}
	else if (data > node->data)
	{
		node->right = add_node(node->right, data);
	}
	else
	{
		//When given key data already exists
		return node;
	}
	// Change the height of current node
	node->height = 1 + max_height(height(node->left), height(node->right));
	//Get balance factor of a node
	int balance_factor = get_balance_factor(node);
	// LL Case
	if (balance_factor > 1 && data < node->left->data)
	{
		return right_rotate(node);
	}
	// RR Case 
	if (balance_factor < -1 && data > node->right->data)
	{
		return left_rotate(node);
	}
	// LL Case
	if (balance_factor > 1 && data > node->left->data)
	{
		node->left = left_rotate(node->left);
		return right_rotate(node);
	}
	// RR Case 
	if (balance_factor < -1 && data < node->right->data)
	{
		node->right = right_rotate(node->right);
		return left_rotate(node);
	}
	return node;
}
//Print the tree in preorder form
void preorder(struct Node *root)
{
	if (root != NULL)
	{
		printf("%d ", root->data);
		preorder(root->left);
		preorder(root->right);
	}
}
//Print the tree in inorder form
void inorder(struct Node *root)
{
	if (root != NULL)
	{
		inorder(root->left);
		printf("%d ", root->data);
		inorder(root->right);
	}
}
// Print the tree in postorder form
void postorder(struct Node *root)
{
	if (root != NULL)
	{
		postorder(root->left);
		postorder(root->right);
		printf("%d ", root->data);
	}
}
int main()
{
	struct Node *root = NULL;
	//add tree node
	root = add_node(root, 12);
	root = add_node(root, 7);
	root = add_node(root, 5);
	root = add_node(root, 19);
	root = add_node(root, 17);
	root = add_node(root, 13);
	root = add_node(root, 11);
	root = add_node(root, 3);
	root = add_node(root, 2);
	/*
	    Resultant  AVL Tree
	    -----------------

	           12
	          /  \ 
	         /    \
	        7      17
	       / \     / \
	      3   11  13  19
	     / \
	    2   5


	*/
	printf("Resultant AVL Tree");
	printf("\nPreorder  : ");
	preorder(root);
	printf("\nInorder   : ");
	inorder(root);
	printf("\nPostorder : ");
	postorder(root);
	return 0;
}

Output

Resultant AVL Tree
Preorder  : 12 7 3 2 5 11 17 13 19
Inorder   : 2 3 5 7 11 12 13 17 19
Postorder : 2 5 3 11 7 13 19 17 12
// Java program
// AVL Tree insertion
//Avl tree node
class Node
{
	public int data;
	public int height;
	public Node left;
	public Node right;
	public Node(int data)
	{
		//Set node value of avl tree
		this.data = data;
		this.height = 1;
		this.left = null;
		this.right = null;
	}
}
class AvlTree
{
	public Node root;
	public AvlTree()
	{
		this.root = null;
	}
	//Get the height of given node
	public int height(Node node)
	{
		if (node == null)
		{
			return 0;
		}
		return node.height;
	}
	//Get the max value of given two numbers
	public int max_height(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Perform the Right rotate operation
	public Node right_rotate(Node node)
	{
		//Get left child node
		Node left_node = node.left;
		//Get left node right subtree
		Node right_subtree = left_node.right;
		//update the left and right subtree 
		left_node.right = node;
		node.left = right_subtree;
		//Change the height of modified node
		node.height = max_height(height(node.left), height(node.right)) + 1;
		left_node.height = max_height(height(left_node.left), height(left_node.right)) + 1;
		return left_node;
	}
	// Perform the Left Rotate operation
	public Node left_rotate(Node node)
	{
		// Get right child node
		Node right_node = node.right;
		//Get right node left subtree
		Node left_subtree = right_node.left;
		//update the left and right subtree 
		right_node.left = node;
		node.right = left_subtree;
		//Change the height of modified node
		node.height = max_height(height(node.left), height(node.right)) + 1;
		right_node.height = max_height(height(right_node.left), height(right_node.right)) + 1;
		return right_node;
	}
	// Get the balance factor
	public int get_balance_factor(Node node)
	{
		if (node == null)
		{
			return 0;
		}
		return height(node.left) - height(node.right);
	}
	// Recursively, add a node in AVL tree
	// Duplicate keys (data) are not allowed
	public Node add_node(Node node, int data)
	{
		if (node == null)
		{
			//return a new node
			return new Node(data);
		}
		if (data < node.data)
		{
			node.left = add_node(node.left, data);
		}
		else if (data > node.data)
		{
			node.right = add_node(node.right, data);
		}
		else
		{
			//When given key data already exists
			return node;
		}
		// Change the height of current node
		node.height = 1 + max_height(height(node.left), height(node.right));
		//Get balance factor of a node
		int balance_factor = get_balance_factor(node);
		// LL Case
		if (balance_factor > 1 && data < node.left.data)
		{
			return right_rotate(node);
		}
		// RR Case 
		if (balance_factor < -1 && data > node.right.data)
		{
			return left_rotate(node);
		}
		// LL Case
		if (balance_factor > 1 && data > node.left.data)
		{
			node.left = left_rotate(node.left);
			return right_rotate(node);
		}
		// RR Case 
		if (balance_factor < -1 && data < node.right.data)
		{
			node.right = right_rotate(node.right);
			return left_rotate(node);
		}
		return node;
	}
	//Print the tree in preorder form
	public void preorder(Node root)
	{
		if (root != null)
		{
			System.out.print("" + root.data + " ");
			preorder(root.left);
			preorder(root.right);
		}
	}
	//Print the tree in inorder form
	public void inorder(Node root)
	{
		if (root != null)
		{
			inorder(root.left);
			System.out.print("" + root.data + " ");
			inorder(root.right);
		}
	}
	// Print the tree in postorder form
	public void postorder(Node root)
	{
		if (root != null)
		{
			postorder(root.left);
			postorder(root.right);
			System.out.print("" + root.data + " ");
		}
	}
	public static void main(String[] args)
	{
		AvlTree obj = new AvlTree();
		//add tree node
		obj.root = obj.add_node(obj.root, 12);
		obj.root = obj.add_node(obj.root, 7);
		obj.root = obj.add_node(obj.root, 5);
		obj.root = obj.add_node(obj.root, 19);
		obj.root = obj.add_node(obj.root, 17);
		obj.root = obj.add_node(obj.root, 13);
		obj.root = obj.add_node(obj.root, 11);
		obj.root = obj.add_node(obj.root, 3);
		obj.root = obj.add_node(obj.root, 2);
		/*
		  Resultant  AVL Tree
		  -----------------

		         12
		        /  \ 
		       /    \
		      7      17
		     / \     / \
		    3   11  13  19
		   / \
		  2   5


		*/
		System.out.print("Resultant AVL Tree");
		System.out.print("\nPreorder  : ");
		obj.preorder(obj.root);
		System.out.print("\nInorder   : ");
		obj.inorder(obj.root);
		System.out.print("\nPostorder : ");
		obj.postorder(obj.root);
	}
}

Output

Resultant AVL Tree
Preorder  : 12 7 3 2 5 11 17 13 19
Inorder   : 2 3 5 7 11 12 13 17 19
Postorder : 2 5 3 11 7 13 19 17 12
//Include header file
#include <iostream>

using namespace std;
// C++ program
// AVL Tree insertion
//Avl tree node
class Node
{
	public: int data;
	int height;
	Node * left;
	Node * right;
	Node(int data)
	{
		//Set node value of avl tree
		this->data = data;
		this->height = 1;
		this->left = NULL;
		this->right = NULL;
	}
};
class AvlTree
{
	public: Node * root;
	AvlTree()
	{
		this->root = NULL;
	}
	//Get the height of given node
	int height(Node * node)
	{
		if (node == NULL)
		{
			return 0;
		}
		return node->height;
	}
	//Get the max value of given two numbers
	int max_height(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Perform the Right rotate operation
	Node * right_rotate(Node * node)
	{
		//Get left child node
		Node * left_node = node->left;
		//Get left node right subtree
		Node * right_subtree = left_node->right;
		//update the left and right subtree 
		left_node->right = node;
		node->left = right_subtree;
		//Change the height of modified node
		node->height = this->max_height(this->height(node->left), this->height(node->right)) + 1;
		left_node->height = this->max_height(this->height(left_node->left), this->height(left_node->right)) + 1;
		return left_node;
	}
	// Perform the Left Rotate operation
	Node * left_rotate(Node * node)
	{
		// Get right child node
		Node * right_node = node->right;
		//Get right node left subtree
		Node * left_subtree = right_node->left;
		//update the left and right subtree 
		right_node->left = node;
		node->right = left_subtree;
		//Change the height of modified node
		node->height = this->max_height(this->height(node->left), this->height(node->right)) + 1;
		right_node->height = this->max_height(this->height(right_node->left), this->height(right_node->right)) + 1;
		return right_node;
	}
	// Get the balance factor
	int get_balance_factor(Node * node)
	{
		if (node == NULL)
		{
			return 0;
		}
		return this->height(node->left) - this->height(node->right);
	}
	// Recursively, add a node in AVL tree
	// Duplicate keys (data) are not allowed
	Node * add_node(Node * node, int data)
	{
		if (node == NULL)
		{
			//return a new node
			return new Node(data);
		}
		if (data < node->data)
		{
			node->left = this->add_node(node->left, data);
		}
		else if (data > node->data)
		{
			node->right = this->add_node(node->right, data);
		}
		else
		{
			//When given key data already exists
			return node;
		}
		// Change the height of current node
		node->height = 1 + this->max_height(this->height(node->left), this->height(node->right));
		//Get balance factor of a node
		int balance_factor = this->get_balance_factor(node);
		// LL Case
		if (balance_factor > 1 && data < node->left->data)
		{
			return this->right_rotate(node);
		}
		// RR Case 
		if (balance_factor < -1 && data > node->right->data)
		{
			return this->left_rotate(node);
		}
		// LL Case
		if (balance_factor > 1 && data > node->left->data)
		{
			node->left = this->left_rotate(node->left);
			return this->right_rotate(node);
		}
		// RR Case 
		if (balance_factor < -1 && data < node->right->data)
		{
			node->right = this->right_rotate(node->right);
			return this->left_rotate(node);
		}
		return node;
	}
	//Print the tree in preorder form
	void preorder(Node * root)
	{
		if (root != NULL)
		{
			cout << "  " << root->data;
			this->preorder(root->left);
			this->preorder(root->right);
		}
	}
	//Print the tree in inorder form
	void inorder(Node * root)
	{
		if (root != NULL)
		{
			this->inorder(root->left);
			cout << "  " << root->data;
			this->inorder(root->right);
		}
	}
	// Print the tree in postorder form
	void postorder(Node * root)
	{
		if (root != NULL)
		{
			this->postorder(root->left);
			this->postorder(root->right);
			cout << "  " << root->data;
		}
	}
};
int main()
{
	AvlTree obj = AvlTree();
	//add tree node
	obj.root = obj.add_node(obj.root, 12);
	obj.root = obj.add_node(obj.root, 7);
	obj.root = obj.add_node(obj.root, 5);
	obj.root = obj.add_node(obj.root, 19);
	obj.root = obj.add_node(obj.root, 17);
	obj.root = obj.add_node(obj.root, 13);
	obj.root = obj.add_node(obj.root, 11);
	obj.root = obj.add_node(obj.root, 3);
	obj.root = obj.add_node(obj.root, 2);
	/*
			  Resultant  AVL Tree
			  -----------------

			         12
			        /  \ 
			       /    \
			      7      17
			     / \     / \
			    3   11  13  19
			   / \
			  2   5


			*/
	cout << "Resultant AVL Tree";
	cout << "\nPreorder  : ";
	obj.preorder(obj.root);
	cout << "\nInorder   : ";
	obj.inorder(obj.root);
	cout << "\nPostorder : ";
	obj.postorder(obj.root);
	return 0;
}

Output

Resultant AVL Tree
Preorder  :   12  7  3  2  5  11  17  13  19
Inorder   :   2  3  5  7  11  12  13  17  19
Postorder :   2  5  3  11  7  13  19  17  12
//Include namespace system
using System;
// C# program
// AVL Tree insertion
//Avl tree node
class Node
{
	public int data;
	public int height;
	public Node left;
	public Node right;
	public Node(int data)
	{
		//Set node value of avl tree
		this.data = data;
		this.height = 1;
		this.left = null;
		this.right = null;
	}
}
class AvlTree
{
	public Node root;
	public AvlTree()
	{
		this.root = null;
	}
	//Get the height of given node
	public int height(Node node)
	{
		if (node == null)
		{
			return 0;
		}
		return node.height;
	}
	//Get the max value of given two numbers
	public int max_height(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Perform the Right rotate operation
	public Node right_rotate(Node node)
	{
		//Get left child node
		Node left_node = node.left;
		//Get left node right subtree
		Node right_subtree = left_node.right;
		//update the left and right subtree 
		left_node.right = node;
		node.left = right_subtree;
		//Change the height of modified node
		node.height = max_height(height(node.left), height(node.right)) + 1;
		left_node.height = max_height(height(left_node.left), height(left_node.right)) + 1;
		return left_node;
	}
	// Perform the Left Rotate operation
	public Node left_rotate(Node node)
	{
		// Get right child node
		Node right_node = node.right;
		//Get right node left subtree
		Node left_subtree = right_node.left;
		//update the left and right subtree 
		right_node.left = node;
		node.right = left_subtree;
		//Change the height of modified node
		node.height = max_height(height(node.left), height(node.right)) + 1;
		right_node.height = max_height(height(right_node.left), height(right_node.right)) + 1;
		return right_node;
	}
	// Get the balance factor
	public int get_balance_factor(Node node)
	{
		if (node == null)
		{
			return 0;
		}
		return height(node.left) - height(node.right);
	}
	// Recursively, add a node in AVL tree
	// Duplicate keys (data) are not allowed
	public Node add_node(Node node, int data)
	{
		if (node == null)
		{
			//return a new node
			return new Node(data);
		}
		if (data < node.data)
		{
			node.left = add_node(node.left, data);
		}
		else if (data > node.data)
		{
			node.right = add_node(node.right, data);
		}
		else
		{
			//When given key data already exists
			return node;
		}
		// Change the height of current node
		node.height = 1 + max_height(height(node.left), height(node.right));
		//Get balance factor of a node
		int balance_factor = get_balance_factor(node);
		// LL Case
		if (balance_factor > 1 && data < node.left.data)
		{
			return right_rotate(node);
		}
		// RR Case 
		if (balance_factor < -1 && data > node.right.data)
		{
			return left_rotate(node);
		}
		// LL Case
		if (balance_factor > 1 && data > node.left.data)
		{
			node.left = left_rotate(node.left);
			return right_rotate(node);
		}
		// RR Case 
		if (balance_factor < -1 && data < node.right.data)
		{
			node.right = right_rotate(node.right);
			return left_rotate(node);
		}
		return node;
	}
	//Print the tree in preorder form
	public void preorder(Node root)
	{
		if (root != null)
		{
			Console.Write("  " + root.data);
			preorder(root.left);
			preorder(root.right);
		}
	}
	//Print the tree in inorder form
	public void inorder(Node root)
	{
		if (root != null)
		{
			inorder(root.left);
			Console.Write("  " + root.data);
			inorder(root.right);
		}
	}
	// Print the tree in postorder form
	public void postorder(Node root)
	{
		if (root != null)
		{
			postorder(root.left);
			postorder(root.right);
			Console.Write("  " + root.data);
		}
	}
	public static void Main(String[] args)
	{
		AvlTree obj = new AvlTree();
		//add tree node
		obj.root = obj.add_node(obj.root, 12);
		obj.root = obj.add_node(obj.root, 7);
		obj.root = obj.add_node(obj.root, 5);
		obj.root = obj.add_node(obj.root, 19);
		obj.root = obj.add_node(obj.root, 17);
		obj.root = obj.add_node(obj.root, 13);
		obj.root = obj.add_node(obj.root, 11);
		obj.root = obj.add_node(obj.root, 3);
		obj.root = obj.add_node(obj.root, 2);
		/*
				  Resultant  AVL Tree
				  -----------------

				         12
				        /  \ 
				       /    \
				      7      17
				     / \     / \
				    3   11  13  19
				   / \
				  2   5


				*/
		Console.Write("Resultant AVL Tree");
		Console.Write("\nPreorder  : ");
		obj.preorder(obj.root);
		Console.Write("\nInorder   : ");
		obj.inorder(obj.root);
		Console.Write("\nPostorder : ");
		obj.postorder(obj.root);
	}
}

Output

Resultant AVL Tree
Preorder  :   12  7  3  2  5  11  17  13  19
Inorder   :   2  3  5  7  11  12  13  17  19
Postorder :   2  5  3  11  7  13  19  17  12
<?php
// Php program
// AVL Tree insertion
//Avl tree node
class Node
{
	public $data;
	public $height;
	public $left;
	public $right;

	function __construct($data)
	{
		//Set node value of avl tree
		$this->data = $data;
		$this->height = 1;
		$this->left = null;
		$this->right = null;
	}
}
class AvlTree
{
	public $root;

	function __construct()
	{
		$this->root = null;
	}
	//Get the height of given node
	public	function height($node)
	{
		if ($node == null)
		{
			return 0;
		}
		return $node->height;
	}
	//Get the max value of given two numbers
	public	function max_height($a, $b)
	{
		if ($a > $b)
		{
			return $a;
		}
		else
		{
			return $b;
		}
	}
	// Perform the Right rotate operation
	public	function right_rotate($node)
	{
		//Get left child node
		$left_node = $node->left;
		//Get left node right subtree
		$right_subtree = $left_node->right;
		//update the left and right subtree 
		$left_node->right = $node;
		$node->left = $right_subtree;
		//Change the height of modified node
		$node->height = $this->max_height($this->height($node->left), $this->height($node->right)) + 1;
		$left_node->height = $this->max_height($this->height($left_node->left), $this->height($left_node->right)) + 1;
		return $left_node;
	}
	// Perform the Left Rotate operation
	public	function left_rotate($node)
	{
		// Get right child node
		$right_node = $node->right;
		//Get right node left subtree
		$left_subtree = $right_node->left;
		//update the left and right subtree 
		$right_node->left = $node;
		$node->right = $left_subtree;
		//Change the height of modified node
		$node->height = $this->max_height($this->height($node->left), $this->height($node->right)) + 1;
		$right_node->height = $this->max_height($this->height($right_node->left), $this->height($right_node->right)) + 1;
		return $right_node;
	}
	// Get the balance factor
	public	function get_balance_factor($node)
	{
		if ($node == null)
		{
			return 0;
		}
		return $this->height($node->left) - $this->height($node->right);
	}
	// Recursively, add a node in AVL tree
	// Duplicate keys (data) are not allowed
	public	function add_node($node, $data)
	{
		if ($node == null)
		{
			//return a new node
			return new Node($data);
		}
		if ($data < $node->data)
		{
			$node->left = $this->add_node($node->left, $data);
		}
		else if ($data > $node->data)
		{
			$node->right = $this->add_node($node->right, $data);
		}
		else
		{
			//When given key data already exists
			return $node;
		}
		// Change the height of current node
		$node->height = 1 + $this->max_height($this->height($node->left), $this->height($node->right));
		//Get balance factor of a node
		$balance_factor = $this->get_balance_factor($node);
		// LL Case
		if ($balance_factor > 1 && $data < $node->left->data)
		{
			return $this->right_rotate($node);
		}
		// RR Case 
		if ($balance_factor < -1 && $data > $node->right->data)
		{
			return $this->left_rotate($node);
		}
		// LL Case
		if ($balance_factor > 1 && $data > $node->left->data)
		{
			$node->left = $this->left_rotate($node->left);
			return $this->right_rotate($node);
		}
		// RR Case 
		if ($balance_factor < -1 && $data < $node->right->data)
		{
			$node->right = $this->right_rotate($node->right);
			return $this->left_rotate($node);
		}
		return $node;
	}
	//Print the tree in preorder form
	public	function preorder($root)
	{
		if ($root != null)
		{
			echo "  ". $root->data;
			$this->preorder($root->left);
			$this->preorder($root->right);
		}
	}
	//Print the tree in inorder form
	public	function inorder($root)
	{
		if ($root != null)
		{
			$this->inorder($root->left);
			echo "  ". $root->data;
			$this->inorder($root->right);
		}
	}
	// Print the tree in postorder form
	public	function postorder($root)
	{
		if ($root != null)
		{
			$this->postorder($root->left);
			$this->postorder($root->right);
			echo "  ". $root->data;
		}
	}
}

function main()
{
	$obj = new AvlTree();
	//add tree node
	$obj->root = $obj->add_node($obj->root, 12);
	$obj->root = $obj->add_node($obj->root, 7);
	$obj->root = $obj->add_node($obj->root, 5);
	$obj->root = $obj->add_node($obj->root, 19);
	$obj->root = $obj->add_node($obj->root, 17);
	$obj->root = $obj->add_node($obj->root, 13);
	$obj->root = $obj->add_node($obj->root, 11);
	$obj->root = $obj->add_node($obj->root, 3);
	$obj->root = $obj->add_node($obj->root, 2);
	/*
			  Resultant  AVL Tree
			  -----------------

			         12
			        /  \ 
			       /    \
			      7      17
			     / \     / \
			    3   11  13  19
			   / \
			  2   5


			*/
	echo "Resultant AVL Tree";
	echo "\nPreorder  : ";
	$obj->preorder($obj->root);
	echo "\nInorder   : ";
	$obj->inorder($obj->root);
	echo "\nPostorder : ";
	$obj->postorder($obj->root);
}
main();

Output

Resultant AVL Tree
Preorder  :   12  7  3  2  5  11  17  13  19
Inorder   :   2  3  5  7  11  12  13  17  19
Postorder :   2  5  3  11  7  13  19  17  12
// Node Js program
// AVL Tree insertion
//Avl tree node
class Node
{
	constructor(data)
	{
		//Set node value of avl tree
		this.data = data;
		this.height = 1;
		this.left = null;
		this.right = null;
	}
}
class AvlTree
{
	constructor()
	{
		this.root = null;
	}
	//Get the height of given node
	height(node)
	{
		if (node == null)
		{
			return 0;
		}
		return node.height;
	}
	//Get the max value of given two numbers
	max_height(a, b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Perform the Right rotate operation
	right_rotate(node)
	{
		//Get left child node
		var left_node = node.left;
		//Get left node right subtree
		var right_subtree = left_node.right;
		//update the left and right subtree 
		left_node.right = node;
		node.left = right_subtree;
		//Change the height of modified node
		node.height = this.max_height(this.height(node.left), this.height(node.right)) + 1;
		left_node.height = this.max_height(this.height(left_node.left), this.height(left_node.right)) + 1;
		return left_node;
	}
	// Perform the Left Rotate operation
	left_rotate(node)
	{
		// Get right child node
		var right_node = node.right;
		//Get right node left subtree
		var left_subtree = right_node.left;
		//update the left and right subtree 
		right_node.left = node;
		node.right = left_subtree;
		//Change the height of modified node
		node.height = this.max_height(this.height(node.left), this.height(node.right)) + 1;
		right_node.height = this.max_height(this.height(right_node.left), this.height(right_node.right)) + 1;
		return right_node;
	}
	// Get the balance factor
	get_balance_factor(node)
	{
		if (node == null)
		{
			return 0;
		}
		return this.height(node.left) - this.height(node.right);
	}
	// Recursively, add a node in AVL tree
	// Duplicate keys (data) are not allowed
	add_node(node, data)
	{
		if (node == null)
		{
			//return a new node
			return new Node(data);
		}
		if (data < node.data)
		{
			node.left = this.add_node(node.left, data);
		}
		else if (data > node.data)
		{
			node.right = this.add_node(node.right, data);
		}
		else
		{
			//When given key data already exists
			return node;
		}
		// Change the height of current node
		node.height = 1 + this.max_height(this.height(node.left), this.height(node.right));
		//Get balance factor of a node
		var balance_factor = this.get_balance_factor(node);
		// LL Case
		if (balance_factor > 1 && data < node.left.data)
		{
			return this.right_rotate(node);
		}
		// RR Case 
		if (balance_factor < -1 && data > node.right.data)
		{
			return this.left_rotate(node);
		}
		// LL Case
		if (balance_factor > 1 && data > node.left.data)
		{
			node.left = this.left_rotate(node.left);
			return this.right_rotate(node);
		}
		// RR Case 
		if (balance_factor < -1 && data < node.right.data)
		{
			node.right = this.right_rotate(node.right);
			return this.left_rotate(node);
		}
		return node;
	}
	//Print the tree in preorder form
	preorder(root)
	{
		if (root != null)
		{
			process.stdout.write("  " + root.data);
			this.preorder(root.left);
			this.preorder(root.right);
		}
	}
	//Print the tree in inorder form
	inorder(root)
	{
		if (root != null)
		{
			this.inorder(root.left);
			process.stdout.write("  " + root.data);
			this.inorder(root.right);
		}
	}
	// Print the tree in postorder form
	postorder(root)
	{
		if (root != null)
		{
			this.postorder(root.left);
			this.postorder(root.right);
			process.stdout.write("  " + root.data);
		}
	}
}

function main()
{
	var obj = new AvlTree();
	//add tree node
	obj.root = obj.add_node(obj.root, 12);
	obj.root = obj.add_node(obj.root, 7);
	obj.root = obj.add_node(obj.root, 5);
	obj.root = obj.add_node(obj.root, 19);
	obj.root = obj.add_node(obj.root, 17);
	obj.root = obj.add_node(obj.root, 13);
	obj.root = obj.add_node(obj.root, 11);
	obj.root = obj.add_node(obj.root, 3);
	obj.root = obj.add_node(obj.root, 2);
	/*
			  Resultant  AVL Tree
			  -----------------

			         12
			        /  \ 
			       /    \
			      7      17
			     / \     / \
			    3   11  13  19
			   / \
			  2   5


			*/
	process.stdout.write("Resultant AVL Tree");
	process.stdout.write("\nPreorder  : ");
	obj.preorder(obj.root);
	process.stdout.write("\nInorder   : ");
	obj.inorder(obj.root);
	process.stdout.write("\nPostorder : ");
	obj.postorder(obj.root);
}
main();

Output

Resultant AVL Tree
Preorder  :   12  7  3  2  5  11  17  13  19
Inorder   :   2  3  5  7  11  12  13  17  19
Postorder :   2  5  3  11  7  13  19  17  12
#  Python 3 program
#  AVL Tree insertion

# Avl tree node
class Node :
	
	def __init__(self, data) :
		# Set node value of avl tree
		self.data = data
		self.height = 1
		self.left = None
		self.right = None
	
class AvlTree :
	
	def __init__(self) :
		self.root = None
	
	# Get the height of given node
	def height(self, node) :
		if (node == None) :
			return 0
		
		return node.height
	
	# Get the max value of given two numbers
	def max_height(self, a, b) :
		if (a > b) :
			return a
		else :
			return b
		
	
	#  Perform the Right rotate operation
	def right_rotate(self, node) :
		# Get left child node
		left_node = node.left
		# Get left node right subtree
		right_subtree = left_node.right
		# update the left and right subtree 
		left_node.right = node
		node.left = right_subtree
		# Change the height of modified node
		node.height = self.max_height(self.height(node.left), self.height(node.right)) + 1
		left_node.height = self.max_height(self.height(left_node.left), self.height(left_node.right)) + 1
		return left_node
	
	#  Perform the Left Rotate operation
	def left_rotate(self, node) :
		#  Get right child node
		right_node = node.right
		# Get right node left subtree
		left_subtree = right_node.left
		# update the left and right subtree 
		right_node.left = node
		node.right = left_subtree
		# Change the height of modified node
		node.height = self.max_height(self.height(node.left), self.height(node.right)) + 1
		right_node.height = self.max_height(self.height(right_node.left), self.height(right_node.right)) + 1
		return right_node
	
	#  Get the balance factor
	def get_balance_factor(self, node) :
		if (node == None) :
			return 0
		
		return self.height(node.left) - self.height(node.right)
	
	#  Recursively, add a node in AVL tree
	#  Duplicate keys (data) are not allowed
	def add_node(self, node, data) :
		if (node == None) :
			# return a new node
			return Node(data)
		
		if (data < node.data) :
			node.left = self.add_node(node.left, data)
		
		elif(data > node.data) :
			node.right = self.add_node(node.right, data)
		else :
			# When given key data already exists
			return node
		
		#  Change the height of current node
		node.height = 1 + self.max_height(self.height(node.left), self.height(node.right))
		# Get balance factor of a node
		balance_factor = self.get_balance_factor(node)
		#  LL Case
		if (balance_factor > 1 and data < node.left.data) :
			return self.right_rotate(node)
		
		#  RR Case 
		if (balance_factor < -1 and data > node.right.data) :
			return self.left_rotate(node)
		
		#  LL Case
		if (balance_factor > 1 and data > node.left.data) :
			node.left = self.left_rotate(node.left)
			return self.right_rotate(node)
		
		#  RR Case 
		if (balance_factor < -1 and data < node.right.data) :
			node.right = self.right_rotate(node.right)
			return self.left_rotate(node)
		
		return node
	
	# Print the tree in preorder form
	def preorder(self, root) :
		if (root != None) :
			print("  ", root.data, end = "")
			self.preorder(root.left)
			self.preorder(root.right)
		
	
	# Print the tree in inorder form
	def inorder(self, root) :
		if (root != None) :
			self.inorder(root.left)
			print("  ", root.data, end = "")
			self.inorder(root.right)
		
	
	#  Print the tree in postorder form
	def postorder(self, root) :
		if (root != None) :
			self.postorder(root.left)
			self.postorder(root.right)
			print("  ", root.data, end = "")
		
	

def main() :
	obj = AvlTree()
	# add tree node
	obj.root = obj.add_node(obj.root, 12)
	obj.root = obj.add_node(obj.root, 7)
	obj.root = obj.add_node(obj.root, 5)
	obj.root = obj.add_node(obj.root, 19)
	obj.root = obj.add_node(obj.root, 17)
	obj.root = obj.add_node(obj.root, 13)
	obj.root = obj.add_node(obj.root, 11)
	obj.root = obj.add_node(obj.root, 3)
	obj.root = obj.add_node(obj.root, 2)
	# 
	# 		  Resultant  AVL Tree
	# 		  -----------------
	# 		         12
	# 		        /  \ 
	# 		       /    \
	# 		      7      17
	# 		     / \     / \
	# 		    3   11  13  19
	# 		   / \
	# 		  2   5
	# 		
	
	print("Resultant AVL Tree", end = "")
	print("\nPreorder  : ", end = "")
	obj.preorder(obj.root)
	print("\nInorder   : ", end = "")
	obj.inorder(obj.root)
	print("\nPostorder : ", end = "")
	obj.postorder(obj.root)

if __name__ == "__main__": main()

Output

Resultant AVL Tree
Preorder  :    12   7   3   2   5   11   17   13   19
Inorder   :    2   3   5   7   11   12   13   17   19
Postorder :    2   5   3   11   7   13   19   17   12
#  Ruby program
#  AVL Tree insertion
# Avl tree node
class Node 

	# Define the accessor and reader of class Node  
	attr_reader :data, :height, :left, :right
	attr_accessor :data, :height, :left, :right

	def initialize(data)
	
		# Set node value of avl tree
		self.data = data
		self.height = 1
		self.left = nil
		self.right = nil
	end
end
class AvlTree 

	# Define the accessor and reader of class AvlTree  
	attr_reader :root
	attr_accessor :root


	
	def initialize()
	
		self.root = nil
	end
	# Get the height of given node
	def height(node)
	
		if (node == nil)
		
			return 0
		end
		return node.height
	end
	# Get the max value of given two numbers
	def max_height(a, b)
	
		if (a > b)
		
			return a
		else
		
			return b
		end
	end
	#  Perform the Right rotate operation
	def right_rotate(node)
	
		# Get left child node
		left_node = node.left
		# Get left node right subtree
		right_subtree = left_node.right
		# update the left and right subtree 
		left_node.right = node
		node.left = right_subtree
		# Change the height of modified node
		node.height = self.max_height(self.height(node.left), self.height(node.right)) + 1
		left_node.height = self.max_height(self.height(left_node.left), self.height(left_node.right)) + 1
		return left_node
	end
	#  Perform the Left Rotate operation
	def left_rotate(node)
	
		#  Get right child node
		right_node = node.right
		# Get right node left subtree
		left_subtree = right_node.left
		# update the left and right subtree 
		right_node.left = node
		node.right = left_subtree
		# Change the height of modified node
		node.height = self.max_height(self.height(node.left), self.height(node.right)) + 1
		right_node.height = self.max_height(self.height(right_node.left), self.height(right_node.right)) + 1
		return right_node
	end
	#  Get the balance factor
	def get_balance_factor(node)
	
		if (node == nil)
		
			return 0
		end
		return self.height(node.left) - self.height(node.right)
	end
	#  Recursively, add a node in AVL tree
	#  Duplicate keys (data) are not allowed
	def add_node(node, data)
	
		if (node == nil)
		
			# return a new node
			return Node.new(data)
		end
		if (data < node.data)
		
			node.left = self.add_node(node.left, data)
		elsif(data > node.data)
		
			node.right = self.add_node(node.right, data)
		else
		
			# When given key data already exists
			return node
		end
		#  Change the height of current node
		node.height = 1 + self.max_height(self.height(node.left), self.height(node.right))
		# Get balance factor of a node
		balance_factor = self.get_balance_factor(node)
		#  LL Case
		if (balance_factor > 1 && data < node.left.data)
		
			return self.right_rotate(node)
		end
		#  RR Case 
		if (balance_factor < -1 && data > node.right.data)
		
			return self.left_rotate(node)
		end
		#  LL Case
		if (balance_factor > 1 && data > node.left.data)
		
			node.left = self.left_rotate(node.left)
			return self.right_rotate(node)
		end
		#  RR Case 
		if (balance_factor < -1 && data < node.right.data)
		
			node.right = self.right_rotate(node.right)
			return self.left_rotate(node)
		end
		return node
	end
	# Print the tree in preorder form
	def preorder(root)
	
		if (root != nil)
		
			print("  ", root.data)
			self.preorder(root.left)
			self.preorder(root.right)
		end
	end
	# Print the tree in inorder form
	def inorder(root)
	
		if (root != nil)
		
			self.inorder(root.left)
			print("  ", root.data)
			self.inorder(root.right)
		end
	end
	#  Print the tree in postorder form
	def postorder(root)
	
		if (root != nil)
		
			self.postorder(root.left)
			self.postorder(root.right)
			print("  ", root.data)
		end
	end
end
def main()

	obj = AvlTree.new()
	# add tree node
	obj.root = obj.add_node(obj.root, 12)
	obj.root = obj.add_node(obj.root, 7)
	obj.root = obj.add_node(obj.root, 5)
	obj.root = obj.add_node(obj.root, 19)
	obj.root = obj.add_node(obj.root, 17)
	obj.root = obj.add_node(obj.root, 13)
	obj.root = obj.add_node(obj.root, 11)
	obj.root = obj.add_node(obj.root, 3)
	obj.root = obj.add_node(obj.root, 2)
	# 
	# 		  Resultant  AVL Tree
	# 		  -----------------
	# 		         12
	# 		        /  \ 
	# 		       /    \
	# 		      7      17
	# 		     / \     / \
	# 		    3   11  13  19
	# 		   / \
	# 		  2   5
	# 		
	
	print("Resultant AVL Tree")
	print("\nPreorder  : ")
	obj.preorder(obj.root)
	print("\nInorder   : ")
	obj.inorder(obj.root)
	print("\nPostorder : ")
	obj.postorder(obj.root)
end
main()

Output

Resultant AVL Tree
Preorder  :   12  7  3  2  5  11  17  13  19
Inorder   :   2  3  5  7  11  12  13  17  19
Postorder :   2  5  3  11  7  13  19  17  12
// Scala program
// AVL Tree insertion

//Avl tree node
class Node(var data: Int,
	var height: Int,
		var left: Node,
			var right: Node)
{
	def this(data: Int)
	{
        //set avl tree node value
		this(data, 1, null, null);
	}
}
class AvlTree(var root: Node)
{
	def this()
	{
		this(null);
	}
	//Get the height of given node
	def height(node: Node): Int = {
		if (node == null)
		{
			return 0;
		}
		return node.height;
	}
	//Get the max value of given two numbers
	def max_height(a: Int, b: Int): Int = {
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Perform the Right rotate operation
	def right_rotate(node: Node): Node = {
		//Get left child node
		var left_node: Node = node.left;
		//Get left node right subtree
		var right_subtree: Node = left_node.right;
		//update the left and right subtree 
		left_node.right = node;
		node.left = right_subtree;
		//Change the height of modified node
		node.height = max_height(height(node.left), height(node.right)) + 1;
		left_node.height = max_height(height(left_node.left), height(left_node.right)) + 1;
		return left_node;
	}
	// Perform the Left Rotate operation
	def left_rotate(node: Node): Node = {
		// Get right child node
		var right_node: Node = node.right;
		//Get right node left subtree
		var left_subtree: Node = right_node.left;
		//update the left and right subtree 
		right_node.left = node;
		node.right = left_subtree;
		//Change the height of modified node
		node.height = max_height(height(node.left), height(node.right)) + 1;
		right_node.height = max_height(height(right_node.left), height(right_node.right)) + 1;
		return right_node;
	}
	// Get the balance factor
	def get_balance_factor(node: Node): Int = {
		if (node == null)
		{
			return 0;
		}
		return height(node.left) - height(node.right);
	}
	// Recursively, add a node in AVL tree
	// Duplicate keys (data) are not allowed
	def add_node(node: Node, data: Int): Node = {
		if (node == null)
		{
			//return a new node
			return new Node(data);
		}
		if (data < node.data)
		{
			node.left = add_node(node.left, data);
		}
		else if (data > node.data)
		{
			node.right = add_node(node.right, data);
		}
		else
		{
			//When given key data already exists
			return node;
		}
		// Change the height of current node
		node.height = 1 + max_height(height(node.left), height(node.right));
		//Get balance factor of a node
		var balance_factor: Int = get_balance_factor(node);
		// LL Case
		if (balance_factor > 1 && data < node.left.data)
		{
			return right_rotate(node);
		}
		// RR Case 
		if (balance_factor < -1 && data > node.right.data)
		{
			return left_rotate(node);
		}
		// LL Case
		if (balance_factor > 1 && data > node.left.data)
		{
			node.left = left_rotate(node.left);
			return right_rotate(node);
		}
		// RR Case 
		if (balance_factor < -1 && data < node.right.data)
		{
			node.right = right_rotate(node.right);
			return left_rotate(node);
		}
		return node;
	}
	//Print the tree in preorder form
	def preorder(root: Node): Unit = {
		if (root != null)
		{
			print("  " + root.data);
			preorder(root.left);
			preorder(root.right);
		}
	}
	//Print the tree in inorder form
	def inorder(root: Node): Unit = {
		if (root != null)
		{
			inorder(root.left);
			print("  " + root.data);
			inorder(root.right);
		}
	}
	// Print the tree in postorder form
	def postorder(root: Node): Unit = {
		if (root != null)
		{
			postorder(root.left);
			postorder(root.right);
			print("  " + root.data);
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: AvlTree = new AvlTree();
		//add tree node
		obj.root = obj.add_node(obj.root, 12);
		obj.root = obj.add_node(obj.root, 7);
		obj.root = obj.add_node(obj.root, 5);
		obj.root = obj.add_node(obj.root, 19);
		obj.root = obj.add_node(obj.root, 17);
		obj.root = obj.add_node(obj.root, 13);
		obj.root = obj.add_node(obj.root, 11);
		obj.root = obj.add_node(obj.root, 3);
		obj.root = obj.add_node(obj.root, 2);
		/*
				  Resultant  AVL Tree
				  -----------------

				         12
				        /  \ 
				       /    \
				      7      17
				     / \     / \
				    3   11  13  19
				   / \
				  2   5


				*/
		print("Resultant AVL Tree");
		print("\nPreorder  : ");
		obj.preorder(obj.root);
		print("\nInorder   : ");
		obj.inorder(obj.root);
		print("\nPostorder : ");
		obj.postorder(obj.root);
	}
}

Output

Resultant AVL Tree
Preorder  :   12  7  3  2  5  11  17  13  19
Inorder   :   2  3  5  7  11  12  13  17  19
Postorder :   2  5  3  11  7  13  19  17  12
// Swift program
// AVL Tree insertion
//Avl tree node
class Node
{
	var data: Int;
	var height: Int;
	var left: Node? ;
	var right: Node? ;
	init(_ data: Int)
	{
		//Set node value of avl tree
		self.data = data;
		self.height = 1;
		self.left = nil;
		self.right = nil;
	}
}
class AvlTree
{
	var root: Node? ;
	init()
	{
		self.root = nil;
	}
	//Get the height of given node
	func height(_ node: Node? ) -> Int
	{
		if (node == nil)
		{
			return 0;
		}
		return node!.height;
	}
	//Get the max value of given two numbers
	func max_height(_ a: Int, _ b: Int) -> Int
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Perform the Right rotate operation
	func right_rotate(_ node: Node? ) -> Node?
	{
		//Get left child node
		let left_node: Node? = node!.left;
		//Get left node right subtree
		let right_subtree: Node? = left_node!.right;
		//update the left and right subtree 
		left_node!.right = node;node!.left = right_subtree;
		//Change the height of modified node
		node!.height = self.max_height(self.height(node!.left), self.height(node!.right)) + 1;left_node!.height = self.max_height(self.height(left_node!.left), self.height(left_node!.right)) + 1;
		return left_node;
	}
	// Perform the Left Rotate operation
	func left_rotate(_ node: Node? ) -> Node?
	{
		// Get right child node
		let right_node: Node? = node!.right;
		//Get right node left subtree
		let left_subtree: Node? = right_node!.left;
		//update the left and right subtree 
		right_node!.left = node;node!.right = left_subtree;
		//Change the height of modified node
		node!.height = self.max_height(self.height(node!.left), self.height(node!.right)) + 1;right_node!.height = self.max_height(self.height(right_node!.left), self.height(right_node!.right)) + 1;
		return right_node;
	}
	// Get the balance factor
	func get_balance_factor(_ node: Node? ) -> Int
	{
		if (node == nil)
		{
			return 0;
		}
		return self.height(node!.left) - self.height(node!.right);
	}
	// Recursively, add a node in AVL tree
	// Duplicate keys (data) are not allowed
	func add_node(_ node: Node? , _ data : Int) -> Node?
	{
		if (node == nil)
		{
			//return a new node
			return Node(data);
		}
		if (data < node!.data)
		{
			node!.left = self.add_node(node!.left, data);
		}
		else if (data > node!.data)
		{
			node!.right = self.add_node(node!.right, data);
		}
		else
		{
			//When given key data already exists
			return node;
		}
		// Change the height of current node
		node!.height = 1 + self.max_height(self.height(node!.left), self.height(node!.right));
		//Get balance factor of a node
		let balance_factor: Int = self.get_balance_factor(node);
		// LL Case
		if (balance_factor > 1 && data < node!.left!.data)
		{
			return self.right_rotate(node);
		}
		// RR Case 
		if (balance_factor < -1 && data > node!.right!.data)
		{
			return self.left_rotate(node);
		}
		// LL Case
		if (balance_factor > 1 && data > node!.left!.data)
		{
			node!.left = self.left_rotate(node!.left);
			return self.right_rotate(node);
		}
		// RR Case 
		if (balance_factor < -1 && data < node!.right!.data)
		{
			node!.right = self.right_rotate(node!.right);
			return self.left_rotate(node);
		}
		return node;
	}
	//Print the tree in preorder form
	func preorder(_ root: Node? )
	{
		if (root != nil)
		{
			print("  ", root!.data, terminator: "");
			self.preorder(root!.left);
			self.preorder(root!.right);
		}
	}
	//Print the tree in inorder form
	func inorder(_ root: Node? )
	{
		if (root != nil)
		{
			self.inorder(root!.left);
			print("  ", root!.data, terminator: "");
			self.inorder(root!.right);
		}
	}
	// Print the tree in postorder form
	func postorder(_ root: Node? )
	{
		if (root != nil)
		{
			self.postorder(root!.left);
			self.postorder(root!.right);
			print("  ", root!.data, terminator: "");
		}
	}
}
func main()
{
	let obj: AvlTree = AvlTree();
	//add tree node
	obj.root = obj.add_node(obj.root, 12);
	obj.root = obj.add_node(obj.root, 7);
	obj.root = obj.add_node(obj.root, 5);
	obj.root = obj.add_node(obj.root, 19);
	obj.root = obj.add_node(obj.root, 17);
	obj.root = obj.add_node(obj.root, 13);
	obj.root = obj.add_node(obj.root, 11);
	obj.root = obj.add_node(obj.root, 3);
	obj.root = obj.add_node(obj.root, 2);
	/*
			  Resultant  AVL Tree
			  -----------------

			         12
			        /  \ 
			       /    \
			      7      17
			     / \     / \
			    3   11  13  19
			   / \
			  2   5


			*/
	print("Resultant AVL Tree", terminator: "");
	print("\nPreorder  : ", terminator: "");
	obj.preorder(obj.root);
	print("\nInorder   : ", terminator: "");
	obj.inorder(obj.root);
	print("\nPostorder : ", terminator: "");
	obj.postorder(obj.root);
}
main();

Output

Resultant AVL Tree
Preorder  :    12   7   3   2   5   11   17   13   19
Inorder   :    2   3   5   7   11   12   13   17   19
Postorder :    2   5   3   11   7   13   19   17   12


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved