Java Algorithms Binary Search Trees

The skeleton code on below is the start of a program to schedule I/O requests to the head/arm of a hard disk. Each I/O request is for a specific track and sector. Your program must track all of the incoming requests and then, when told where the drive head is, return the n next or previous I/O requests. (This is the elevator method of I/O scheduling.) We will assume that requests are ordered first by track and then by sector, and that each request is unique. Tracks and sectors are both represented as non-negative numbers.

The current implementation has a linked list that works poorly under common loads. Implement a binary search tree and the methods to support it.

The skeleton code has an abstract LocationHolder class. This class has methods to build a data structure, find values in it, and find the next or previous location. It also has two important parts of a binary tree implemented: root and nil. There is one class already implemented:

L Implements a linked list data structure

For this assignment, you will implement the methods in the remaining class: BST.java as a binary search tree. For sources for this assignment, you should use the lecture slides and the book (chapter 12). I would recommend sticking closely to the pseudocode, and using the nil construct that the book suggests. (nil is implemented in LocationHolder for you already.)

This skeleton code has a lot of moving parts. There is an abstract LocationHolder class, which L and BST both inherit from. There is a supporting node class called DiskLocation.java that holds the location and all necessary node information. It also has a comparator method, isGreaterThan, that you should use. You should not modify any file besides BST.java. You can add as many private supporting methods as you need.

In order to get next and prev to work you need to implement find first.

/*

* A class that represents a binary tree node to hold disk location information

* The node has parent, left, and right references for binary trees

*/

public class DiskLocation {

private int track;

private int sector;

public DiskLocation left;

public DiskLocation right;

public DiskLocation parent;

public boolean isGreaterThan(DiskLocation that) {

if (this.track > that.track)

return true;

else if (this.track == that.track && this.sector > that.sector)

return true;

return false;

}

public boolean equals(Object that) {

if (that.getClass() != this.getClass())

return false;

DiskLocation d = (DiskLocation) that;

return (this.track == d.track && this.sector == d.sector);

}

public DiskLocation(int t, int s) {

track = t;

sector = s;

left = null;

right = null;

parent = null;

}

public String toString() {

if (track < 0)

return new String("");

return String.format("Track: %d, Sector: %d", track, sector);

}

}

/*

* A doubly linked list implementation to hold DiskLocations

* The list is sorted on inserts so that next and prev are fast

*

* The class uses DiskLocation's right/parent for next/prev in the list

*/

public class L extends LocationHolder {

@Override

public DiskLocation find(DiskLocation d) {

return _find(d, root);

}

private DiskLocation _find(DiskLocation d, DiskLocation curr) {

if (curr == nil)

return nil;

else if (d.equals(curr))

return curr;

else

return _find(d, curr.right);

}

@Override

public DiskLocation next(DiskLocation d) {

return d.right;

}

@Override

public DiskLocation prev(DiskLocation d) {

return d.parent;

}

@Override

public void insert(DiskLocation d) {

if (root == null) { //empty list

root = d;

d.parent = nil;

d.right = nil;

return;

}

DiskLocation temp = root;

DiskLocation prev = nil;

while (!temp.isGreaterThan(d) && !temp.equals(nil)) {

prev = temp;

temp = temp.right;

}

d.parent = prev;

d.right = temp;

if (temp != nil)

temp.parent = d;

if (prev != nil)

prev.right = d;

else

root = d;

}

@Override

public int height() {

int h = 0;

DiskLocation d = root;

while (d != nil) {

h++;

d = d.right;

}

return h;

}

}

import java.util.Scanner;

/* Provides next/previous/height info on (int, int) disk locations

*

* Wentworth Institute of Technology

* COMP 2350

* Lab Assignment 4

*

*/

