# 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)
{
}
else if (key > node->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)
{
}
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)
{
}
else if (key > node.key)
{
}
else
{
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)
{
}
this.index = 0;
sortedElements(tree.root, arr);
}

public static void main(String[] args)
{
// 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;
}
}``````

#### 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
{
if (node == NULL)
{
//return a new node
return new TreeNode(key);
}
if (key < node->key)
{
}
else if (key > node->key)
{
}
else
{
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)
{
}
this->index = 0;
this->sortedElements(tree->root, arr);
}
};
int main()
{
// 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]);
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)
{
}
else if (key > node.key)
{
}
else
{
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)
{
}
this.index = 0;
this.sortedElements(tree.root, arr);
}
public static void Main(String[] args)
{
// 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;
}
}``````

#### 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 {
} else if key > node.key {
} else {
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++ {
}
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)
}``````

#### 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
{
if (\$node == NULL)
{
//return a new node
return new TreeNode(\$key);
}
if (\$key < \$node->key)
{
}
else if (\$key > \$node->key)
{
}
else
{
\$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)
{
}
\$this->index = 0;
\$this->sortedElements(\$tree->root, \$arr);
}
}

function main()
{
// 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);
}
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
{
if (node == null)
{
//return a new node
return new TreeNode(key);
}
if (key < node.key)
{
}
else if (key > node.key)
{
}
else
{
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)
{
}
this.index = 0;
this.sortedElements(tree.root, arr);
}
}

function main()
{
// 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;
}
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
if (node == None) :
# return a new node
return TreeNode(key)

if (key < node.key) :
elif (key > node.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) :
i += 1

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

def main() :
#  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)

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_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
if (node == nil)
# return a new node
return TreeNode.new(key)
end

if (key < node.key)
elsif (key > node.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_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)
i += 1
end

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

end

def main()
#  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
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)
{
}
else if (key > node.key)
{
}
else
{
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)
{
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;
}
}``````

#### 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)
{
}
else if (key > node!.key)
{
}
else
{
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)
{
i += 1;
}
self.index = 0;
self.sortedElements(tree.root, &arr);
}
}
func main()
{
// 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;
}
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)
{
}
else if (key > node.key)
{
}
else
{
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)
{
i += 1;
}
this.index = 0;
this.sortedElements(tree.root, arr);
}
}
fun main(args: Array < String > ): Unit
{
// 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();
}``````

#### Output

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

## Comment

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.