Sort array with repeated element using AVL Tree

Here given code implementation process.

/*
    C program for
    Sort array with repeated element using AVL Tree
*/
#include <stdio.h>
#include <stdlib.h>

// Avl tree node
struct TreeNode
{
	// Data value of tree
	int key;
	// Used to hold the height of current node
	int height;
	// Count occurrence nodes
	int occurrence;
	// Indicate left and right subtree
	struct TreeNode *left;
	struct TreeNode *right;
};
struct AVLTree
{
	struct TreeNode *root;
};
// Create new tree
struct AVLTree *newTree()
{
	// Create dynamic node
	struct AVLTree *tree = (struct AVLTree *)
	malloc(sizeof(struct AVLTree));
	if (tree != NULL)
	{
		tree->root = NULL;
	}
	else
	{
		printf("Memory Overflow to Create Tree\n");
	}
	// Return new tree
	return tree;
}
// Get the height of given node
int height(struct TreeNode *node)
{
	if (node == NULL)
	{
		return 0;
	}
	return node->height;
}
// Get the max value of given two numbers
int maxHeight(int a, int b)
{
	if (a > b)
	{
		return a;
	}
	else
	{
		return b;
	}
}
// Create a new Avl Tree node
struct TreeNode *newTreeNode(int key)
{
	// Create a tree node
	struct TreeNode *node = (struct TreeNode *) 
  							malloc(sizeof(struct TreeNode));
	if (node != NULL)
	{
		// Set initial node values
		node->key = key;
		node->height = 1;
		node->left = NULL;
		node->right = NULL;
		node->occurrence = 1;
	}
	else
	{
		printf("\nMemory overflow");
	}
	return node;
}
// Perform the Right rotate operation
struct TreeNode *rightRotate(struct TreeNode *node)
{
	// Get left child node
	struct TreeNode *left_node = node->left;
	// Get left node right subtree
	struct TreeNode *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 = maxHeight(height(node->left), 
                             height(node->right)) + 1;
	left_node->height = maxHeight(height(left_node->left), 
                                  height(left_node->right)) + 1;
	return left_node;
}
// Perform the Left Rotate operation
struct TreeNode *left_rotate(struct TreeNode *node)
{
	// Get right child node
	struct TreeNode *right_node = node->right;
	// Get right node left subtree
	struct TreeNode *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 = maxHeight(height(node->left), 
                             height(node->right)) + 1;
	right_node->height = maxHeight(height(right_node->left), 
                                   height(right_node->right)) + 1;
	return right_node;
}
// Get the balance factor
int getBalanceFactor(struct TreeNode *node)
{
	if (node == NULL)
	{
		return 0;
	}
	return height(node->left) - height(node->right);
}
// Recursively, add a node in AVL tree
// Duplicate keys (key) are allowed
struct TreeNode *addElement(struct TreeNode *node, int key)
{
	if (node == NULL)
	{
		// return a new node
		return newTreeNode(key);
	}
	if (key < node->key)
	{
		node->left = addElement(node->left, key);
	}
	else if (key > node->key)
	{
		node->right = addElement(node->right, key);
	}
	else
	{
		node->occurrence = node->occurrence + 1;
		// When given key key already exists
		return node;
	}
	// Change the height of current node
	node->height = 1 + maxHeight(height(node->left), 
                                 height(node->right));
	// Get balance factor of a node
	int balance_factor = getBalanceFactor(node);
	// RR Case
	if (balance_factor > 1 && key < node->left->key)
	{
		return rightRotate(node);
	}
	// LL Case 
	if (balance_factor < -1 && key > node->right->key)
	{
		return left_rotate(node);
	}
	// LR Case
	if (balance_factor > 1 && key > node->left->key)
	{
		node->left = left_rotate(node->left);
		return rightRotate(node);
	}
	// RL Case 
	if (balance_factor < -1 && key < node->right->key)
	{
		node->right = rightRotate(node->right);
		return left_rotate(node);
	}
	return node;
}
// Display given array elements
void printRecord(int arr[], int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("  %d", arr[i]);
	}
}
// Collect sorted elements
void sortedElements(struct TreeNode *node, int arr[], int *index)
{
	if (node != NULL)
	{
      	// Visit left subtree
		sortedElements(node->left, arr, index);
		int i = 0;
		
		while (i < node->occurrence)
		{
			arr[ *index] = node->key;
            *index = *index + 1;
			i++;
		}
      	// Visit right subtree
		sortedElements(node->right, arr, index);
	}
}
void sort(int arr[], int n)
{
	// New Tree
	struct AVLTree *tree = newTree();
	for (int i = 0; i < n; ++i)
	{
		tree->root = addElement(tree->root, arr[i]);
	}
	int index = 0;
	sortedElements(tree->root, arr, & index);
}
int main(int argc, char const *argv[])
{
	// Array of integer elements
	int arr[] = {
		6 , 2 , 6 , 2 , 4 , 6 , 3 , 6 , 
        2 , 2 , 8 , 9 , 3 , 6 , 8 , 9
	};
	// Get the number of elements
	int n = sizeof(arr) / sizeof(arr[0]);
	sort(arr, n);
	printRecord(arr, n);
	return 0;
}

Output

  2  2  2  2  3  3  4  6  6  6  6  6  8  8  9  9
// Java program
// Sort array with repeated element using AVL tree

