Question: I have problem doing part C and I can't do part ii in Part D Here is my code: ******AVLnode.java*********** public class AvlNode { private
I have problem doing part C and I can't do part ii in Part D
Here is my code:
******AVLnode.java***********
public class AvlNode { private int value; private AvlNode left; private AvlNode right; private int height; public AvlNode(int value) { this.value = value; left = null; right = null; height = 0; } public int getValue() { return value; } public void setValue(int value) { this.value = value; } public AvlNode getLeft() { return left; } public void setLeft(AvlNode left) { this.left = left; } public AvlNode getRight() { return right; } public void setRight(AvlNode right) { this.right = right; } public int getHeight() { return height; } public void setHeight(int height) { this.height = height; } }
***********AVLtree.java************
import java.util.Random;
public class AvlTree {
AvlNode position;
AvlNode avlTree;
public AvlNode makeEmpty(AvlNode t) {
if (t != null) {
makeEmpty(t.getLeft());
makeEmpty(t.getRight());
t = null;
}
return null;
}
public AvlNode find(int value, AvlNode t) {
if (t == null) {
return null;
}
if (value
return find(value, t.getLeft());
} else if (value > t.getValue()) {
return find(value, t.getRight());
} else
return t;
}
public AvlNode findMin(AvlNode t) {
if (t == null) {
return null;
} else if (t.getLeft() == null)
return t;
else
return findMin(t.getLeft());
}
public AvlNode findMax(AvlNode t) {
if (t != null)
while (t.getRight() != null)
t = t.getRight();
return t;
}
public static int getHeight(AvlNode position) {
if (position == null)
return -1;
else
return position.getHeight();
}
public static int max(int lhs, int rhs) {
return lhs > rhs ? lhs : rhs;
}
public static AvlNode singleRotateWithLeft(AvlNode k2) {
AvlNode k1;
k1 = k2.getLeft();
k2.setLeft(k1.getRight());
k1.setRight(k2);
k2.setHeight(max(getHeight(k2.getLeft()), getHeight(k2.getRight())) + 1);
k1.setHeight(max(getHeight(k1.getLeft()), k2.getHeight()) + 1);
return k1;
}
public static AvlNode singleRotateWithRight(AvlNode k1) {
AvlNode k2;
k2 = k1.getRight();
k1.setRight(k2.getLeft());
k2.setLeft(k1);
k1.setHeight(max(getHeight(k1.getLeft()), getHeight(k1.getRight())) + 1);
k2.setHeight(max(getHeight(k2.getRight()), k1.getHeight()) + 1);
return k2;
}
public static AvlNode doubleRotateWithLeft(AvlNode k3) {
k3.setLeft(singleRotateWithRight(k3.getLeft()));
return singleRotateWithLeft(k3);
}
public static AvlNode doubleRotateWithRight(AvlNode k1) {
k1.setRight(singleRotateWithLeft(k1.getRight()));
return singleRotateWithRight(k1);
}
public AvlNode insert(int value, AvlNode t) {
if (t == null) {
t = new AvlNode(value);
} else if (value
t.setLeft(insert(value, t.getLeft()));
if (getHeight(t.getLeft()) - getHeight(t.getRight()) == 2)
if (value
t = singleRotateWithLeft(t);
else
t = doubleRotateWithLeft(t);
} else if (value > t.getValue()) {
t.setRight(insert(value, t.getRight()));
if (getHeight(t.getRight()) - getHeight(t.getLeft()) == 2)
if (value > t.getRight().getValue())
t = singleRotateWithRight(t);
else
t = doubleRotateWithRight(t);
}
t.setHeight(max(getHeight(t.getLeft()), getHeight(t.getRight())) + 1);
return t;
}
public int retrieve(AvlNode t) {
return t.getValue();
}
public void preOrder(AvlNode t) {
System.out.println(t.getValue());
if (t.getLeft() != null) {
preOrder(t.getLeft());
}
if (t.getRight() != null) {
preOrder(t.getRight());
}
}
public static void main(String[] args) {
AvlTree at = new AvlTree();
AvlNode t;
AvlNode position;
int i;
int j = 0;
int[] array = new int[4097];
Random rnd = new Random();
for(i = 0; i
array[i] = rnd.nextInt(4097-0+1)+0;
}
t = at.makeEmpty(null);
for (i = 0; i
t = at.insert(array[i], t);
/*for (i = 0; i
if ((position = at.find(i, t)) == null || at.retrieve(position) != i)
System.out.println("Error at " + i);*/
System.out.println("Min is " + at.retrieve(at.findMin(t)));
//at.preOrder(t);
}
}
1. Design and implement an AVL Tree Node class that must support "find- 2. Design and implement a driver (the main method) that does the following: (a) Creates an array that contains a list of integers, in a random order (b) AVL-insert, into the first AVL tree that is initially empty, the num- Min", "inser and "remove" operations. from 0 to to 4098 bers in the array sequentially from the start to the end. (c) Initialize the second empty AVL tree. (d) Enter a forever while loop to do the following: i. Call "findMin" to find the node with the smallest value ii. Call " Remove" to remove the smallest value from the first AVL tree, and display "The process with a priority of%d is now sched- uled to run!" iii. Call Insert to insert the removed value to the second AVL tree and display "The process with a priority of %d has run out of its timeslice!" iv. When the first AVL tree becomes empty, display "Every process has got a chance to run; Please press "Enter" to start the next round! v. When"Ente is pressed, swap the two AVL trees, and continue the loop
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help