COMP 282 - Project 1 The purpose of this project is to introduce you to building

Question

COMP 282 - Project 1
The purpose of this project is to introduce you to building and utilizing trees. It will consist of multiple parts, each corresponding to a lecture. You will be expected to follow the directions for submission to the letter. Failure to do so will result in you receiving no credit for the assignment. Instructions for Submission You must provide all source les in a single .zip le. This le most contain no directories whatsoever. That is, if I were to unzip it, the contents would be only the .java les required for the project. For example, in a *nix environment, I would create a submission by navigating to my source directory issuing a zip AdamClark *.java. Under no circumstances will a submission be accepted if it is the product of you zipping your IDE’s project directory! There are to be absolutely no packages used in your submissions. The use of the default package is, generally, not advised for enterprise-level work; this, however, is not that. Additionally, you should not include any main functions in your submission, only those les required for each project part are recommended. The following les must be present in your submission: • Tree.java • BinaryTree.java • AVLTree.java
You may include any interfaces described here, but they will not be examined. A successful project need only include the list of les mentioned above – with appropriate implementations, of course.
Part 1 - The Tree Class In order to build more complex tree-based structures, you need to start with the basics. Namely, you will need to build a Tree class to store some arbitrary set of elements. We will extend this class throughout the rest of the project. The basic interface denition is as follows:
public interface ITree<T> {
public T getItem();
public ITree<T> find(T item);
public ITree<T> insert(T item); }
This should be included in your project as ITree.java. You must provide an implementation for this interface in form of a Tree class – to be dened in Tree.java:
public class Tree<T> implements ITree<T>
{ // ...
public Tree(T item) {
// ...
}
// ...
}
This is the only le required from this part of the project. Part 2 - Binary Search Trees
Now it’s time to take the general implementation of a tree, and extend from it a binary search tree. To do this, we will need to be able to only accept items that are ordinal:
public class BinaryTree<T extends Comparable<T>> extends Tree<Comparable<T>> { // ... }
You will want to override the find and insert methods of your Tree class in order to ensure you are using this new tree as eciently as possible. The BinaryTree.java le will be the only required le from this part of the project.
Part 3 - Traversal In this part, we will supply four methods for traversing our tree structures. The goal is to implement the following interface in your BinaryTree class: import java.util.*; public interface ITraversable<T> {
public ArrayList<T> nlr(); // Pre-order
public ArrayList<T> lnr(); // In-order
public ArrayList<T> lrn(); // Post-order
public ArrayList<T> bfs(); // Breadth-first } Each method should return an ArrayList of node values, based on the appropriate traversal.
Part 4 - Measurement In order to implement some more sophisticated trees, we will need an easy way of determining their heights. In order for to do this, we will implement another interface:
public interface IMeasurable {
public int size(); public int height();
}
These should be fairly self descriptive: the size method will return the total number of elements in the tree, while the height method returns its height. Remember: the height of a tree is the longest path from the root to any of its leaves
Part 5 - Rotation We have seen where the use of binary search trees can go wrong if we aren’t careful about their inputs. In order to be more robust against these bad situations, we will implement left and right rotations in the BinaryTree class. In order to accomplish this, you will have to implement a new interface: public interface IRotatable<T> {
public ITree<T> rotateLeft();
public ITree<T> rotateRight();
} Each function will operate on the root node of its tree, and perform the appropriate rotation. The return value should be the new root of the rotated tree. For example: BinaryTree<Integer> t = new BinaryTree<Integer>(1);
t.insert(2);
t.insert(3);
ITree<Integer> rotated = t.rotateLeft();
rotated.getItem(); // == 2
PART 6: AVL trees
Finally, your task will be to implement an AVLTree class which derives from your BinaryTree class. Your AVL Tree should maintain a balance factor during item insertion, and use it to rebalance the tree automatically whenever the balance factor is determined to be 1 or 1. You should also maintain a reference to your tree’s parent inside the class:
public class AVLTree<T extends Comparable<T>> extends BinaryTree<T> {
private int balance;
private AVLTree<T> parent; public AVLTree(T item) {
this(item, null);
}
public AVLTree(T item, AVLTree<T> parent) {
super(item);
this.balance = 0;
this.parent = parent; } } In order to properly extend your BinaryTree class, you will have to override its insert, rotateLeft, and rotateRight functions. This will be in order to maintain a proper balance factor, for retracing, and for maintaining a proper reference to each subtree’s parent during each of these operations. You will have to submit your AVLTree.java le for maximum credit.
COMP 282 - Project 1
The purpose of this project is to introduce you to building and utilizing trees. It will consist of multiple parts, each corresponding to a lecture. You will be expected to follow the directions for submission to the letter. Failure to do so will result in you receiving no credit for the assignment. Instructions for Submission You must provide all source les in a single .zip le. This le most contain no directories whatsoever. That is, if I were to unzip it, the contents would be only the .java les required for the project. For example, in a *nix environment, I would create a submission by navigating to my source directory issuing a zip AdamClark *.java. Under no circumstances will a submission be accepted if it is the product of you zipping your IDE’s project directory! There are to be absolutely no packages used in your submissions. The use of the default package is, generally, not advised for enterprise-level work; this, however, is not that. Additionally, you should not include any main functions in your submission, only those les required for each project part are recommended. The following les must be present in your submission: • Tree.java • BinaryTree.java • AVLTree.java
You may include any interfaces described here, but they will not be examined. A successful project need only include the list of les mentioned above – with appropriate implementations, of course.
Part 1 - The Tree Class In order to build more complex tree-based structures, you need to start with the basics. Namely, you will need to build a Tree class to store some arbitrary set of elements. We will extend this class throughout the rest of the project. The basic interface denition is as follows:
public interface ITree<T> {
public T getItem();
public ITree<T> find(T item);
public ITree<T> insert(T item); }
This should be included in your project as ITree.java. You must provide an implementation for this interface in form of a Tree class – to be dened in Tree.java:
public class Tree<T> implements ITree<T>
{ // ...
public Tree(T item) {
// ...
}
// ...
}
This is the only le required from this part of the project. Part 2 - Binary Search Trees
Now it’s time to take the general implementation of a tree, and extend from it a binary search tree. To do this, we will need to be able to only accept items that are ordinal:
public class BinaryTree<T extends Comparable<T>> extends Tree<Comparable<T>> { // ... }
You will want to override the find and insert methods of your Tree class in order to ensure you are using this new tree as eciently as possible. The BinaryTree.java le will be the only required le from this part of the project.
Part 3 - Traversal In this part, we will supply four methods for traversing our tree structures. The goal is to implement the following interface in your BinaryTree class: import java.util.*; public interface ITraversable<T> {
public ArrayList<T> nlr(); // Pre-order
public ArrayList<T> lnr(); // In-order
public ArrayList<T> lrn(); // Post-order
public ArrayList<T> bfs(); // Breadth-first } Each method should return an ArrayList of node values, based on the appropriate traversal.
Part 4 - Measurement In order to implement some more sophisticated trees, we will need an easy way of determining their heights. In order for to do this, we will implement another interface:
public interface IMeasurable {
public int size(); public int height();
}
These should be fairly self descriptive: the size method will return the total number of elements in the tree, while the height method returns its height. Remember: the height of a tree is the longest path from the root to any of its leaves
Part 5 - Rotation We have seen where the use of binary search trees can go wrong if we aren’t careful about their inputs. In order to be more robust against these bad situations, we will implement left and right rotations in the BinaryTree class. In order to accomplish this, you will have to implement a new interface: public interface IRotatable<T> {
public ITree<T> rotateLeft();
public ITree<T> rotateRight();
} Each function will operate on the root node of its tree, and perform the appropriate rotation. The return value should be the new root of the rotated tree. For example: BinaryTree<Integer> t = new BinaryTree<Integer>(1);
t.insert(2);
t.insert(3);
ITree<Integer> rotated = t.rotateLeft();
rotated.getItem(); // == 2
PART 6: AVL trees
Finally, your task will be to implement an AVLTree class which derives from your BinaryTree class. Your AVL Tree should maintain a balance factor during item insertion, and use it to rebalance the tree automatically whenever the balance factor is determined to be 1 or 1. You should also maintain a reference to your tree’s parent inside the class:
public class AVLTree<T extends Comparable<T>> extends BinaryTree<T> {
private int balance;
private AVLTree<T> parent; public AVLTree(T item) {
this(item, null);
}
public AVLTree(T item, AVLTree<T> parent) {
super(item);
this.balance = 0;
this.parent = parent; } } In order to properly extend your BinaryTree class, you will have to override its insert, rotateLeft, and rotateRight functions. This will be in order to maintain a proper balance factor, for retracing, and for maintaining a proper reference to each subtree’s parent during each of these operations. You will have to submit your AVLTree.java le for maximum credit.
COMP 282 - Project 1
The purpose of this project is to introduce you to building and utilizing trees. It will consist of multiple parts, each corresponding to a lecture. You will be expected to follow the directions for submission to the letter. Failure to do so will result in you receiving no credit for the assignment. Instructions for Submission You must provide all source les in a single .zip le. This le most contain no directories whatsoever. That is, if I were to unzip it, the contents would be only the .java les required for the project. For example, in a *nix environment, I would create a submission by navigating to my source directory issuing a zip AdamClark *.java. Under no circumstances will a submission be accepted if it is the product of you zipping your IDE’s project directory! There are to be absolutely no packages used in your submissions. The use of the default package is, generally, not advised for enterprise-level work; this, however, is not that. Additionally, you should not include any main functions in your submission, only those les required for each project part are recommended. The following les must be present in your submission: • Tree.java • BinaryTree.java • AVLTree.java
You may include any interfaces described here, but they will not be examined. A successful project need only include the list of les mentioned above – with appropriate implementations, of course.
Part 1 - The Tree Class In order to build more complex tree-based structures, you need to start with the basics. Namely, you will need to build a Tree class to store some arbitrary set of elements. We will extend this class throughout the rest of the project. The basic interface denition is as follows:
public interface ITree<T> {
public T getItem();
public ITree<T> find(T item);
public ITree<T> insert(T item); }
This should be included in your project as ITree.java. You must provide an implementation for this interface in form of a Tree class – to be dened in Tree.java:
public class Tree<T> implements ITree<T>
{ // ...
public Tree(T item) {
// ...
}
// ...
}
This is the only le required from this part of the project. Part 2 - Binary Search Trees
Now it’s time to take the general implementation of a tree, and extend from it a binary search tree. To do this, we will need to be able to only accept items that are ordinal:
public class BinaryTree<T extends Comparable<T>> extends Tree<Comparable<T>> { // ... }
You will want to override the find and insert methods of your Tree class in order to ensure you are using this new tree as eciently as possible. The BinaryTree.java le will be the only required le from this part of the project.
Part 3 - Traversal In this part, we will supply four methods for traversing our tree structures. The goal is to implement the following interface in your BinaryTree class: import java.util.*; public interface ITraversable<T> {
public ArrayList<T> nlr(); // Pre-order
public ArrayList<T> lnr(); // In-order
public ArrayList<T> lrn(); // Post-order
public ArrayList<T> bfs(); // Breadth-first } Each method should return an ArrayList of node values, based on the appropriate traversal.
Part 4 - Measurement In order to implement some more sophisticated trees, we will need an easy way of determining their heights. In order for to do this, we will implement another interface:
public interface IMeasurable {
public int size(); public int height();
}
These should be fairly self descriptive: the size method will return the total number of elements in the tree, while the height method returns its height. Remember: the height of a tree is the longest path from the root to any of its leaves
Part 5 - Rotation We have seen where the use of binary search trees can go wrong if we aren’t careful about their inputs. In order to be more robust against these bad situations, we will implement left and right rotations in the BinaryTree class. In order to accomplish this, you will have to implement a new interface: public interface IRotatable<T> {
public ITree<T> rotateLeft();
public ITree<T> rotateRight();
} Each function will operate on the root node of its tree, and perform the appropriate rotation. The return value should be the new root of the rotated tree. For example: BinaryTree<Integer> t = new BinaryTree<Integer>(1);
t.insert(2);
t.insert(3);
ITree<Integer> rotated = t.rotateLeft();
rotated.getItem(); // == 2
PART 6: AVL trees
Finally, your task will be to implement an AVLTree class which derives from your BinaryTree class. Your AVL Tree should maintain a balance factor during item insertion, and use it to rebalance the tree automatically whenever the balance factor is determined to be 1 or 1. You should also maintain a reference to your tree’s parent inside the class:
public class AVLTree<T extends Comparable<T>> extends BinaryTree<T> {
private int balance;
private AVLTree<T> parent; public AVLTree(T item) {
this(item, null);
}
public AVLTree(T item, AVLTree<T> parent) {
super(item);
this.balance = 0;
this.parent = parent; } } In order to properly extend your BinaryTree class, you will have to override its insert, rotateLeft, and rotateRight functions. This will be in order to maintain a proper balance factor, for retracing, and for maintaining a proper reference to each subtree’s parent during each of these operations. You will have to submit your AVLTree.java le for maximum credit.

Explanation / Answer

AVL Trees

The vast majority of the BST activities (e.g., seek, max, min, embed, erase.. and so on) take O(h) time where h is the tallness of the BST. The expense of these activities may progress toward becoming O(n) for a skewed Binary tree. On the off chance that we ensure that tallness of the tree remains O(Logn) after each addition and cancellation, at that point we can ensure an upper bound of O(Logn) for every one of these tasks. The stature of an AVL tree is dependably O(Logn) where n is the quantity of hubs in the tree (See this video address for confirmation).

Addition

To ensure that the given tree remains AVL after each addition, we should increase the standard BST embed task to play out some re-adjusting. Following are two essential activities that can be performed to re-balance a BST without disregarding the BST property (keys(left) < key(root) < keys(right)). 1) Left Rotation 2) Right Rotation

T1, T2 and T3 are subtrees of the tree

established with y (on the left side) or x (on

the correct side)

y x

/ Right Rotation/

x T3 – > T1 y

/ < -/

T1 T2 Left Rotation T2 T3

Keys in both of the above trees take after the

following request

keys(T1) < key(x) < keys(T2) < key(y) < keys(T3)

So BST property isn't abused anyplace.

Ventures to take after for addition

Give the recently embedded hub a chance to be w

1) Perform standard BST embed for w.

2) Starting from w, travel up and locate the primary uneven hub. Give z a chance to be the main lopsided hub, y be the offspring of z that goes ahead the way from w to z and x be the grandkid of z that goes ahead the way from w to z.

3) Re-balance the tree by performing proper revolutions on the subtree established with z. There can be 4 conceivable cases that should be dealt with as x, y and z can be orchestrated in 4 different ways. Following are the conceivable 4 courses of action:

a) y is left offspring of z and x is left offspring of y (Left Case)

