The current implementation uses 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 LocationContainer 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. Use these values instead of reimplementing your own. 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 LocationContainer for you already.$)$

This skeleton code has a lot of moving parts. There is an abstract LocationContainer 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 to compare DiskLocations to each other. You should not modify any file besides BST$.$java. You can

add as many private supporting methods as you need.

The height of a tree is defined as the number of steps it takes to get from the root to the deepest child. This

means a tree with a single node has a height of $0.$ A balanced tree with $7$ nodes has a height of $2.$ Check

out the SIZE method in LocationContainer for an idea how to measure the height. Think of the height of

the node as $1+$ the height of its larger subtree.

The FIND method should return the DiskLocation in your BST that has the same track$/$sector values as the

input parameter.

The NEXT and PREV methods should return nil if they are called with the largest$/$smallest value in the tree,

respectively.

$//$ TODO: document class

public class BST extends LocationContainer $\{$

@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$;

$\}$

$\}$