//Avl tree node
class TreeNode
{
    public int key;
    public int height;
    public int occurrence;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int key)
    {
        //Set node value of avl tree
        this.key = key;
        this.height = 1;
        this.occurrence = 1;
        this.left = null;
        this.right = null;
    }
}
class AvlTree
{
    public TreeNode root;
    public AvlTree()
    {
        this.root = null;
    }
    //Get the height of given node
    public int height(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
        TreeNode left_node = node.left;
        //Get left node right subtree
        TreeNode 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 = maxHeight(height(node.left), 
            height(node.right)) + 1;
        left_node.height = maxHeight(height(left_node.left), 
            height(left_node.right)) + 1;
        return left_node;
    }
    // Perform the Left Rotate operation
    public TreeNode leftRotate(TreeNode node)
    {
        // Get right child node
        TreeNode right_node = node.right;
        //Get right node left subtree
        TreeNode 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 = maxHeight(height(node.left), 
            height(node.right)) + 1;
        right_node.height = maxHeight(height(right_node.left), 
            height(right_node.right)) + 1;
        return right_node;
    }
    // Get the balance factor
    public int getBalanceFactor(TreeNode node)
    {
        if (node == null)
        {
            return 0;
        }
        return height(node.left) - height(node.right);
    }
    // Recursively, add a node in AVL tree with
    // Duplicate keys are allowed
    public TreeNode addTreeNode(TreeNode node, int key)
    {
        if (node == null)
        {
            //return a new node
            return new TreeNode(key);
        }
        if (key < node.key)
        {
            node.left = addTreeNode(node.left, key);
        }
        else if (key > node.key)
        {
            node.right = addTreeNode(node.right, key);
        }
        else
        {
            //When given key already exists
            node.occurrence = node.occurrence + 1;
            return node;
        }
        // Change the height of current node
        node.height = 1 + maxHeight(height(node.left), 
                                    height(node.right));
        //Get balance factor of a node
        int balance_factor = getBalanceFactor(node);
        if (balance_factor > 1 && key < node.left.key)
        {
            return rightRotate(node);
        }
        if (balance_factor < -1 && key > node.right.key)
        {
            return leftRotate(node);
        }
        if (balance_factor > 1 && key > node.left.key)
        {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
        if (balance_factor < -1 && key < node.right.key)
        {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
        return node;
    }
}

public class SortArray
{
  	public int index;
  	public SortArray()
    {
      this.index = 0;
    }
    // Display given array elements
    public void printRecord(int[] arr, int n)
    {
        for (int i = 0; i < n; ++i)
        {
            System.out.print(" " + arr[i] );
        }
    }
    // Collect sorted elements
    public void sortedElements(TreeNode node, int[] arr)
    {
        if (node != null)
        {
            // Visit left subtree
            sortedElements(node.left, arr);
            int i = 0;
            while (i < node.occurrence)
            {
                arr[this.index] = node.key;
                this.index = this.index + 1;
                i++;
            }
            // Visit right subtree
            sortedElements(node.right, arr);
        }
    }
    public void sort(int[] arr, int n)
    {
        // New Tree
        AvlTree tree = new AvlTree();
        for (int i = 0; i < n; ++i)
        {
            tree.root = tree.addTreeNode(tree.root, arr[i]);
        }
        this.index = 0;
        sortedElements(tree.root, arr);
    }

    public static void main(String[] args)
    {
        SortArray task = new SortArray();
        // Array of integer elements
        int[] arr =  {
            6 , 2 , 6 , 2 , 4 , 6 , 3 , 6 , 2 , 
            2 , 8 , 9 , 3 , 6 , 8 , 9
        };
        // Get the number of elements
        int n = arr.length;
        task.sort(arr, n);
        task.printRecord(arr, n);
    }
}

Output

 2 2 2 2 3 3 4 6 6 6 6 6 8 8 9 9
// Include header file
#include <iostream>
using namespace std;
// C++ program
// Sort array with repeated element using AVL tree

//Avl tree node
class TreeNode
{
	public: int key;
	int height;
	int occurrence;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int key)
	{
		//Set node value of avl tree
		this->key = key;
		this->height = 1;
		this->occurrence = 1;
		this->left = NULL;
		this->right = NULL;
	}
};
class AvlTree
{
	public: TreeNode *root;
	AvlTree()
	{
		this->root = NULL;
	}
	//Get the height of given node
	int height(TreeNode *node)
	{
		if (node == NULL)
		{
			return 0;
		}
		return node->height;
	}
	//Get the max value of given two numbers
	int maxHeight(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Perform the Right rotate operation
	TreeNode *rightRotate(TreeNode *node)
	{
		//Get left child node
		TreeNode *left_node = node->left;
		//Get left node right subtree
		TreeNode *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->maxHeight(
          this->height(node->left), 
          this->height(node->right)) + 1;
		left_node->height = this->maxHeight
        (this->height(left_node->left), 
         this->height(left_node->right)) + 1;
		return left_node;
	}
	// Perform the Left Rotate operation
	TreeNode *leftRotate(TreeNode *node)
	{
		// Get right child node
		TreeNode *right_node = node->right;
		//Get right node left subtree
		TreeNode *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->maxHeight(
          this->height(node->left), 
          this->height(node->right)) + 1;
		right_node->height = this->maxHeight(
          this->height(right_node->left), 
          this->height(right_node->right)) + 1;
		return right_node;
	}
	// Get the balance factor
	int getBalanceFactor(TreeNode *node)
	{
		if (node == NULL)
		{
			return 0;
		}
		return this->height(node->left) - this->height(node->right);
	}
	// Recursively, add a node in AVL tree with
	// Duplicate keys are allowed
	TreeNode *addTreeNode(TreeNode *node, int key)
	{
		if (node == NULL)
		{
			//return a new node
			return new TreeNode(key);
		}
		if (key < node->key)
		{
			node->left = this->addTreeNode(node->left, key);
		}
		else if (key > node->key)
		{
			node->right = this->addTreeNode(node->right, key);
		}
		else
		{
			//When given key already exists
			node->occurrence = node->occurrence + 1;
			return node;
		}
		// Change the height of current node
		node->height = 1 + this->maxHeight(
          this->height(node->left), this->height(node->right));
		//Get balance factor of a node
		int balance_factor = this->getBalanceFactor(node);
		if (balance_factor > 1 && key < node->left->key)
		{
			return this->rightRotate(node);
		}
		if (balance_factor < -1 && key > node->right->key)
		{
			return this->leftRotate(node);
		}
		if (balance_factor > 1 && key > node->left->key)
		{
			node->left = this->leftRotate(node->left);
			return this->rightRotate(node);
		}
		if (balance_factor < -1 && key < node->right->key)
		{
			node->right = this->rightRotate(node->right);
			return this->leftRotate(node);
		}
		return node;
	}
};
class SortArray
{
	public: int index;
	SortArray()
	{
		this->index = 0;
	}
	// Display given array elements
	void printRecord(int arr[], int n)
	{
		for (int i = 0; i < n; ++i)
		{
			cout << " " << arr[i];
		}
	}
	// Collect sorted elements
	void sortedElements(TreeNode *node, int arr[])
	{
		if (node != NULL)
		{
			// Visit left subtree
			this->sortedElements(node->left, arr);
			int i = 0;
			while (i < node->occurrence)
			{
				arr[this->index] = node->key;
				this->index = this->index + 1;
				i++;
			}
			// Visit right subtree
			this->sortedElements(node->right, arr);
		}
	}
	void sort(int arr[], int n)
	{
		// New Tree
		AvlTree *tree = new AvlTree();
		for (int i = 0; i < n; ++i)
		{
			tree->root = tree->addTreeNode(tree->root, arr[i]);
		}
		this->index = 0;
		this->sortedElements(tree->root, arr);
	}
};
int main()
{
	SortArray *task = new SortArray();
	// Array of integer elements
	int arr[] = {
		6 , 2 , 6 , 2 , 4 , 6 , 3 , 6 , 2 , 2 , 8 , 9 , 3 , 6 , 8 , 9
	};
	// Get the number of elements
	int n = sizeof(arr) / sizeof(arr[0]);
	task->sort(arr, n);
	task->printRecord(arr, n);
	return 0;
}

Output

