Avl tree node insertion in c#

Csharp program for Avl tree node insertion. Here more information.

// Include namespace system
using System;
// Csharp program
// AVL Tree insertion

// Avl Tree Node
public class TreeNode
{
	public int data;
	public int height;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		// Set node value of avl tree
		this.data = data;
		this.height = 1;
		this.left = null;
		this.right = null;
	}
}
public class AvlTree
{
	// Tree root node
	public TreeNode root;
	public AvlTree()
	{
		// Set value of root
		this.root = null;
	}
	// Get the height of given node
	public int getHeight(TreeNode node)
	{
		if (node == null)
		{
			return 0;
		}
		return node.height;
	}
	// Get the max value of given two numbers
	public int maxHeight(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Perform the Right rotate operation
	public TreeNode rightRotate(TreeNode node)
	{
		// Get left child node
		var leftNode = node.left;
		// Get left node right subtree
		var rightSubtree = leftNode.right;
		// Update the left and right subtree
		leftNode.right = node;
		node.left = rightSubtree;
		// Change the height of modified node
		node.height = this.maxHeight(
          this.getHeight(node.left), 
          this.getHeight(node.right)) + 1;
		leftNode.height = this.maxHeight(
          this.getHeight(leftNode.left), 
          this.getHeight(leftNode.right)) + 1;
		return leftNode;
	}
	// Perform the Left Rotate operation
	public TreeNode leftRotate(TreeNode node)
	{
		// Get right child node
		var rightNode = node.right;
		// Get right node left subtree
		var leftSubtree = rightNode.left;
		// Update the left and right subtree
		rightNode.left = node;
		node.right = leftSubtree;
		// Change the height of modified node
		node.height = this.maxHeight(
          this.getHeight(node.left), 
          this.getHeight(node.right)) + 1;
		rightNode.height = this.maxHeight(
          this.getHeight(rightNode.left), 
          this.getHeight(rightNode.right)) + 1;
		return rightNode;
	}
	// Get the balance factor
	public int getBalanceFactor(TreeNode node)
	{
		if (node == null)
		{
			return 0;
		}
		return this.getHeight(node.left) - 
          this.getHeight(node.right);
	}
	// Recursively, add a node in AVL tree
	// Duplicate keys (data) are not allowed
	public TreeNode addNode(TreeNode node, int data)
	{
		if (node == null)
		{
			// Return a new node
			return new TreeNode(data);
		}
		if (data < node.data)
		{
			node.left = this.addNode(node.left, data);
		}
		else if (data > node.data)
		{
			node.right = this.addNode(node.right, data);
		}
		else
		{
			// When given key data already exists
			return node;
		}
		// Change the height of current node
		node.height = 1 + this.maxHeight(
          this.getHeight(node.left), 
          this.getHeight(node.right));
		// Get balance factor of a node
		var factor = this.getBalanceFactor(node);
		// LL Case
		if (factor > 1 && data < node.left.data)
		{
			return this.rightRotate(node);
		}
		// RR Case
		if (factor < -1 && data > node.right.data)
		{
			return this.leftRotate(node);
		}
		// LL Case
		if (factor > 1 && data > node.left.data)
		{
			node.left = this.leftRotate(node.left);
			return this.rightRotate(node);
		}
		// RR Case
		if (factor < -1 && data < node.right.data)
		{
			node.right = this.rightRotate(node.right);
			return this.leftRotate(node);
		}
		return node;
	}
	// Print the tree in preorder form
	public void preorder(TreeNode node)
	{
		if (node != null)
		{
			Console.Write("  " + node.data);
			this.preorder(node.left);
			this.preorder(node.right);
		}
	}
	// Print the tree in inorder form
	public void inorder(TreeNode node)
	{
		if (node != null)
		{
			this.inorder(node.left);
			Console.Write("  " + node.data);
			this.inorder(node.right);
		}
	}
	// Print the tree in postorder form
	public void postorder(TreeNode node)
	{
		if (node != null)
		{
			this.postorder(node.left);
			this.postorder(node.right);
			Console.Write("  " + node.data);
		}
	}
	public static void Main(String[] args)
	{
		var tree = new AvlTree();
		// Add tree node
		tree.root = tree.addNode(tree.root, 4);
		tree.root = tree.addNode(tree.root, 7);
		tree.root = tree.addNode(tree.root, 5);
		tree.root = tree.addNode(tree.root, 19);
		tree.root = tree.addNode(tree.root, 17);
		tree.root = tree.addNode(tree.root, 13);
		tree.root = tree.addNode(tree.root, 11);
		tree.root = tree.addNode(tree.root, 3);
		tree.root = tree.addNode(tree.root, 2);
		tree.root = tree.addNode(tree.root, -3);
		/*
		  Resultant  AVL Tree
		  -----------------
		         7
		        /  \ 
		       /    \
		      4      17
		     / \     / \
		    2   5  13  19
		   / \     /
		 -3   3   11
		*/
		Console.Write("Resultant AVL Tree");
		Console.Write("\nPreorder  :");
		tree.preorder(tree.root);
		Console.Write("\nInorder   :");
		tree.inorder(tree.root);
		Console.Write("\nPostorder :");
		tree.postorder(tree.root);
	}
}

Output

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


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