+1 (208) 254-6996 [email protected]

I need this completed by today; please bid if this is possible!

Coding Component (50%)

Don't use plagiarized sources. Get Your Custom Essay on
Computer Science AVL Tree
Just from $13/Page
Order Essay

We’ve provided you with an implementation of an unbalanced binary search tree. The tree implements an ordered dynamic set over a generic comparable type T. Supported operations include insertion, deletion, min, max, and testing whether a value is in the set (via the exists method). Because it’s a set, duplicates are not allowed, and the insert operation will not insert a value if it is already present.

We have implemented the BST operations in a recursive style. For example, inserting a value into a tree recurses down the tree seeking the correct place to add a new leaf. Each recursive call returns the root of the subtree on which it was called, after making any modifications needed to the subtree to perform the insertion. Deletion is implemented similarly.

Your job is to add the functionality needed to keep the tree balanced using the AVL property. In particular, you will need to

· augment the tree to maintain the height of each of its subtrees, as discussed in Studio;

· compute the balance at the root of a subtree (which is the height of the root’s left subtree minus that of its right subtree);

· implement the AVL rebalancing operation, along with the supporting rotation operations; and

· call the height maintenance and rebalancing operations at the appropriate times during insertion and deletion.

Code Outline

There are two main source code files you need to consider, both in the avl package:

· TreeNode.java implements a class TreeNode that represents a node of a binary search tree. It holds a value (the key of the node) along with child and parent pointers. It has a height data member that is currently not used for anything. You should not modify this file, but you need to understand its contents.

· AVLTree.java implements an ordered set as a binary search tree made out of TreeNode objects.

The AVLTree class provides an interface that includes element insertion and deletion, as well as an exists() method that tests whether a value is present in the set. It also offers min() and max() methods. These methods all work as given for (unbalanced) BSTs, using the algorithms we discussed in lecture.

To implement the AVL balancing method, you will need to fill in some missing code to maintain the height of each subtree and perform rebalancing. Look for the ‘FIXME’ tags in AVLTree.java to see which methods you must modify.

Height Maintenance

You’ll need to set the height data member each time a new leaf is allocated in the tree. You can then maintain the height as part of insertion or deletion using the incremental updating strategy you worked out in Studio 10, Part C.

The update procedure updateHeight() takes in a node and updates its height using the heights of its two subtrees. It should run in constant time.

You’ll need to call updateHeight() wherever it is needed – in insertion, deletion, and perhaps elsewhere.

Rebalancing

You must implement four methods as part of AVL rebalancing:

· getBalance() computes the balance factor of a subtree given its root. It should run in constant time using stored subtree height information.

· rebalance() rebalances a tree whose balance factor is +2 or -2, using rotations according to the AVL rebalancing algorithm.

· rightRotate() performs a right rotation on a subtree.

· leftRotate() performs a left rotation on a subtree.

In addition to implementing these methods, you will need to call the rebalancing algorithm as needed during insertion and deletion.

Tree-printing output

The codebase provides utility functions for printing binary trees in the file avl/util/TreeToStrings.java . Many of the tests provided in the codebase call these utility functions during normal operation and/or error printing, some tests have print calls commented out so you can add them during debugging, and you are encouraged to call the functions in your own tests as well. It is therefore to your great advantage to understand the format in which these functions print a tree.

The most commonly-used print method in the test code, formatVertically , prints a tree in  prefix order  (i.e. parent, then left subtree, then right subtree). One node is printed per line, with the depth of the node equivalent to the number of ‘|’ characters printed before it. For example, if the following values are inserted into an empty BST in order:

2, 1, 3

…then formatVertically will print the following:

Root-2

| L-1

| R-3

As a slightly larger example, if the following values are inserted into an empty BST in order:

7, 4, 10, 3, 5, 8, 17, 15, 20