 2 2 2 2 3 3 4 6 6 6 6 6 8 8 9 9
// Include namespace system
using System;
// Csharp program
// Sort array with repeated element using AVL tree

//Avl tree node
public class TreeNode
{
	public int key;
	public int height;
	public int occurrence;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int key)
	{
		//Set node value of avl tree
		this.key = key;
		this.height = 1;
		this.occurrence = 1;
		this.left = null;
		this.right = null;
	}
}
public class AvlTree
{
	public TreeNode root;
	public AvlTree()
	{
		this.root = null;
	}
	//Get the height of given node
	public int height(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
		TreeNode left_node = node.left;
		//Get left node right subtree
		TreeNode 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.maxHeight(
          this.height(node.left), 
          this.height(node.right)) + 1;
		left_node.height = this.maxHeight(
          this.height(left_node.left), 
          this.height(left_node.right)) + 1;
		return left_node;
	}
	// Perform the Left Rotate operation
	public TreeNode leftRotate(TreeNode node)
	{
		// Get right child node
		TreeNode right_node = node.right;
		//Get right node left subtree
		TreeNode 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.maxHeight(
          this.height(node.left), 
          this.height(node.right)) + 1;
		right_node.height = this.maxHeight(
          this.height(right_node.left), 
          this.height(right_node.right)) + 1;
		return right_node;
	}
	// Get the balance factor
	public int getBalanceFactor(TreeNode node)
	{
		if (node == null)
		{
			return 0;
		}
		return this.height(node.left) - this.height(node.right);
	}
	// Recursively, add a node in AVL tree with
	// Duplicate keys are allowed
	public TreeNode addTreeNode(TreeNode node, int key)
	{
		if (node == null)
		{
			//return a new node
			return new TreeNode(key);
		}
		if (key < node.key)
		{
			node.left = this.addTreeNode(node.left, key);
		}
		else if (key > node.key)
		{
			node.right = this.addTreeNode(node.right, key);
		}
		else
		{
			//When given key already exists
			node.occurrence = node.occurrence + 1;
			return node;
		}
		// Change the height of current node
		node.height = 1 + this.maxHeight(
          this.height(node.left), 
          this.height(node.right));
		//Get balance factor of a node
		int balance_factor = this.getBalanceFactor(node);
		if (balance_factor > 1 && key < node.left.key)
		{
			return this.rightRotate(node);
		}
		if (balance_factor < -1 && key > node.right.key)
		{
			return this.leftRotate(node);
		}
		if (balance_factor > 1 && key > node.left.key)
		{
			node.left = this.leftRotate(node.left);
			return this.rightRotate(node);
		}
		if (balance_factor < -1 && key < node.right.key)
		{
			node.right = this.rightRotate(node.right);
			return this.leftRotate(node);
		}
		return node;
	}
}
public class SortArray
{
	public int index;
	public SortArray()
	{
		this.index = 0;
	}
	// Display given array elements
	public void printRecord(int[] arr, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			Console.Write(" " + arr[i]);
		}
	}
	// Collect sorted elements
	public void sortedElements(TreeNode node, int[] arr)
	{
		if (node != null)
		{
			// Visit left subtree
			this.sortedElements(node.left, arr);
			int i = 0;
			while (i < node.occurrence)
			{
				arr[this.index] = node.key;
				this.index = this.index + 1;
				i++;
			}
			// Visit right subtree
			this.sortedElements(node.right, arr);
		}
	}
	public void sort(int[] arr, int n)
	{
		// New Tree
		AvlTree tree = new AvlTree();
		for (int i = 0; i < n; ++i)
		{
			tree.root = tree.addTreeNode(tree.root, arr[i]);
		}
		this.index = 0;
		this.sortedElements(tree.root, arr);
	}
	public static void Main(String[] args)
	{
		SortArray task = new SortArray();
		// Array of integer elements
		int[] arr = {
			6 , 2 , 6 , 2 , 4 , 6 , 3 , 6 , 2 , 
            2 , 8 , 9 , 3 , 6 , 8 , 9
		};
		// Get the number of elements
		int n = arr.Length;
		task.sort(arr, n);
		task.printRecord(arr, n);
	}
}

Output

 2 2 2 2 3 3 4 6 6 6 6 6 8 8 9 9
package main
import "fmt"
// Go program
// Sort array with repeated element using AVL tree

