Question
Can you help me finish my implementation on AVL Tree? I'm having trouble writing the main method. import java.util.Scanner; // a generic avl tree node
Can you help me finish my implementation on AVL Tree?
I'm having trouble writing the main method.
import java.util.Scanner;
// a generic avl tree node class to hold the
class AVLTreeNode
{
// the key for this node
int key;
// the value for this node
V value;
// left and right child
AVLTreeNode
AVLTreeNode
// the height of this node
int height;
// constructor
public AVLTreeNode()
{
key = -1;
value = null;
leftChild = null;
rightChild = null;
height = 1;
}
// the parameterized constructor
public AVLTreeNode(int key,V value)
{
this.key = key;
this.value = value;
leftChild = null;
rightChild = null;
height = 1;
}
}
class DataItem
{
// the key
int key;
// the value
String value;
public DataItem(int key, String value)
{
this.key = key;
this.value = value;
}
}
class AVLTree
{
//The root for this tree
private AVLTreeNode
/* Constructor */
public AVLTree()
{
root = null;
}
public int getHeight(AVLTreeNode
{
if( node == null )
return 0;
return node.height;
}
// to right rotate
private AVLTreeNode
{
AVLTreeNode
AVLTreeNode
x.rightChild = node;
node.leftChild = t2;
node.height = Math.max( getHeight(node.leftChild), getHeight(node.rightChild)) + 1;
x.height = Math.max( getHeight( x.leftChild ), getHeight( x.rightChild )) + 1;
return x;
}
// to right rotate
private AVLTreeNode
{
AVLTreeNode
AVLTreeNode
y.leftChild = node;
node.rightChild = t2;
node.height = Math.max( getHeight(node.leftChild), getHeight(node.rightChild)) + 1;
y.height = Math.max( getHeight(y.leftChild ), getHeight( y.rightChild )) + 1;
return y;
}
// to get the balance
public int getBalance(AVLTreeNode
{
// if null, return 0
if (n == null)
return 0;
// difference between left and right child height
return getHeight(n.leftChild) - getHeight(n.rightChild);
}
// insert the new node
public void insert(int key, V value)
{
root = insert(root, key, value);
}
// the insert method
private AVLTreeNode
{
if (n == null)
return new AVLTreeNode
if (key < n.key)
n.leftChild = insert(n.leftChild, key, value);
else if( key > n.key )
n.rightChild = insert(n.rightChild, key, value);
else
return n;
n.height = Math.max( getHeight(n.rightChild), getHeight(n.leftChild)) + 1;
int balance = getBalance(n);
if (balance > 1 && key < n.leftChild.key )
return rotateRight(n);
if (balance < -1 && key > n.rightChild.key )
return rotateLeft(n);
if (balance > 1 && key > n.leftChild.key)
{
n.leftChild = rotateLeft(n.leftChild);
return rotateRight(n);
}
if (balance < -1 && key < n.rightChild.key)
{
n.rightChild = rotateRight(n.rightChild);
return rotateLeft(n);
}
return n;
}
// to search
public V search(int key)
{
AVLTreeNode
if( node == null )
return null;
return node.value;
}
// private helper method to search
private AVLTreeNode
{
// if this node is null
if( n == null) // return null
return null;
// if key is found, we return the node
if( n.key == key )
return n;
// if key is lesser than this, go left
if( n.key > key )
return search( n.leftChild, key);
else
return search( n.rightChild, key);
}
// the inorder traversal
public void inorder()
{
inorder( root );
}
// the inorder traversal
private void inorder( AVLTreeNode
{
// if this node is null, return
if( n == null )
return;
inorder(n.leftChild);
System.out.println(n.value + " ");
inorder(n.rightChild);
}
}//end AVLTree class
public class TestAVLTree
{
// main method
public static void main(String args[])
{
Scanner scan = new Scanner(System.in);
AVLTree tree = new AVLTree();
System.out.println("Testing AVLTree ");
char input;
}
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started