public class LAB4 {

// read pairs of ints from scanner

// returns an array of DiskLocations

private static DiskLocation getLoc(Scanner s) {

int track, sector = 0;

track = s.nextInt();

if (s.hasNextInt())

sector = s.nextInt();

else {

System.err.println("Track/sector mismatch on input " + s.next());

System.exit(0);

}

if (track < 0 || sector < 0) {

System.err.println("Track and sector values must be non-negative");

System.exit(0);

}

DiskLocation d = new DiskLocation(track, sector);

return d;

}

// prints the next/prev n items after a specific location

// the location must be a valid location in l

private static void printIter(LocationHolder l, DiskLocation d, char direction, int number) {

DiskLocation temp = l.find(d);

for (int i = 0; i < number; i++) {

if (temp == LocationHolder.nil)

return;

if (direction == 'n')

temp = l.next(temp);

else if (direction == 'p')

temp = l.prev(temp);

if (temp.toString().length() == 0)

break;

System.out.println(temp.toString());

}

}

public static void main(String[] args) {

Scanner s = new Scanner(System.in);

s.useDelimiter("(\\s|,)+"); //delimit with commas

LocationHolder l = new BST();

System.out.printf("Enter the data structure to use ([l]ist, [b]inary tree): ");

char algo = s.next().charAt(0);

switch (algo) {

case 'l':

l = new L();

break;

case 'b':

l = new BST();

break;

default:

System.out.println("Invalid data structure");

System.exit(0);

break;

}

System.out.printf("Enter non-negative track/sector pairs separated by commas. Terminate the list with one of the following options: ");

System.out.printf("Enter [n] to print the next values after a location (must be valid location). ");

System.out.printf("Enter [p] to print the previous values before a location (must be valid location). ");

System.out.printf("Enter [h] to print the height of the data structure ");

System.out.printf("Enter [q] to quit ");

System.out.printf("*** Example (inserts three locations and asks for the previous 2 before (2, 1): 0 1, 1 1, 2 1 p 2 1 2 *** ");

char nextAction = ',';

while (nextAction == ',') {

l.insert(getLoc(s));

if (!s.hasNextInt())

nextAction = s.next().charAt(0); // read in option

}

switch (nextAction) {

case 'n':

case 'p':

int track = -1;

int sector = -1;

int number = -1;

System.out.printf("Enter starting

: ");

if (s.hasNextInt())

track = s.nextInt();

if (s.hasNextInt())

sector = s.nextInt();

System.out.printf("Enter number of locations to seek: ");

if (s.hasNextInt())

number = s.nextInt();

else {

System.err.println("Couldn't read track/sector and number");

System.exit(0);

}

printIter(l, new DiskLocation(track, sector), nextAction, number);

break;

case 'h':

System.out.printf("height: %d ", l.height());

break;

case 'q':

System.exit(0);

default:

System.out.println("Invalid action");

System.exit(0);

break;

}

s.close();

}

}

/*

* An abstract class to insert and retrieve some info about disk locations

*/

public abstract class LocationHolder {

public static DiskLocation nil = new DiskLocation(-1, -1);

protected DiskLocation root;

public abstract DiskLocation find(DiskLocation d); // returns the object or nil

public abstract DiskLocation next(DiskLocation d); // returns the next object or nil

public abstract DiskLocation prev(DiskLocation d); // returns the previous object or nil

public abstract void insert(DiskLocation d); // inserts the object

public abstract int height(); // returns the largest tree height

public int size() {

return _size(root);

}

private int _size(DiskLocation D) {

if (D == null || D == nil)

return 0;

return 1 + _size(D.left) + _size(D.right);

}

}

//This is the method that you should edit

// @Override tags tell the compiler that the method is implementing a method

// inherited from the abstract parent class

// will return relevant DiskLocation for each method

// will need tests to check for robustness (prevent program from breaking)

// TODO: document class

public class BST extends LocationHolder {

@Override

public DiskLocation find(DiskLocation d) {

// TODO: implement method

return null;

}

@Override

public DiskLocation next(DiskLocation d) {

// TODO: implement method

return null;

}

@Override

public DiskLocation prev(DiskLocation d) {

// TODO: implement method

return null;

}

@Override

public void insert(DiskLocation d) {

// TODO: implement method

}

@Override

public int height() {

// TODO: implement method

return -1;

}

}