…then formatVertically` will print the following:

Root-7

| L-4

| | L-3

| | R-5

| R-10

| | L-8

| | R-17

| | | L-15

| | | R-20

, represeting the tree: 

Unit tests

The following unit tests are provided in the avl.test package in your repository:

1. TestSmall: contains a variety of tests for insertion and deletion, some of which require no rebalancing and some of which require rebalancing due to all four unbalanced AVL cases. These tests should be a great help in debugging your code, so it is to your advantage to be familiar with all of them before debugging.

2. TestFull: tests full functionality on large trees. Some of trees built by this test are quite large (100,000 elements or more). These large tests may fail to finish in a reasonable amount of time or may cause Java to crash with a stack overflow (due to very deep recursion in insert or delete) unless your tree is properly balanced.

3. TestCustom: Three empty function stubs that you can fill in with your own tests as you see fit.

The autograder will run the tests in TestSmall.java and TestFull.java as given to determine your coding grade (TestSmall: 75% of coding credit, TestFull: 25% of coding credit).

All tests should finish within a few seconds, and the autograder will time out and record zero credit after 20 seconds.

As always, passing the unit test does not guarantee that your code is correct – you are ultimately responsible for correctness – but failing it does indicate that there is a problem you need to fix.

If you want to check your understanding of how AVL trees work or see what tree you should get for a small input, you might find  this AVL tree visualizer  helpful.

What to Turn In (READ CAREFULLY)

To complete this portion of the lab, you must do the following:

1. Make sure you have not modified any files besides AVLTree.java.

2. Make sure your code passes the JUnit tests as given in your repository.

3. Make sure you eliminate or disable any print statements or other extraneous code that you may have used for debugging. Extraneous code may slow down your implementation to the point that our autograder will fail it for taking too long to run.

4. Make sure you do a Team/Pull on your repository before attempting to push your code. Remember,  pull before push!

5. You must both commit and push all of your code to your repository AND submit it to Gradescope. It’s best to commit from the top-most level of your repository, which bears your name and student ID. If you do not push your code to your GitHub repository, Gradescope will not be using the latest version of your code for testing.

package avl;

import java.util.LinkedList;

public class AVLTree<T extends Comparable<T>> {

/* For the AVL Lab, find all ‘FIXME’s and

* supply the code asked for.

*/

private TreeNode<T> root;

public int size;

public AVLTree() {

this.root = null;

this.size = 0;

}

////////////////////////////////////////////////////////

//

// exists()

// Check whether a specified value exists in the set

//

public boolean exists(T value) {

return existsHelper(value, this.root);

}

//

// existsHelper()

// (Optionally) recursive procedure to traverse a tree

// rooted at “root” to find a specified value.

//

// RETURNS: true if the value is found, else false

//

private boolean existsHelper(T value, TreeNode<T> root) {

if (root == null) { // not found

return false;

} else {

int comparison = value.compareTo(root.value);

if (comparison == 0) { // found

return true;

} else if (comparison < 0) { // still looking – go left

return existsHelper(value, root.left);

} else { // still looking – go right

return existsHelper(value, root.right);

}

}

}

////////////////////////////////////////////////////////

//

// min()

// Return the minimum value in the set

//

// If the set is empty, result is undefined.

//

public T min() {

return minValueInSubtree(this.root);

}

//

// minValueInSubTree()

// Find the smallest value in the subtree rooted at

// the specified node.

//

// ASSUMED: root is not null.

//

private T minValueInSubtree(TreeNode<T> root) {

while (root.left != null)

root = root.left;

return root.value;

}

//

// max()

// Return the maximum value in the set

//

// If the set is empty, result is undefined.

//

public T max() {

return maxValueInSubtree(this.root);

}

//

// maxValueInSubTree()

// Find the largest value in the subtree rooted at

// the specified node.

//

// ASSUMED: root is not null.

//

private T maxValueInSubtree(TreeNode<T> root) {

while (root.right != null)

root = root.right;

return root.value;

}

////////////////////////////////////////////////////////

//

// insert()

// Insert the specified value in the set if it does not

// already exist.

//

// RETURNS: the size of the set after insertion.

//

public int insert(T value)

{

this.root = insertHelper(value, this.root);

return size;

}

//

// insertHelper()

// Recursive procedure to insert a value into the subtree

// rooted at “root”. If value is already present in the

// tree, nothing is inserted.

//

// RETURNS: root node of subtree after insertion

//

// FIXME: add the necessary code to this function

// to maintain height and rebalance the tree when

// a node is removed.

//

private TreeNode<T> insertHelper(T value,

TreeNode<T> root) {

if (root == null) {

// add new element as leaf of tree

TreeNode<T> newNode = new TreeNode<T>(value);

size++;

return newNode;

} else {

int comparison = value.compareTo(root.value);

if (comparison == 0) {

// duplicate element — return existing node

return root;

} else if (comparison < 0) {

// still looking — go left

root.setLeft(insertHelper(value, root.left));

} else {

// still looking — go right

root.setRight(insertHelper(value, root.right));

}

return root;

}

}

////////////////////////////////////////////////////////

//

// remove()

// Remove a value from the set if it is present

//

public void remove(T value) {

this.root = removeHelper(value, this.root);

}

//

// removeHelper()

// Recursive procedure to remove a value from the

// subtree rooted at “root”, if it exists.

//

// RETURNS root node of subtree after insertion

//

// FIXME: add the necessary code to this function

// to maintain height and rebalance the tree when

// a node is removed.

//

private TreeNode<T> removeHelper(T value,

TreeNode<T> root) {

if (root == null) { // did not find element

return null;

} else {

int comparison = value.compareTo(root.value);

if (comparison == 0) { // found element to remove

if (root.left == null || root.right == null) {

// base case — root has at most one subtree,

// so return whichever one is not null (or null

// if both are)

size–;

return (root.left == null ? root.right : root.left);

} else {

// node with two subtrees — replace key

// with successor and recursively remove

// the successor.

T minValue = minValueInSubtree(root.right);

root.value = minValue;

root.setRight(removeHelper(minValue, root.right));

}

} else if (comparison < 0) {

// still looking for element to remove — go left

root.setLeft(removeHelper(value, root.left));

} else {

// still looking for element to remove — go right

root.setRight(removeHelper(value, root.right));

}

return root;

}

}

////////////////////////////////////////////////////////

//

// INTERNAL METHODS FOR MAINTAINING BALANCE

//

// updateHeight()

//

// Recompute the height of the subtree rooted at “root”,

// assuming that its left and right children (if any)

// have correct heights for their respective subtrees.

//

// EFFECT: Set the root’s height field to the updated value

//

private void updateHeight(TreeNode<T> root) {

// FIXME: fill in the update code

}

//

// getBalance()

// Return the balance factor of a subtree rooted at “root”

// (left subtree height – right subtree height)

//

private int getBalance(TreeNode<T> root) {

// FIXME: fill in the balance computation

return 0;

}

//

// rebalance()

//

// Rebalance an AVL subtree, rooted at “root”, that has possibly

// been unbalanced by a single node’s insertion or deletion.

//

// RETURNS: the root of the subtree after rebalancing

//

private TreeNode<T> rebalance(TreeNode<T> root) {

// FIXME: fill in the rebalancing code

return null;

}

//

// rightRotate() (Clockwise)

// Perform a right rotation on a tree rooted at “root”

// The tree’s root is assumed to have a left child.

//

// Tree Before: Tree After:

// c (root) b

// / \ / \

// b t4 a c

// / \ / \ / \

// a t3 t1 t2 t3 t4

// / \

// t1 t2

//

// RETURNS: the new root after rotation.

//

private TreeNode<T> rightRotate(TreeNode<T> root) {

// FIXME: fill in the rotation code

return null;

}

//

// leftRotate()

// Perform a left rotation on a tree rooted at “root”

// The tree’s root is assumed to have a right child.

//

// Tree Before: Tree After:

// (root)

// / \ / \

// ? ? ? ?

// … … / \ / \

// ? ? ? ?

//

//

//

// RETURNS: the new root after rotation.

//

private TreeNode<T> leftRotate(TreeNode<T> root) {

// FIXME: fill in the rotation code

return null;

}

/////////////////////////////////////////////////////////////

//

// METHODS USED TO VALIDATE CORRECTNESS OF TREE

// (You should not have to touch these)

//

//

// getRoot()

// Return the root node of the tree (for validation only!)

//

public TreeNode<T> getRoot() {

return this.root;

}

//

// enumerate()

// Return the contents of the tree as an ordered list

//

public LinkedList<T> enumerate() {

return enumerateHelper(this.root);

}

//

// enumerateHelper()

// Enumerate the contents of the tree rooted at “root” in order

// as a linked list

//

private LinkedList<T> enumerateHelper(TreeNode<T> root) {

if (root == null)

{

return new LinkedList<T>();

}

else

{

LinkedList<T> list = enumerateHelper(root.left);

list.addLast(root.value);

list.addAll(enumerateHelper(root.right));

return list;

}

}

}

Order your essay today and save 10% with the discount code ESSAYHELP