- #1
DODGEVIPER13
- 672
- 0
Homework Statement
Write a java program to construct an AVL tree and then generate 100 random numbers to insert to this tree and then delete randomly 50 of these random numbers from this AVL tree.
(use the AVL tree animation of your book to understand the bahavior of the this tree in the case of insertion and deletion, www.cs.armstrong.edu/liang/animation/AVLTreeAnimation.html).
Homework Equations
The Attempt at a Solution
The program BinaryTree errors deal with the inorder method I am not sure what the heck is wrong with it becuase it came straight from the book I would just like it so that I can create a test class for it but I can't resolve this error. There is also an error with my AVLTree program its updateheigth method is not quite right.
Code:
public class BinaryTree<E extends Comparable<E>> extends Abstracttree<E> {
protected TreeNode<E> root;
protected int size = 0;
public BinaryTree(){
}
public BinaryTree(E[] objects){
for(int i = 0;i < objects.length; i++)
insert(objects[i]);
}
public boolean search(E e){
TreeNode<E> current = root;
while ( current != null){
if(e.compareTo(current.element)< 0){
current = current.left;
}
else if (e.compareTo(current.element) > 0){
current = current.right;
}
else
return true;
}
return false;
}
public boolean insert(E e){
if(root == null)
root = createNewNode(e);
else{
TreeNode<E> parent = null;
TreeNode<E> current = root;
while(current != null)
if (e.compareTo(current.element) < 0){
parent = current;
current = current.left;
}
else if (e.compareTo(current.element) > 0){
parent = current;
current = current.right;
}
else
return false;
if(e.compareTo(parent.element)< 0)
parent.left = createNewNode(e);
else
parent.right = createNewNode(e);
}
size++;
return true;
}
protected TreeNode<E> createNewNode(E e){
return new TreeNode<E>(e);
}
public void inorder(){
inorder(root);
}
protected void inorder(TreeNode<E> root){
if(root== null) return;
inorder(root.left);
System.out.print(root.element + " ");
inorder(root.right);
}
public void postorder(){
postorder(root);
}
protected void postorder(TreeNode<E> root){
if(root== null) return;
postorder(root.left);
postorder(root.right);
System.out.print(root.element + " ");
}
public void preorder() {
preorder(root);
}
protected void preorder(TreeNode<E> root){
if(root == null) return;
System.out.print(root.element + " ");
preorder(root.left);
preorder(root.right);
}
@Override
public void inOrder() {
throw new UnsupportedOperationException("Not supported yet.");
}
public static class TreeNode<E extends Comparable<E>>{
E element;
TreeNode<E> left;
TreeNode<E> right;
public TreeNode(E e){
element = e;
}
}
public int getSize(){
return size;
}
public TreeNode getRoot(){
return root;
}
public java.util.ArrayList<TreeNode<E>> path(E e) {
java.util.ArrayList<TreeNode<E>> list = new java.util.ArrayList<TreeNode<E>>();
TreeNode<E> current = root;
while(current != null){
list.add(current);
if(e.compareTo(current.element) < 0){
current = current.left;
}
else if (e.compareTo(current.element) > 0){
current = current.right;
}
else break;
}
return list;
}
public boolean delete(E e){
TreeNode<E> parent = null;
TreeNode<E> current = root;
while(current != null){
if(e.compareTo(current.element) < 0){
parent = current;
current = current.left;
}
else if (e.compareTo(current.element) > 0){
parent = current;
current = current.right;
}
else
break;
}
if(current == null)
return false;
if(current.left == null){
if(parent == null){
root = current.right;
}
else{
if(e.compareTo(parent.element) < 0)
parent.left = current.right;
else
parent.right = current.right;
}
}
else{
TreeNode<E> parentOfRightMost = current;
TreeNode<E> rightMost = current.left;
while(rightMost.right != null){
parentOfRightMost = rightMost;
rightMost = rightMost.right;
}
current.element = rightMost.element;
if(parentOfRightMost.right == rightMost)
parentOfRightMost.right = rightMost.left;
else
parentOfRightMost.left = rightMost.left;
}
size--;
return true;
}
public java.util.Iterator iterator(){
return inorderIterator();
}
public java.util.Iterator inorderIterator(){
return new InorderIterator();
}
class InorderIterator implements java.util.Iterator {
private java.util.ArrayList<E> list = new java.util.ArrayList<E>();
private int current = 0;
public InorderIterator(){
inorder();
}
public void inorder(TreeNode<E> root){
if(root == null) return;
inorder(root.left);
list.add(root.element);
inorder(root.right);
}
public boolean hasNext(){
if(current < list.size())
return true;
return false;
}
public Object next(){
return list.get(current++);
}
public void remove(){
delete(list.get(current));
list.clear();
inorder();
}
private void inorder() {
throw new UnsupportedOperationException("Not yet implemented");
}
}
public void clear(){
root = null;
size = 0;
}
}
Code:
public abstract class Abstracttree<E extends Comparable<E>>implements Tree<E> {
public void inorder() {
}
public void postorder() {
}
public void preorder() {
}
public boolean isEmpty() {
return getSize() == 0;
}
public java.util.Iterator iterator() {
return null;
}
}
Code:
public interface Tree<E extends Comparable<E>> {
public boolean search(E e);
public boolean insert(E e);
public boolean delete(E e);
public void inOrder();
public void postorder();
public void preorder();
public int getSize();
public boolean isEmpty();
public java.util.Iterator iterator();
}
Code:
public class AVLTree<E extends Comparable<E>> extends BinaryTree<E> {
public AVLTree(){
}
public AVLTree(E[] objects){
super(objects);
}
@Override
protected AVLTreeNode<E> createNewNode(E o){
return new AVLTreeNode<E>(o);
}
public boolean insert(E o){
boolean successful = super.insert(o);
if (!successful)
return false; // o is already in the tree
else {
balancePath(o); // Balance from o to the root if necessary
}
return true; //
}
private int balanceFactor(AVLTreeNode<E> node) {
if (node.right == null) // node has no right subtree
return -node.height;
else if (node.left == null) // node has no left subtree
return +node.height;
else
return ((AVLTreeNode<E>)node.right).height -
((AVLTreeNode<E>)node.left).height;
}
public void updateHeigth(AVLTreeNode<E> node){
if (node.left == null && node.right == null)
node.height = 0;
else if (node.left == null) // node has no left subtree
node.height = 1 + ((AVLTreeNode<E>)(node.right)).height;
else if (node.right == null) // node has no right subtree
node.height = 1 + ((AVLTreeNode<E>)(node.left)).height;
else
node.height = 1 +
Math.max(((AVLTreeNode<E>)(node.right)).height,
((AVLTreeNode<E>)(node.left)).height);
}
private void balanceLL(TreeNode<E> A, TreeNode<E> parentOfA) {
TreeNode<E> B = A.left; // A is left-heavy and B is left-heavy
if (A == root) {
root = B;
}
else {
if (parentOfA.left == A) {
parentOfA.left = B;
}
else {
parentOfA.right = B;
}
}
A.left = B.right; // Make T2 the left subtree of A
B.right = A; // Make A the left child of B
updateHeight((AVLTreeNode<E>)A);
updateHeight((AVLTreeNode<E>)B);
}
private void balanceLR(TreeNode<E> A, TreeNode<E> parentOfA) {
TreeNode<E> B = A.left; // A is left-heavy
TreeNode<E> C = B.right; // B is right-heavy
if (A == root) {
root = C;
}
else {
if (parentOfA.left == A) {
parentOfA.left = C;
}
else {
parentOfA.right = C;
}
}
A.left = C.right; // Make T3 the left subtree of A
B.right = C.left; // Make T2 the right subtree of B
C.left = B;
C.right = A;
// Adjust heights
updateHeight((AVLTreeNode<E>)A);
updateHeight((AVLTreeNode<E>)B);
updateHeight((AVLTreeNode<E>)C);
}
private void balanceRR(TreeNode<E> A, TreeNode<E> parentOfA) {
TreeNode<E> B = A.right; // A is right-heavy and B is right-heavy
if (A == root) {
root = B;
}
else {
if (parentOfA.left == A) {
parentOfA.left = B;
}
else {
parentOfA.right = B;
}
}
A.right = B.left; // Make T2 the right subtree of A
B.left = A;
updateHeight((AVLTreeNode<E>)A);
updateHeight((AVLTreeNode<E>)B);
}
private void balanceRL(TreeNode<E> A, TreeNode<E> parentOfA) {
TreeNode<E> B = A.right; // A is right-heavy
TreeNode<E> C = B.left; // B is left-heavy
if (A == root) {
root = C;
}
else {
if (parentOfA.left == A) {
parentOfA.left = C;
}
else {
parentOfA.right = C;
}
}
A.right =C.left; // Make T2 the right subtree of A
B.left = C.right; // Make T3 the left subtree of B
C.left = A;
C.right = B;
// Adjust heights
updateHeight((AVLTreeNode<E>)A);
updateHeight((AVLTreeNode<E>)B);
updateHeight((AVLTreeNode<E>)C);
}
private void balancePath(E o){
java.util.ArrayList<TreeNode<E>> path = path(o);
for (int i = path.size() - 1; i >= 0; i--) {
AVLTreeNode<E> A = (AVLTreeNode<E>)(path.get(i));
updateHeight(A);
AVLTreeNode<E> parentOfA = (A == root) ? null :
(AVLTreeNode<E>)(path.get(i - 1));
switch (balanceFactor(A)) {
case -2:
if (balanceFactor((AVLTreeNode<E>)A.left) <= 0) {
balanceLL(A, parentOfA); // Perform LL rotation
}
else {
balanceLR(A, parentOfA); // Perform LR rotation
}
break;
case +2:
if (balanceFactor((AVLTreeNode<E>)A.right) >= 0) {
balanceRR(A, parentOfA); // Perform RR rotation
}
else {
balanceRL(A, parentOfA); // Perform RL rotation
}
}
}
}
public boolean delete(E element) {
if (root == null)
return false; // Element is not in the tree
// Locate the node to be deleted and also locate its parent node
TreeNode<E> parent = null;
TreeNode<E> current = root;
while (current != null) {
if (element.compareTo(current.element) < 0) {
parent = current;
current = current.left;
}
else if (element.compareTo(current.element) > 0) {
parent = current;
current = current.right;
}
else
break; // Element is in the tree pointed by current
}
if (current == null)
return false; // Element is not in the tree
if (current.left == null) {
// Connect the parent with the right child of the current node
if (parent == null) {
root = current.right;
}
else {
if (element.compareTo(parent.element) < 0)
parent.left = current.right;
else
parent.right = current.right;
// Balance the tree if necessary
balancePath(parent.element);
}
}
else {
// Case 2: The current node has a left child
// Locate the rightmost node in the left subtree of
// the current node and also its parent
TreeNode<E> parentOfRightMost = current;
TreeNode<E> rightMost = current.left;
while (rightMost.right != null) {
parentOfRightMost = rightMost;
rightMost = rightMost.right; // Keep going to the right
}
// Replace the element in current by the element in rightMost
current.element = rightMost.element;
// Eliminate rightmost node
if (parentOfRightMost.right == rightMost)
parentOfRightMost.right = rightMost.left;
else
// Special case: parentOfRightMost is current
parentOfRightMost.left = rightMost.left;
// Balance the tree if necessary
balancePath(parentOfRightMost.element);
}
size--;
return true; // Element insert
// Case 1: current has no left children (See Figure 23.6)
}
private void updateHeight(AVLTreeNode<E> avlTreeNode) {
throw new UnsupportedOperationException("Not yet implemented");
}
protected static class AVLTreeNode<E extends Comparable<E>>
extends BinaryTree.TreeNode<E> {
int height = 0;
public AVLTreeNode(E o) {
super(o);
}
}
}
Last edited: