DATA STRUCTURE: The BST.java file provides the BST class, used to manage a Binar
ID: 3678060 • Letter: D
Question
DATA STRUCTURE:
The BST.java file provides the BST class, used to manage a Binary Search Tree. It has a reference for the root of the tree, and supports the Find(), Add(), and Delete() operations as well as providing a toString() method that lists the nodes in order, including the path to each node from the root.
Delete() is a short method that uses the Search method to find a node with the specified key, and then the Remove() method. Remove() removes the contents of the node passed to it, using appropriate replacement for a BST, and returns a reference to the node which replaced the node removed from the tree. Add() inserts the element provided and returns a reference to the new element’s node.
The underlying tree node class (ObjTNode) has links to the data for each node, as well as a field for the height of the node (initialized to 0 for empty nodes and 1 for nodes with content, but the heights are not maintained by the BST class). ObjTNode also provides the method for adding a “leaf” node, and uses a tree organization so that the actual leaves of the tree are empty, with all data (and references to data) held in internal nodes. Thus a “leaf” being added or removed is a node that has only empty children.
You need to extend the BST class into AVL, to turn the ordinary Binary Search Tree into an AVL Tree. Your AVL methods should call the BST methods (Add(), Remove()) to do the actual addition and removal of nodes, and then rebalance the tree according to the AVL tree rules. Your AVL class needs to provide the following methods:
1. Insert(Comparable element): Call Add() to add the element specified to the tree, and then update the node subtree heights and rebalance the tree as needed for the AVL rules.
2. Delete(Comparable item): override the existing Delete() method, providing instead a version that calls Remove() to remove the node and then rebalances the tree and updates subtree heights as needed for the AVL rules. It should also return the element removed from the tree (as the BST version does).
Your class should also have private methods as appropriate, to avoid repeating code and to provide good design. Your class should not have any additional variables declared globally for the class. Ensure that your code works with the provided Driver4.java code, which will be used to test your submitted solution. Organize and comment your code appropriately
BST.java
// with Find(), Add(), and Delete() methods
// uses common Search() for Find() and Delete()
// contains ObjTNode class for binary tree nodes
// invariant: all data is in internal nodes
// with empty leaves
// note: uses replace by successor
// and inserts ties into right subtree
// includes height field, set to 0 for empty leaves
// and 1 for newly inserted nodes
// Provides an inorder traversal to list the nodes
// along with the paths to each node
//****************************************************
public class BST
{
protected ObjTNode root;
public BST()
{
root = new ObjTNode(null);
}
public Comparable Find(Comparable item)
{
ObjTNode current = Search(item);
return current.item;
}
protected ObjTNode Search(Comparable item)
{
ObjTNode current = root;
while(current.item != null && item.compareTo(current.item) != 0) {
if(item.compareTo(current.item) < 0) {
current = current.left;
}
else {
current = current.right;
}
}
return current;
}
public ObjTNode Add(Comparable item)
{
// find insertion point based on order
// starting at root
// needs its own search due to allowing duplicate keys
ObjTNode current = root;
while(current.item != null) {
if(item.compareTo(current.item) < 0) {
current = current.left;
}
else {
current = current.right;
}
}
current.addleaf(item);
return current;
}
public Comparable Delete(Comparable item)
{
// find item, or null if there is no item with the key
Comparable element;
ObjTNode current = Search(item);
element = current.item;
if(current.item != null) { // have found item in tree, remove it
ObjTNode delpoint = Remove(current);
// System.out.println("Key " + element + " removed, node at del point is " + delpoint.item);
}
return element;
}
protected ObjTNode Remove(ObjTNode current)
{
// separate method to remove a node from the tree
// returns the node that replaces the node removed structurally
ObjTNode delpoint; // will point to the location where a node was removed
if(current.left.item != null && current.right.item != null) {
// node has two children, replace by successor
ObjTNode succ = current.right;
while(succ.left.item != null) {
succ = succ.left;
}
// swap into successor node
Comparable element = current.item;
current.item = succ.item;
succ.item = element;
if(succ != current.right) {
succ.parent.left = succ.right;
}
else {
current.right = succ.right;
}
succ.right.parent = succ.parent;
delpoint = succ.right;
}
else {
// node has at least one empty child, replace by the other child
// handles removal if the replacement child is empty or not
ObjTNode child;
if(current.left.item == null) {
child = current.right;
}
else {
child = current.left;
}
if(current.parent != null) {
if(current == current.parent.left) {
current.parent.left = child;
}
else {
current.parent.right = child;
}
}
else {
root = child;
}
child.parent = current.parent;
delpoint = child;
}
return delpoint;
}
private String inorder(String path, ObjTNode node)
{
String result = " ";
if(node.item != null) {
result = inorder(path+"L", node.left) + path + " " + node.toString() + inorder(path+"R", node.right);
}
return result;
}
public String toString()
{
String result = inorder("", root) + " ";
return result;
}
public class ObjTNode
{
public Comparable item;
public int height;
public ObjTNode left;
public ObjTNode right;
public ObjTNode parent;
public ObjTNode(Comparable element)
{
item = element;
height = 0;
left = null;
right = null;
parent = null;
}
public void addleaf(Comparable element)
{
if(left == null && right == null) {
item = element;
height = 1;
left = new ObjTNode(null);
left.parent = this;
right = new ObjTNode(null);
right.parent = this;
}
}
public String toString()
{
String result = "";
if(item != null) {
result = item.toString() + " " + height;
}
else {
result = "null " + height;
}
return result;
}
}
}
Driver4.java
import java.util.Scanner;
public class Driver4
{
public static void main(String[] args)
{
int n;
char c;
String word;
NumName item;
AVL tree = new AVL();
Scanner scan = new Scanner(System.in);
NumName goal = new NumName(0, "not found");
System.out.print("Command (f, a, r, q): ");
c = scan.next().charAt(0);
while(c!='q') {
if(c=='f') {
System.out.print("Enter integer to find: ");
n = scan.nextInt();
goal.number = n;
item = (NumName) tree.Find((Comparable) goal);
if(item != null) {
System.out.println(item);
}
else {
System.out.println(goal);
}
}
if(c == 'a') {
System.out.print("Enter integer to add: ");
n = scan.nextInt();
System.out.print("Enter name: ");
word = scan.next();
item = new NumName(n, word);
tree.Insert(item);
}
if(c == 'r') {
System.out.print("Enter integer to remove: ");
n = scan.nextInt();
goal.number = n;
item = (NumName) tree.Delete((Comparable) goal);
if(item != null) {
System.out.println("Key " + item.number + " removed.");
}
}
System.out.println(tree);
System.out.print("Command (f, a, r, q): ");
c = scan.next().charAt(0);
}
}
// classes for the items in the tree
abstract static class Item implements Comparable
{
public int number;
public String name;
public Item(int value, String word)
{
number = value;
name = word;
}
public String toString()
{
Integer iobj = new Integer(number);
String result = iobj.toString() + " " + name;
return result;
}
public int compareTo(Item other)
{
return number-other.number;
}
}
static class NumName extends Item
{
public NumName(int value, String word)
{
super(value, word);
}
public int compareTo(Object other)
{
return super.compareTo((Item)other);
}
}
}
Explanation / Answer
Binary Tree:
package sophy;
import java.io.*;
import java.lang.Integer;
class avl
{
public static void main(String[] args) throws IOException
{
//creating the object of BST
BST theTree = new BST();
//using insert method to insert some values....
theTree.insert(50);
theTree.insert(25);
theTree.insert(75);
theTree.insert(12);
theTree.insert(37);
theTree.insert(43);
theTree.insert(30);
//using insert method to insert some values....
theTree.insert(33);
theTree.insert(87);
theTree.insert(93);
theTree.insert(97);
//find node of the tree..
theTree.find(97, theTree.getRoot());
}
//putText
public static void putText(String s)
{
System.out.print(s);
System.out.flush();
}
//getString() method...
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
//getChar()..
public static char getChar() throws IOException
{
String s = getString();
return s.charAt(0);
}
//getInt()....
public static int getInt() throws IOException
{
String s = getString();
return Integer.parseInt(s);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.