// Avl tree node
type TreeNode struct {
	key int
	height int
	occurrence int
	left * TreeNode
	right * TreeNode
}
func getTreeNode(key int) * TreeNode {
	var me *TreeNode = &TreeNode {}
	//Set node value of avl tree
	me.key = key
	me.height = 1
	me.occurrence = 1
	me.left = nil
	me.right = nil
	return me
}
type AvlTree struct {
	root * TreeNode
}
func getAvlTree() * AvlTree {
	var me *AvlTree = &AvlTree {}
	me.root = nil
	return me
}
//Get the height of given node
func(this AvlTree) height(node * TreeNode) int {
	if node == nil {
		return 0
	}
	return node.height
}
//Get the max value of given two numbers
func(this AvlTree) maxHeight(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}
// Perform the Right rotate operation
func(this *AvlTree) rightRotate(node * TreeNode) * TreeNode {
	//Get left child node
	var left_node * TreeNode = node.left
	//Get left node right subtree
	var right_subtree * TreeNode = 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.maxHeight(
		this.height(node.left), this.height(node.right)) + 1
	left_node.height = this.maxHeight(
		this.height(left_node.left), this.height(left_node.right)) + 1
	return left_node
}
// Perform the Left Rotate operation
func(this *AvlTree) leftRotate(node * TreeNode) * TreeNode {
	// Get right child node
	var right_node * TreeNode = node.right
	//Get right node left subtree
	var left_subtree * TreeNode = 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.maxHeight(
		this.height(node.left), this.height(node.right)) + 1
	right_node.height = this.maxHeight(
		this.height(right_node.left), this.height(right_node.right)) + 1
	return right_node
}
// Get the balance factor
func(this AvlTree) getBalanceFactor(node * TreeNode) int {
	if node == nil {
		return 0
	}
	return this.height(node.left) - this.height(node.right)
}
// Recursively, add a node in AVL tree with
// Duplicate keys are allowed
func(this *AvlTree) addTreeNode(node * TreeNode, key int) * TreeNode {
	if node == nil {
		//return a new node
		return getTreeNode(key)
	}
	if key < node.key {
		node.left = this.addTreeNode(node.left, key)
	} else if key > node.key {
		node.right = this.addTreeNode(node.right, key)
	} else {
		//When given key already exists
		node.occurrence = node.occurrence + 1
		return node
	}
	// Change the height of current node
	node.height = 1 + this.maxHeight(this.height(node.left), 
		this.height(node.right))
	//Get balance factor of a node
	var balance_factor int = this.getBalanceFactor(node)
	if balance_factor > 1 && key < node.left.key {
		return this.rightRotate(node)
	}
	if balance_factor < -1 && key > node.right.key {
		return this.leftRotate(node)
	}
	if balance_factor > 1 && key > node.left.key {
		node.left = this.leftRotate(node.left)
		return this.rightRotate(node)
	}
	if balance_factor < -1 && key < node.right.key {
		node.right = this.rightRotate(node.right)
		return this.leftRotate(node)
	}
	return node
}
type SortArray struct {
	index int
}
func getSortArray() * SortArray {
	var me *SortArray = &SortArray {}
	me.index = 0
	return me
}
// Display given array elements
func(this SortArray) printRecord(arr[] int, n int) {
	for i := 0 ; i < n ; i++ {
		fmt.Print(" ", arr[i])
	}
}
// Collect sorted elements
func(this *SortArray) sortedElements(node * TreeNode, arr[] int) {
	if node != nil {
		// Visit left subtree
		this.sortedElements(node.left, arr)
		var i int = 0
		for (i < node.occurrence) {
			arr[this.index] = node.key
			this.index = this.index + 1
			i++
		}
		// Visit right subtree
		this.sortedElements(node.right, arr)
	}
}
func(this *SortArray) sort(arr[] int, n int) {
	// New Tree
	var tree * AvlTree = getAvlTree()
	for i := 0 ; i < n ; i++ {
		tree.root = tree.addTreeNode(tree.root, arr[i])
	}
	this.index = 0
	this.sortedElements(tree.root, arr)
}
func main() {
	var task * SortArray = getSortArray()
	// Array of integer elements
	var arr = [] int {6 , 2 , 6 , 2 , 4 , 6 , 3 , 
		6 , 2 , 2 , 8 , 9 , 3 , 6 , 8 , 9}
	// Get the number of elements
	var n int = len(arr)
	task.sort(arr, n)
	task.printRecord(arr, n)
}

Output

 2 2 2 2 3 3 4 6 6 6 6 6 8 8 9 9
<?php
// Php program
// Sort array with repeated element using AVL tree
//Avl tree node
class TreeNode
{
	public $key;
	public $height;
	public $occurrence;
	public $left;
	public $right;
	public	function __construct($key)
	{
		//Set node value of avl tree
		$this->key = $key;
		$this->height = 1;
		$this->occurrence = 1;
		$this->left = NULL;
		$this->right = NULL;
	}
}
class AvlTree
{
	public $root;
	public	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 maxHeight($a, $b)
	{
		if ($a > $b)
		{
			return $a;
		}
		else
		{
			return $b;
		}
	}
	// Perform the Right rotate operation
	public	function rightRotate($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->maxHeight(
          $this->height($node->left), 
          $this->height($node->right)) + 1;
		$left_node->height = $this->maxHeight(
          $this->height($left_node->left), 
          $this->height($left_node->right)) + 1;
		return $left_node;
	}
	// Perform the Left Rotate operation
	public	function leftRotate($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->maxHeight(
          $this->height($node->left), 
          $this->height($node->right)) + 1;
		$right_node->height = $this->maxHeight(
          $this->height($right_node->left), 
          $this->height($right_node->right)) + 1;
		return $right_node;
	}
	// Get the balance factor
	public	function getBalanceFactor($node)
	{
		if ($node == NULL)
		{
			return 0;
		}
		return $this->height($node->left) - $this->height($node->right);
	}
	// Recursively, add a node in AVL tree with
	// Duplicate keys are allowed
	public	function addTreeNode($node, $key)
	{
		if ($node == NULL)
		{
			//return a new node
			return new TreeNode($key);
		}
		if ($key < $node->key)
		{
			$node->left = $this->addTreeNode($node->left, $key);
		}
		else if ($key > $node->key)
		{
			$node->right = $this->addTreeNode($node->right, $key);
		}
		else
		{
			//When given key already exists
			$node->occurrence = $node->occurrence + 1;
			return $node;
		}
		// Change the height of current node
		$node->height = 1 + $this->maxHeight(
          $this->height($node->left), 
          $this->height($node->right));
		//Get balance factor of a node
		$balance_factor = $this->getBalanceFactor($node);
		if ($balance_factor > 1 && $key < $node->left->key)
		{
			return $this->rightRotate($node);
		}
		if ($balance_factor < -1 && $key > $node->right->key)
		{
			return $this->leftRotate($node);
		}
		if ($balance_factor > 1 && $key > $node->left->key)
		{
			$node->left = $this->leftRotate($node->left);
			return $this->rightRotate($node);
		}
		if ($balance_factor < -1 && $key < $node->right->key)
		{
			$node->right = $this->rightRotate($node->right);
			return $this->leftRotate($node);
		}
		return $node;
	}
}
class SortArray
{
	public $index;
	public	function __construct()
	{
		$this->index = 0;
	}
	// Display given array elements
	public	function printRecord($arr, $n)
	{
		for ($i = 0; $i < $n; ++$i)
		{
			echo(" ".$arr[$i]);
		}
	}
	// Collect sorted elements
	public	function sortedElements($node, &$arr)
	{
		if ($node != NULL)
		{
			// Visit left subtree
			$this->sortedElements($node->left, $arr);
			$i = 0;
			while ($i < $node->occurrence)
			{
				$arr[$this->index] = $node->key;
				$this->index = $this->index + 1;
				$i++;
			}
			// Visit right subtree
			$this->sortedElements($node->right, $arr);
		}
	}
	public	function sort(&$arr, $n)
	{
		// New Tree
		$tree = new AvlTree();
		for ($i = 0; $i < $n; ++$i)
		{
			$tree->root = $tree->addTreeNode($tree->root, $arr[$i]);
		}
		$this->index = 0;
		$this->sortedElements($tree->root, $arr);
	}
}

