Avl tree node insertion in php

Php program for Avl tree node insertion. Here problem description and other solutions.

<?php
// Php program
// AVL Tree insertion

// Avl Tree Node
class TreeNode
{
	public $data;
	public $height;
	public $left;
	public $right;
	public	function __construct($data)
	{
		// Set node value of avl tree
		$this->data = $data;
		$this->height = 1;
		$this->left = NULL;
		$this->right = NULL;
	}
}
class AvlTree
{
	// Tree root node
	public $root;
	public	function __construct()
	{
		$this->root = NULL;
	}
	// Get the height of given node
	public	function getHeight($node)
	{
		if ($node == NULL)
		{
			return 0;
		}
		return $node->height;
	}
	// Get the max value of given two numbers
	public	function maxHeight($a, $b)
	{
		if ($a > $b)
		{
			return $a;
		}
		else
		{
			return $b;
		}
	}
	// Perform the Right rotate operation
	public	function rightRotate($node)
	{
		// Get left child node
		$leftNode = $node->left;
		// Get left node right subtree
		$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	function leftRotate($node)
	{
		// Get right child node
		$rightNode = $node->right;
		// Get right node left subtree
		$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	function getBalanceFactor($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	function addNode($node, $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
		$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	function preorder($node)
	{
		if ($node != NULL)
		{
			printf("%d  ",$node->data);
			$this->preorder($node->left);
			$this->preorder($node->right);
		}
	}
	// Print the tree in inorder form
	public	function inorder($node)
	{
		if ($node != NULL)
		{
			$this->inorder($node->left);
			printf("%d  ",$node->data);
			$this->inorder($node->right);
		}
	}
	// Print the tree in postorder form
	public	function postorder($node)
	{
		if ($node != NULL)
		{
			$this->postorder($node->left);
			$this->postorder($node->right);
			printf("%d  ",$node->data);
		}
	}
	public static
	function main($args)
	{
		$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
		*/
		printf("Resultant AVL Tree");
		printf("\nPreorder  : ");
		$tree->preorder($tree->root);
		printf("\nInorder   : ");
		$tree->inorder($tree->root);
		printf("\nPostorder : ");
		$tree->postorder($tree->root);
	}
}

AvlTree::main(array());

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