b) y is left offspring of z and x is correct offspring of y (Left Right Case)

c) y is correct offspring of z and x is correct offspring of y (Right Case)

d) y is correct offspring of z and x is left offspring of y (Right Left Case)

Following are the activities to be performed in previously mentioned 4 cases. In the majority of the cases, we just need to re-offset the subtree established with z and the total tree ends up adjusted as the tallness of subtree (After suitable pivots) established with z winds up same as it was before addition

class AVLNode {
int keyy, ht;
AVLNode L, R;
  
AVLNode(int d) {
keyy = d;
ht = 1;
}
}
  
class AVLTree {
AVLNode root;
int ht(AVLNode N) {
if (N == null)
return 0;
  
return N.ht;
}
int max(int a, int b) {
return (a > b) ? a : b;
}
AVLNode rightRotate(AVLNode y) {
AVLNode x = y.L;
AVLNode T2 = x.R;
x.R = y;
y.L = T2;
y.ht = max(ht(y.L), ht(y.R)) + 1;
x.ht = max(ht(x.L), ht(x.R)) + 1;
return x;
}
AVLNode leftRotate(AVLNode x) {
AVLNode y = x.R;
AVLNode T2 = y.L;
y.L = x;
x.R = T2;
x.ht = max(ht(x.L), ht(x.R)) + 1;
y.ht = max(ht(y.L), ht(y.R)) + 1;
return y;
}

int getBalance(AVLNode N) {
if (N == null)
return 0;
  
return ht(N.L) - ht(N.R);
}
  
AVLNode insert(AVLNode AVLNode, int keyy) {
if (AVLNode == null)
return (new AVLNode(keyy));
  
if (keyy < AVLNode.keyy)
AVLNode.L = insert(AVLNode.L, keyy);
else if (keyy > AVLNode.keyy)
AVLNode.R = insert(AVLNode.R, keyy);
else
return AVLNode;
AVLNode.ht = 1 + max(ht(AVLNode.L),
ht(AVLNode.R));
int balance = getBalance(AVLNode);
if (balance > 1 && keyy < AVLNode.L.keyy)
return rightRotate(AVLNode);
if (balance < -1 && keyy > AVLNode.R.keyy)
return leftRotate(AVLNode);
if (balance > 1 && keyy > AVLNode.L.keyy) {
AVLNode.L = leftRotate(AVLNode.L);
return rightRotate(AVLNode);
}
if (balance < -1 && keyy < AVLNode.R.keyy) {
AVLNode.R = rightRotate(AVLNode.R);
return leftRotate(AVLNode);
}
return AVLNode;
}
void preOrder(AVLNode AVLNode) {
if (AVLNode != null) {
System.out.print(AVLNode.keyy + " ");
preOrder(AVLNode.L);
preOrder(AVLNode.R);
}
}
  
public static void main(String[] args) {
AVLTree tree = new AVLTree();
tree.root = tree.insert(tree.root, 10);
tree.root = tree.insert(tree.root, 20);
tree.root = tree.insert(tree.root, 30);
tree.root = tree.insert(tree.root, 40);
tree.root = tree.insert(tree.root, 50);
tree.root = tree.insert(tree.root, 25);
System.out.println("Preorder traversal" +
" of constructed tree is : ");
tree.preOrder(tree.root);
}
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.