function main()
{
	$task = new SortArray();
	// Array of integer elements
	$arr = array(6, 2, 6, 2, 4, 6, 3, 6, 2, 2, 8, 9, 3, 6, 8, 9);
	// Get the number of elements
	$n = count($arr);
	$task->sort($arr, $n);
	$task->printRecord($arr, $n);
}
main();

Output

 2 2 2 2 3 3 4 6 6 6 6 6 8 8 9 9
// Node JS program
// Sort array with repeated element using AVL tree

// Avl tree node
class TreeNode
{
	constructor(key)
	{
		//Set node value of avl tree
		this.key = key;
		this.height = 1;
		this.occurrence = 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
	maxHeight(a, b)
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Perform the Right rotate operation
	rightRotate(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.maxHeight(
          this.height(node.left), 
          this.height(node.right)) + 1;
		left_node.height = this.maxHeight(
          this.height(left_node.left), 
          this.height(left_node.right)) + 1;
		return left_node;
	}
	// Perform the Left Rotate operation
	leftRotate(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.maxHeight(
          this.height(node.left), 
          this.height(node.right)) + 1;
		right_node.height = this.maxHeight(
          this.height(right_node.left), 
          this.height(right_node.right)) + 1;
		return right_node;
	}
	// Get the balance factor
	getBalanceFactor(node)
	{
		if (node == null)
		{
			return 0;
		}
		return this.height(node.left) - this.height(node.right);
	}
	// Recursively, add a node in AVL tree with
	// Duplicate keys are allowed
	addTreeNode(node, key)
	{
		if (node == null)
		{
			//return a new node
			return new TreeNode(key);
		}
		if (key < node.key)
		{
			node.left = this.addTreeNode(node.left, key);
		}
		else if (key > node.key)
		{
			node.right = this.addTreeNode(node.right, key);
		}
		else
		{
			//When given key already exists
			node.occurrence = node.occurrence + 1;
			return node;
		}
		// Change the height of current node
		node.height = 1 + this.maxHeight(
          this.height(node.left), 
          this.height(node.right));
		//Get balance factor of a node
		var balance_factor = this.getBalanceFactor(node);
		if (balance_factor > 1 && key < node.left.key)
		{
			return this.rightRotate(node);
		}
		if (balance_factor < -1 && key > node.right.key)
		{
			return this.leftRotate(node);
		}
		if (balance_factor > 1 && key > node.left.key)
		{
			node.left = this.leftRotate(node.left);
			return this.rightRotate(node);
		}
		if (balance_factor < -1 && key < node.right.key)
		{
			node.right = this.rightRotate(node.right);
			return this.leftRotate(node);
		}
		return node;
	}
}
class SortArray
{
	constructor()
	{
		this.index = 0;
	}
	// Display given array elements
	printRecord(arr, n)
	{
		for (var i = 0; i < n; ++i)
		{
			process.stdout.write(" " + arr[i]);
		}
	}
	// Collect sorted elements
	sortedElements(node, arr)
	{
		if (node != null)
		{
			// Visit left subtree
			this.sortedElements(node.left, arr);
			var i = 0;
			while (i < node.occurrence)
			{
				arr[this.index] = node.key;
				this.index = this.index + 1;
				i++;
			}
			// Visit right subtree
			this.sortedElements(node.right, arr);
		}
	}
	sort(arr, n)
	{
		// New Tree
		var tree = new AvlTree();
		for (var i = 0; i < n; ++i)
		{
			tree.root = tree.addTreeNode(tree.root, arr[i]);
		}
		this.index = 0;
		this.sortedElements(tree.root, arr);
	}
}

function main()
{
	var task = new SortArray();
	// Array of integer elements
	var arr = [6, 2, 6, 2, 4, 6, 3, 6, 2, 2, 8, 9, 3, 6, 8, 9];
	// Get the number of elements
	var n = arr.length;
	task.sort(arr, n);
	task.printRecord(arr, n);
}
main();

Output

 2 2 2 2 3 3 4 6 6 6 6 6 8 8 9 9
#  Python 3 program
#  Sort array with repeated element using AVL tree

# Avl tree node
class TreeNode :
	def __init__(self, key) :
		# Set node value of avl tree
		self.key = key
		self.height = 1
		self.occurrence = 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 maxHeight(self, a, b) :
		if (a > b) :
			return a
		else :
			return b
		
	
	#  Perform the Right rotate operation
	def rightRotate(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.maxHeight(
          self.height(node.left), 
          self.height(node.right)) + 1
		left_node.height = self.maxHeight(
          self.height(left_node.left), 
          self.height(left_node.right)) + 1
		return left_node
	
	#  Perform the Left Rotate operation
	def leftRotate(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.maxHeight(
          self.height(node.left), 
          self.height(node.right)) + 1
		right_node.height = self.maxHeight(
          self.height(right_node.left), 
          self.height(right_node.right)) + 1
		return right_node
	
	#  Get the balance factor
	def getBalanceFactor(self, node) :
		if (node == None) :
			return 0
		
		return self.height(node.left) - self.height(node.right)
	
	#  Recursively, add a node in AVL tree with
	#  Duplicate keys are allowed
	def addTreeNode(self, node, key) :
		if (node == None) :
			# return a new node
			return TreeNode(key)
		
		if (key < node.key) :
			node.left = self.addTreeNode(node.left, key)
		elif (key > node.key) :
			node.right = self.addTreeNode(node.right, key)
		else :
			# When given key already exists
			node.occurrence = node.occurrence + 1
			return node
		
		#  Change the height of current node
		node.height = 1 + self.maxHeight(
          self.height(node.left), self.height(node.right))
		# Get balance factor of a node
		balance_factor = self.getBalanceFactor(node)
		if (balance_factor > 1 and key < node.left.key) :
			return self.rightRotate(node)
		
		if (balance_factor < -1 and key > node.right.key) :
			return self.leftRotate(node)
		
		if (balance_factor > 1 and key > node.left.key) :
			node.left = self.leftRotate(node.left)
			return self.rightRotate(node)
		
		if (balance_factor < -1 and key < node.right.key) :
			node.right = self.rightRotate(node.right)
			return self.leftRotate(node)
		
		return node
	

class SortArray :
	def __init__(self) :
		self.index = 0
	
	#  Display given array elements
	def printRecord(self, arr, n) :
		i = 0
		while (i < n) :
			print(" ", arr[i], end = "")
			i += 1
		
	
	#  Collect sorted elements
	def sortedElements(self, node, arr) :
		if (node != None) :
			#  Visit left subtree
			self.sortedElements(node.left, arr)
			i = 0
			while (i < node.occurrence) :
				arr[self.index] = node.key
				self.index = self.index + 1
				i += 1
			
			#  Visit right subtree
			self.sortedElements(node.right, arr)
		
	
	def sort(self, arr, n) :
		#  New Tree
		tree = AvlTree()
		i = 0
		while (i < n) :
			tree.root = tree.addTreeNode(tree.root, arr[i])
			i += 1
		
		self.index = 0
		self.sortedElements(tree.root, arr)
	

def main() :
	task = SortArray()
	#  Array of integer elements
	arr = [6, 2, 6, 2, 4, 6, 3, 6, 2, 2, 8, 9, 3, 6, 8, 9]
	#  Get the number of elements
	n = len(arr)
	task.sort(arr, n)
	task.printRecord(arr, n)

if __name__ == "__main__": main()

Output

  2  2  2  2  3  3  4  6  6  6  6  6  8  8  9  9
#  Ruby program
#  Sort array with repeated element using AVL tree

# Avl tree node
class TreeNode 
	# Define the accessor and reader of class TreeNode
	attr_reader :key, :height, :occurrence, :left, :right
	attr_accessor :key, :height, :occurrence, :left, :right
	def initialize(key) 
		# Set node value of avl tree
		self.key = key
		self.height = 1
		self.occurrence = 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 maxHeight(a, b) 
		if (a > b) 
			return a
		else
			return b
		end

	end

	#  Perform the Right rotate operation
	def rightRotate(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.maxHeight(
          self.height(node.left), self.height(node.right)) + 1
		left_node.height = self.maxHeight(
          self.height(left_node.left), self.height(left_node.right)) + 1
		return left_node
	end

	#  Perform the Left Rotate operation
	def leftRotate(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.maxHeight(
          self.height(node.left), self.height(node.right)) + 1
		right_node.height = self.maxHeight(
          self.height(right_node.left), self.height(right_node.right)) + 1
		return right_node
	end

	#  Get the balance factor
	def getBalanceFactor(node) 
		if (node == nil) 
			return 0
		end

		return self.height(node.left) - self.height(node.right)
	end

	#  Recursively, add a node in AVL tree with
	#  Duplicate keys are allowed
	def addTreeNode(node, key) 
		if (node == nil) 
			# return a new node
			return TreeNode.new(key)
		end

		if (key < node.key) 
			node.left = self.addTreeNode(node.left, key)
		elsif (key > node.key) 
			node.right = self.addTreeNode(node.right, key)
		else
 
			# When given key already exists
			node.occurrence = node.occurrence + 1
			return node
		end

		#  Change the height of current node
		node.height = 1 + self.maxHeight(
          self.height(node.left), self.height(node.right))
		# Get balance factor of a node
		balance_factor = self.getBalanceFactor(node)
		if (balance_factor > 1 && key < node.left.key) 
			return self.rightRotate(node)
		end

		if (balance_factor < -1 && key > node.right.key) 
			return self.leftRotate(node)
		end

		if (balance_factor > 1 && key > node.left.key) 
			node.left = self.leftRotate(node.left)
			return self.rightRotate(node)
		end

		if (balance_factor < -1 && key < node.right.key) 
			node.right = self.rightRotate(node.right)
			return self.leftRotate(node)
		end

		return node
	end

end

class SortArray 
	# Define the accessor and reader of class SortArray
	attr_reader :index
	attr_accessor :index
	def initialize() 
		self.index = 0
	end

	#  Display given array elements
	def printRecord(arr, n) 
		i = 0
		while (i < n) 
			print(" ", arr[i])
			i += 1
		end

	end

	#  Collect sorted elements
	def sortedElements(node, arr) 
		if (node != nil) 
			#  Visit left subtree
			self.sortedElements(node.left, arr)
			i = 0
			while (i < node.occurrence) 
				arr[self.index] = node.key
				self.index = self.index + 1
				i += 1
			end

			#  Visit right subtree
			self.sortedElements(node.right, arr)
		end

	end

	def sort(arr, n) 
		#  New Tree
		tree = AvlTree.new()
		i = 0
		while (i < n) 
			tree.root = tree.addTreeNode(tree.root, arr[i])
			i += 1
		end

		self.index = 0
		self.sortedElements(tree.root, arr)
	end

end

def main() 
	task = SortArray.new()
	#  Array of integer elements
	arr = [6, 2, 6, 2, 4, 6, 3, 6, 2, 2, 8, 9, 3, 6, 8, 9]
	#  Get the number of elements
	n = arr.length
	task.sort(arr, n)
	task.printRecord(arr, n)
end

main()

Output

 2 2 2 2 3 3 4 6 6 6 6 6 8 8 9 9
// Scala program
// Sort array with repeated element using AVL tree

// Avl tree node
class TreeNode(var key: Int,
	var height: Int,
		var occurrence: Int,
			var left: TreeNode,
				var right: TreeNode)
{
	def this(key: Int)
	{
		// Set node value of avl tree
		this(key, 1, 1, null, null);
	}
}
class AvlTree(var root: TreeNode)
{
	def this()
	{
		this(null);
	}
	//Get the height of given node
	def height(node: TreeNode): Int = {
		if (node == null)
		{
			return 0;
		}
		return node.height;
	}
	//Get the max value of given two numbers
	def maxHeight(a: Int, b: Int): Int = {
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Perform the Right rotate operation
	def rightRotate(node: TreeNode): TreeNode = {
		//Get left child node
		var left_node: TreeNode = node.left;
		//Get left node right subtree
		var right_subtree: TreeNode = 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 = maxHeight(
      		height(node.left), 
          	height(node.right)) + 1;
		left_node.height = maxHeight(
          height(left_node.left), 
          height(left_node.right)) + 1;
		return left_node;
	}
	// Perform the Left Rotate operation
	def leftRotate(node: TreeNode): TreeNode = {
		// Get right child node
		var right_node: TreeNode = node.right;
		//Get right node left subtree
		var left_subtree: TreeNode = 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 = maxHeight(height(node.left), 
          height(node.right)) + 1;
		right_node.height = maxHeight(
          height(right_node.left), 
          height(right_node.right)) + 1;
		return right_node;
	}
	// Get the balance factor
	def getBalanceFactor(node: TreeNode): Int = {
		if (node == null)
		{
			return 0;
		}
		return height(node.left) - height(node.right);
	}
	// Recursively, add a node in AVL tree with
	// Duplicate keys are allowed
	def addTreeNode(node: TreeNode, key: Int): TreeNode = {
		if (node == null)
		{
			//return a new node
			return new TreeNode(key);
		}
		if (key < node.key)
		{
			node.left = addTreeNode(node.left, key);
		}
		else if (key > node.key)
		{
			node.right = addTreeNode(node.right, key);
		}
		else
		{
			//When given key already exists
			node.occurrence = node.occurrence + 1;
			return node;
		}
		// Change the height of current node
		node.height = 1 + maxHeight(
          height(node.left), 
          height(node.right));
		//Get balance factor of a node
		var balance_factor: Int = getBalanceFactor(node);
		if (balance_factor > 1 && key < node.left.key)
		{
			return rightRotate(node);
		}
		if (balance_factor < -1 && key > node.right.key)
		{
			return leftRotate(node);
		}
		if (balance_factor > 1 && key > node.left.key)
		{
			node.left = leftRotate(node.left);
			return rightRotate(node);
		}
		if (balance_factor < -1 && key < node.right.key)
		{
			node.right = rightRotate(node.right);
			return leftRotate(node);
		}
		return node;
	}
}
class SortArray(var index: Int)
{
	def this()
	{
		this(0);
	}
	// Display given array elements
	def printRecord(arr: Array[Int], n: Int): Unit = {
		var i: Int = 0;
		while (i < n)
		{
			print(" " + arr(i));
			i += 1;
		}
	}
	// Collect sorted elements
	def sortedElements(node: TreeNode, arr: Array[Int]): Unit = {
		if (node != null)
		{
			// Visit left subtree
			sortedElements(node.left, arr);
			var i: Int = 0;
			while (i < node.occurrence)
			{
				arr(this.index) = node.key;
				this.index = this.index + 1;
				i += 1;
			}
			// Visit right subtree
			sortedElements(node.right, arr);
		}
	}
	def sort(arr: Array[Int], n: Int): Unit = {
		// New Tree
		var tree: AvlTree = new AvlTree();
		var i: Int = 0;
		while (i < n)
		{
			tree.root = tree.addTreeNode(tree.root, arr(i));
			i += 1;
		}
		this.index = 0;
		sortedElements(tree.root, arr);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: SortArray = new SortArray();
		// Array of integer elements
		var arr: Array[Int] = Array(6, 2, 6, 2, 4, 6, 3, 6, 
                                    2, 2, 8, 9, 3, 6, 8, 9);
		// Get the number of elements
		var n: Int = arr.length;
		task.sort(arr, n);
		task.printRecord(arr, n);
	}
}

Output

 2 2 2 2 3 3 4 6 6 6 6 6 8 8 9 9
import Foundation;
// Swift 4 program
// Sort array with repeated element using AVL tree

// Avl tree node
class TreeNode
{
	var key: Int;
	var height: Int;
	var occurrence: Int;
	var left: TreeNode? ;
	var right: TreeNode? ;
	init(_ key: Int)
	{
		//Set node value of avl tree
		self.key = key;
		self.height = 1;
		self.occurrence = 1;
		self.left = nil;
		self.right = nil;
	}
}
class AvlTree
{
	var root: TreeNode? ;
	init()
	{
		self.root = nil;
	}
	//Get the height of given node
	func height(_ 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 left_node: TreeNode? = node!.left;
		//Get left node right subtree
		let right_subtree: TreeNode? = 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.maxHeight(
      	self.height(node!.left), 
        self.height(node!.right)) + 1;
		left_node!.height = self.maxHeight(
          self.height(left_node!.left), 
          self.height(left_node!.right)) + 1;
		return left_node;
	}
	// Perform the Left Rotate operation
	func leftRotate(_ node: TreeNode? ) -> TreeNode?
	{
		// Get right child node
		let right_node: TreeNode? = node!.right;
		//Get right node left subtree
		let left_subtree: TreeNode? = 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.maxHeight(
      	  self.height(node!.left), 
          self.height(node!.right)) + 1;
		right_node!.height = self.maxHeight(
          self.height(right_node!.left), 
          self.height(right_node!.right)) + 1;
		return right_node;
	}
	// Get the balance factor
	func getBalanceFactor(_ node: TreeNode? ) -> Int
	{
		if (node == nil)
		{
			return 0;
		}
		return self.height(node!.left) - self.height(node!.right);
	}
	// Recursively, add a node in AVL tree with
	// Duplicate keys are allowed
	func addTreeNode(_ node: TreeNode? , _ key : Int) -> TreeNode?
	{
		if (node == nil)
		{
			//return a new node
			return TreeNode(key);
		}
		if (key < node!.key)
		{
			node!.left = self.addTreeNode(node!.left, key);
		}
		else if (key > node!.key)
		{
			node!.right = self.addTreeNode(node!.right, key);
		}
		else
		{
			//When given key already exists
			node!.occurrence = node!.occurrence + 1;
			return node;
		}
		// Change the height of current node
		node!.height = 1 + self.maxHeight(
          self.height(node!.left), 
          self.height(node!.right));
		//Get balance factor of a node
		let balance_factor: Int = self.getBalanceFactor(node);
		if (balance_factor > 1 && key < node!.left!.key)
		{
			return self.rightRotate(node);
		}
		if (balance_factor < -1 && key > node!.right!.key)
		{
			return self.leftRotate(node);
		}
		if (balance_factor > 1 && key > node!.left!.key)
		{
			node!.left = self.leftRotate(node!.left);
			return self.rightRotate(node);
		}
		if (balance_factor < -1 && key < node!.right!.key)
		{
			node!.right = self.rightRotate(node!.right);
			return self.leftRotate(node);
		}
		return node;
	}
}
class SortArray
{
	var index: Int;
	init()
	{
		self.index = 0;
	}
	// Display given array elements
	func printRecord(_ arr: [Int], _ n: Int)
	{
		var i: Int = 0;
		while (i < n)
		{
			print(" ", arr[i], terminator: "");
			i += 1;
		}
	}
	// Collect sorted elements
	func sortedElements(_ node: TreeNode? , _ arr : inout[Int])
	{
		if (node  != nil)
		{
			// Visit left subtree
			self.sortedElements(node!.left, &arr);
			var i: Int = 0;
			while (i < node!.occurrence)
			{
				arr[self.index] = node!.key;
				self.index = self.index + 1;
				i += 1;
			}
			// Visit right subtree
			self.sortedElements(node!.right, &arr);
		}
	}
	func sort(_ arr: inout[Int], _ n: Int)
	{
		// New Tree
		let tree: AvlTree = AvlTree();
		var i: Int = 0;
		while (i < n)
		{
			tree.root = tree.addTreeNode(tree.root, arr[i]);
			i += 1;
		}
		self.index = 0;
		self.sortedElements(tree.root, &arr);
	}
}
func main()
{
	let task: SortArray = SortArray();
	// Array of integer elements
	var arr: [Int] = [6, 2, 6, 2, 4, 6, 3, 6, 
                      2, 2, 8, 9, 3, 6, 8, 9];
	// Get the number of elements
	let n: Int = arr.count;
	task.sort(&arr, n);
	task.printRecord(arr, n);
}
main();

Output

  2  2  2  2  3  3  4  6  6  6  6  6  8  8  9  9
// Kotlin program
// Sort array with repeated element using AVL tree

// Avl tree node
class TreeNode
{
	var key: Int;
	var height: Int;
	var occurrence: Int;
	var left: TreeNode ? ;
	var right: TreeNode ? ;
	constructor(key: Int)
	{
		//Set node value of avl tree
		this.key = key;
		this.height = 1;
		this.occurrence = 1;
		this.left = null;
		this.right = null;
	}
}
class AvlTree
{
	var root: TreeNode ? ;
	constructor()
	{
		this.root = null;
	}
	//Get the height of given node
	fun height(node: TreeNode ? ): Int
	{
		if (node == null)
		{
			return 0;
		}
		return node.height;
	}
	//Get the max value of given two numbers
	fun maxHeight(a: Int, b: Int): Int
	{
		if (a > b)
		{
			return a;
		}
		else
		{
			return b;
		}
	}
	// Perform the Right rotate operation
	fun rightRotate(node: TreeNode ? ): TreeNode ?
	{
		//Get left child node
		val left_node: TreeNode? = node?.left;
		//Get left node right subtree
		val right_subtree: TreeNode? = 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.maxHeight(
      	this.height(node.left), 
        this.height(node.right)) + 1;
		left_node!!.height = this.maxHeight(
          this.height(left_node.left), 
          this.height(left_node.right)) + 1;
		return left_node;
	}
	// Perform the Left Rotate operation
	fun leftRotate(node: TreeNode ? ): TreeNode ?
	{
		// Get right child node
		val right_node: TreeNode? = node?.right;
		//Get right node left subtree
		val left_subtree: TreeNode? = 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.maxHeight(
      	this.height(node.left), 
        this.height(node.right)) + 1;
		right_node!!.height = this.maxHeight(
          	this.height(right_node.left), 
           	this.height(right_node.right)) + 1;
		return right_node;
	}
	// Get the balance factor
	fun getBalanceFactor(node: TreeNode ? ): Int
	{
		if (node == null)
		{
			return 0;
		}
		return this.height(node.left) - this.height(node.right);
	}
	// Recursively, add a node in AVL tree with
	// Duplicate keys are allowed
	fun addTreeNode(node: TreeNode ? , key : Int): TreeNode ?
	{
		if (node == null)
		{
			//return a new node
			return TreeNode(key);
		}
		if (key < node.key)
		{
			node.left = this.addTreeNode(node.left, key);
		}
		else if (key > node.key)
		{
			node.right = this.addTreeNode(node.right, key);
		}
		else
		{
			//When given key already exists
			node.occurrence = node.occurrence + 1;
			return node;
		}
		// Change the height of current node
		node.height = 1 + this.maxHeight(
          this.height(node.left), this.height(node.right));
		//Get balance factor of a node
		val balance_factor: Int = this.getBalanceFactor(node);
		if (balance_factor > 1 && key < node.left!!.key)
		{
			return this.rightRotate(node);
		}
		if (balance_factor < -1 && key > node.right!!.key)
		{
			return this.leftRotate(node);
		}
		if (balance_factor > 1 && key > node.left!!.key)
		{
			node.left = this.leftRotate(node.left);
			return this.rightRotate(node);
		}
		if (balance_factor < -1 && key < node.right!!.key)
		{
			node.right = this.rightRotate(node.right);
			return this.leftRotate(node);
		}
		return node;
	}
}
class SortArray
{
	var index: Int;
	constructor()
	{
		this.index = 0;
	}
	// Display given array elements
	fun printRecord(arr: Array < Int > , n: Int): Unit
	{
		var i: Int = 0;
		while (i < n)
		{
			print(" " + arr[i]);
			i += 1;
		}
	}
	// Collect sorted elements
	fun sortedElements(node: TreeNode ? , arr : Array < Int > ): Unit
	{
		if (node != null)
		{
			// Visit left subtree
			this.sortedElements(node.left, arr);
			var i: Int = 0;
			while (i < node.occurrence)
			{
				arr[this.index] = node.key;
				this.index = this.index + 1;
				i += 1;
			}
			// Visit right subtree
			this.sortedElements(node.right, arr);
		}
	}
	fun sort(arr: Array < Int > , n: Int): Unit
	{
		// New Tree
		val tree: AvlTree = AvlTree();
		var i: Int = 0;
		while (i < n)
		{
			tree.root = tree.addTreeNode(tree.root, arr[i]);
			i += 1;
		}
		this.index = 0;
		this.sortedElements(tree.root, arr);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: SortArray = SortArray();
	// Array of integer elements
	val arr: Array < Int > = arrayOf(6, 2, 6, 2, 4, 6, 3, 
                                     6, 2, 2, 8, 9, 3, 6, 8, 9);
	// Get the number of elements
	val n: Int = arr.count();
	task.sort(arr, n);
	task.printRecord(arr, n);
}

Output

 2 2 2 2 3 3 4 6 6 6 6 6 8 8 9 9


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