I need help with writing this in Java language. I have the first task done. I ma
ID: 3813455 • Letter: I
Question
I need help with writing this in Java language. I have the first task done. I made a binary tree but I don't know how to make an AVL tree..
From the class you created in Task 1 derive an AvL tree. If done properly you should be able to use the functionality from your base class and simply add the code to balance the tree. This may involve overriding a function or two butlwill leave that up to you. Your class should balance the tree whenever a node is inserted or removed. This means you will probably have to keep track of when a sub "tree is taller and shorter than the other. Feel free to modify the node as neededExplanation / Answer
class node
{
int data, height;
node left, right;
node(int d)
{
data = d;
height = 1;
}
}
class AVLTree
{
node root;
int height(node n)
{
if (n == null)
return 0;
return n.height;
}
int map(int x, int c)
{
return (x > c) ? x : c;
}
node rightRotate(node y)
{
node p = y.left;
node T2 = p.right;
p.right = y;
y.left = T2;
y.height = map(height(y.left), height(y.right)) + 1;
p.height = map(height(p.left), height(p.right)) + 1;
return p;
}
node leftRotate(node p)
{
node y = p.right;
node T2 = y.left;
y.left = p;
p.right = T2;
p.height = map(height(p.left), height(p.right)) + 1;
y.height = map(height(y.left), height(y.right)) + 1;
return y;
}
int getbal(node n)
{
if (n == null)
return 0;
return height(n.left) - height(n.right);
}
node insert(node node, int data)
{
if (node == null)
return (new node(data));
if (data < node.data)
node.left = insert(node.left, data);
else if (data > node.data)
node.right = insert(node.right, data);
else
return node;
node.height = 1 + map(height(node.left),
height(node.right));
int bal = getbal(node);
if (bal > 1 && data < node.left.data)
return rightRotate(node);
if (bal < -1 && data > node.right.data)
return leftRotate(node);
if (bal > 1 && data > node.left.data)
{
node.left = leftRotate(node.left);
return rightRotate(node);
}
if (bal < -1 && data < node.right.data)
{
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}
node mininode(node node)
{
node current = node;
while (current.left != null)
current = current.left;
return current;
}
node delenode(node root, int data)
{
if (root == null)
return root;
if (data < root.data)
root.left = delenode(root.left, data);
else if (data > root.data)
root.right = delenode(root.right, data);
else
{
if ((root.left == null) || (root.right == null))
{
node temp = null;
if (temp == root.left)
temp = root.right;
else
temp = root.left;
if (temp == null)
{
temp = root;
root = null;
}
else
root = temp;
}
else
{
node temp = mininode(root.right);
root.data = temp.data;
root.right = delenode(root.right, temp.data);
}
}
if (root == null)
return root;
root.height = map(height(root.left), height(root.right)) + 1;
int bal = getbal(root);
if (bal > 1 && getbal(root.left) >= 0)
return rightRotate(root);
if (bal > 1 && getbal(root.left) < 0)
{
root.left = leftRotate(root.left);
return rightRotate(root);
}
if (bal < -1 && getbal(root.right) <= 0)
return leftRotate(root);
if (bal < -1 && getbal(root.right) > 0)
{
root.right = rightRotate(root.right);
return leftRotate(root);
}
return root;
}
void preOrder(node node)
{
if (node != null)
{
System.out.print(node.data + " ");
preOrder(node.left);
preOrder(node.right);
}
}
public static void main(String[] args)
{
AVLTree tree = new AVLTree();
tree.root = tree.insert(tree.root, 12);
tree.root = tree.insert(tree.root, 9);
tree.root = tree.insert(tree.root, 10);
tree.root = tree.insert(tree.root, 8);
tree.root = tree.insert(tree.root, 6);
tree.root = tree.insert(tree.root, 0);
tree.root = tree.insert(tree.root, 11);
tree.root = tree.insert(tree.root, 2);
tree.root = tree.insert(tree.root, 1);
System.out.println("Preorder traversal of "+"constructed tree is : ");
tree.preOrder(tree.root);
tree.root = tree.delenode(tree.root, 10);
System.out.println("Preorder traversal after "+"deletion of 10 :");
tree.preOrder(tree.root);
}
}