Avl tree node insertion in swift

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

import Foundation
// Swift 4 program
// AVL Tree insertion

// Avl Tree Node
class TreeNode
{
	var data: Int;
	var height: Int;
	var left: TreeNode? ;
	var right: TreeNode? ;
	init(_ data: Int)
	{
		// Set node value of avl tree
		self.data = data;
		self.height = 1;
		self.left = nil;
		self.right = nil;
	}
}
class AvlTree
{
	// Tree root node
	var root: TreeNode? ;
	init()
	{
		self.root = nil;
	}
	// Get the height of given node
	func getHeight(_ node: TreeNode? ) -> Int
	{
		if (node == nil)
		{
			return 0;
		}
		return node!.height;
	}
	// Get the max value of given two numbers
	func maxHeight(_ a: Int, _ b: Int) -> Int
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Perform the Right rotate operation
	func rightRotate(_ node: TreeNode? ) -> TreeNode?
	{
		// Get left child node
		let leftNode: TreeNode? = node!.left;
		// Get left node right subtree
		let rightSubtree: TreeNode? = leftNode!.right;
		// Update the left and right subtree
		leftNode!.right = node;
		node!.left = rightSubtree;
		// Change the height of modified node
		node!.height = self.maxHeight(
      self.getHeight(node!.left), self.getHeight(node!.right)) + 1;
		leftNode!.height = self.maxHeight(
          self.getHeight(leftNode!.left), 
          self.getHeight(leftNode!.right)) + 1;
		return leftNode;
	}
	// Perform the Left Rotate operation
	func leftRotate(_ node: TreeNode? ) -> TreeNode?
	{
		// Get right child node
		let rightNode: TreeNode? = node!.right;
		// Get right node left subtree
		let leftSubtree: TreeNode? = rightNode!.left;
		// Update the left and right subtree
		rightNode!.left = node;
		node!.right = leftSubtree;
		// Change the height of modified node
		node!.height = self.maxHeight(
      self.getHeight(node!.left), self.getHeight(node!.right)) + 1;
		rightNode!.height = self.maxHeight(
          self.getHeight(rightNode!.left), 
          self.getHeight(rightNode!.right)) + 1;
		return rightNode;
	}
	// Get the balance factor
	func getBalanceFactor(_ node: TreeNode? ) -> Int
	{
		if (node == nil)
		{
			return 0;
		}
		return self.getHeight(node!.left) - 
          self.getHeight(node!.right);
	}
	// Recursively, add a node in AVL tree
	// Duplicate keys (data) are not allowed
	func addNode(_ node: TreeNode? , _ data : Int) -> TreeNode?
	{
		if (node == nil)
		{
			// Return a new node
			return TreeNode(data);
		}
		if (data < node!.data)
		{
			node!.left = self.addNode(node!.left, data);
		}
		else if (data > node!.data)
		{
			node!.right = self.addNode(node!.right, data);
		}
		else
		{
			// When given key data already exists
			return node;
		}
		// Change the height of current node
		node!.height = 1 + self.maxHeight(
          self.getHeight(node!.left), self.getHeight(node!.right));
		// Get balance factor of a node
		let factor: Int = self.getBalanceFactor(node);
		// LL Case
		if (factor > 1 && data < node!.left!.data)
		{
			return self.rightRotate(node);
		}
		// RR Case
		if (factor < -1 && data > node!.right!.data)
		{
			return self.leftRotate(node);
		}
		// LL Case
		if (factor > 1 && data > node!.left!.data)
		{
			node!.left = self.leftRotate(node!.left);
			return self.rightRotate(node);
		}
		// RR Case
		if (factor < -1 && data < node!.right!.data)
		{
			node!.right = self.rightRotate(node!.right);
			return self.leftRotate(node);
		}
		return node;
	}
	// Print the tree in preorder form
	func preorder(_ node: TreeNode? )
	{
		if (node  != nil)
		{
			print("  "
				+ String(node!.data), terminator: "");
			self.preorder(node!.left);
			self.preorder(node!.right);
		}
	}
	// Print the tree in inorder form
	func inorder(_ node: TreeNode? )
	{
		if (node  != nil)
		{
			self.inorder(node!.left);
			print("",node!.data, terminator: " ");
			self.inorder(node!.right);
		}
	}
	// Print the tree in postorder form
	func postorder(_ node: TreeNode? )
	{
		if (node  != nil)
		{
			self.postorder(node!.left);
			self.postorder(node!.right);
			print("",node!.data, terminator: " ");
		}
	}
	static func main(_ args: [String])
	{
		let tree: AvlTree? = 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
		*/
		print("Resultant AVL Tree");
		print("Preorder  :", terminator: "");
		tree!.preorder(tree!.root);
		print("\nInorder   :", terminator: "");
		tree!.inorder(tree!.root);
		print("\nPostorder :", terminator: "");
		tree!.postorder(tree!.root);
	}
}
AvlTree.main([String]());

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