write a program to build a binary search tree Dictionary. Input records are from
ID: 3864507 • Letter: W
Question
write a program to build a binary search tree Dictionary. Input records are from inventory.txt. The data for the BST <Key,E> KVpair are; Key is the PartNo and Element is the Inventory record from the input record.
Use inventory.txt, BinNode.java, BSTNode.java, BST.java, Dictionary.java and Inventory.java found below.
Dictionary.java
/** The Dictionary abstract class. */
public interface Dictionary<Key, E> {
/** Reinitialize dictionary */
public void clear();
/** Insert a record
@param k The key for the record being inserted.
@param e The record being inserted. */
public void insert(Key k, E e);
/** Remove and return a record.
@param k The key of the record to be removed.
@return A maching record. If multiple records match
"k", remove an arbitrary one. Return null if no record
with key "k" exists. */
public E remove(Key k);
/** Remove and return an arbitrary record from dictionary.
@return the record removed, or null if none exists. */
public E removeAny();
/** @return A record matching "k" (null if none exists).
If multiple records match, return an arbitrary one.
@param k The key of the record to find */
public E find(Key k);
/** @return The number of records in the dictionary. */
public int size();
};
inventory.txt
GT12C1068A,YUKON XL,07-14 GMC YUKON XL RT Front fender brace Lower Bracket Hinge,24.00
NI27E1251B,ALTIMA SDN,13-15 NISSAN ALTIMA SDN RT Front fender liner From 10-12 (CAPA),63.00
NI23H1297A,ALTIMA SDN,13-15 NISSAN ALTIMA SDN LT Front fender liner From 10-12 (CAPA),48.00
CV15F1067A,SILVERADO 1500 (NEW),07-13 CHEVY SILVERADO 1500 LT Front fender brace Lower Bracket Hinge,23.00
HY07E1288A,SONATA,15-16 HYUNDAI SONATA Front bumper cover 2.4L Std Type w/o Park Assist prime (CAPA),326.00
CV20B1225B,SILVERADO 1500 HYBRID,09-13 CHEVY SILVERADO 1500 HYBRID LT Front fender brace Lower Bracket Hinge,23.00
CV39A1251A,AVALANCHE,07-13 CHEVY AVALANCHE RT Front fender brace Lower Bracket Hinge,24.00
CV39A1250A,SUBURBAN,07-14 CHEVY SUBURBAN RT Front fender brace Lower Bracket Hinge,24.00
AC12C1250AQ,MDX,07-13 ACURA MDX LT Front fender liner (CAPA),68.00
AC12C1251AQ,MDX,07-13 ACURA MDX RT Front fender liner (CAPA),68.00
BinNode.java
/** ADT for binary tree nodes */
public interface BinNode<E> {
/** Get and set the element value */
public E element();
public void setElement(E v);
/** @return The left child */
public BinNode<E> left();
/** @return The right child */
public BinNode<E> right();
/** @return True if a leaf node, false otherwise */
public boolean isLeaf();
}
BST.java
import java.lang.Comparable;
/** Binary Search Tree implementation for Dictionary ADT */
class BST<Key extends Comparable<? super Key>, E>
implements Dictionary<Key, E> {
private BSTNode<Key,E> root; // Root of the BST
int nodecount; // Number of nodes in the BST
/** Constructor */
BST() { root = null; nodecount = 0; }
/** Reinitialize tree */
public void clear() { root = null; nodecount = 0; }
/** Insert a record into the tree.
@param k Key value of the record.
@param e The record to insert. */
public void insert(Key k, E e) {
root = inserthelp(root, k, e);
nodecount++;
}
// Return root
public BSTNode getRoot()
{
return root;
}
/** Remove a record from the tree.
@param k Key value of record to remove.
@return The record removed, null if there is none. */
public E remove(Key k) {
E temp = findhelp(root, k); // First find it
if (temp != null) {
root = removehelp(root, k); // Now remove it
nodecount--;
}
return temp;
}
/** Remove and return the root node from the dictionary.
@return The record removed, null if tree is empty. */
public E removeAny() {
if (root == null) return null;
E temp = root.element();
root = removehelp(root, root.key());
nodecount--;
return temp;
}
/** @return Record with key value k, null if none exist.
@param k The key value to find. */
public E find(Key k) { return findhelp(root, k); }
/** @return The number of records in the dictionary. */
public int size() { return nodecount; }
private E findhelp(BSTNode<Key,E> rt, Key k) {
if (rt == null) return null;
if (rt.key().compareTo(k) > 0)
return findhelp(rt.left(), k);
else if (rt.key().compareTo(k) == 0) return rt.element();
else return findhelp(rt.right(), k);
}
/** @return The current subtree, modified to contain
the new item */
private BSTNode<Key,E> inserthelp(BSTNode<Key,E> rt,
Key k, E e) {
if (rt == null) return new BSTNode<Key,E>(k, e);
if (rt.key().compareTo(k) > 0)
rt.setLeft(inserthelp(rt.left(), k, e));
else
rt.setRight(inserthelp(rt.right(), k, e));
return rt;
}
/** Remove a node with key value k
@return The tree with the node removed */
private BSTNode<Key,E> removehelp(BSTNode<Key,E> rt,Key k) {
if (rt == null) return null;
if (rt.key().compareTo(k) > 0)
rt.setLeft(removehelp(rt.left(), k));
else if (rt.key().compareTo(k) < 0)
rt.setRight(removehelp(rt.right(), k));
else { // Found it
if (rt.left() == null) return rt.right();
else if (rt.right() == null) return rt.left();
else { // Two children
BSTNode<Key,E> temp = getmin(rt.right());
rt.setElement(temp.element());
rt.setKey(temp.key());
rt.setRight(deletemin(rt.right()));
}
}
return rt;
}
private BSTNode<Key,E> getmin(BSTNode<Key,E> rt) {
if (rt.left() == null) return rt;
return getmin(rt.left());
}
private BSTNode<Key,E> deletemin(BSTNode<Key,E> rt) {
if (rt.left() == null) return rt.right();
rt.setLeft(deletemin(rt.left()));
return rt;
}
private void printhelp(BSTNode<Key,E> rt) {
if (rt == null) return;
printhelp(rt.left());
printVisit(rt.element());
printhelp(rt.right());
}
private StringBuffer out;
public String toString() {
out = new StringBuffer(400);
printhelp(root);
return out.toString();
}
private void printVisit(E it) {
out.append(it + " ");
}
}
//********************************************************************
// Inventory.java
//
//********************************************************************
public class Inventory
{
protected String PartNo;
protected String Model;
protected String Description;
protected Double ListPrice;
//-----------------------------------------------------------------
// Constructor: Sets up this inventory using the specified
// information.
//-----------------------------------------------------------------
public Inventory() {
}
public String GetPartNo()
{
return PartNo;
}
public void SetInventory (String ePartNo, String eModel, String eDescription, Double eListPrice)
{
PartNo = ePartNo;
Model = eModel;
Description = eDescription;
ListPrice = eListPrice;
}
//-----------------------------------------------------------------
// Returns a string including the basic inventory information.
//-----------------------------------------------------------------
public String toString()
{
String result = null;
if (PartNo != null)
{
result = "Part Number: " + PartNo + " ";
result += "Model: " + Model + " ";
result += "List Price: "+ Double.toString(ListPrice) + " ";
result += "Description: " + Description + " ";
}
return result;
}
//-----------------------------------------------------------------
//
//-----------------------------------------------------------------
}
Explanation / Answer
Implement Dictionary Using Binary Search Tree
Example:
well
/
bus xmas
/
air aero zebra
In the above example, keys present at the left sub-tree of the root node are lesser than the key of the root node. And also, the keys present at the right sub-tree are greater than the key of the root node.
InsertionInBST(T, newnode)
y<-NULL
x <- root[T]
while x != NULL
y<-x
if key[z] < key
then x <- left[x]
else x <- right[x]
parent[newnode] <- y
if y == NULL
then root[T] <- newnode
else if key[newnode] < key[y]
then left[y] <- newnode
else right[y] <- newnode
Insert "yell" to the below binary search tree.
workload
/
bus xmas
/
air aero zebra
workload
/
bus xmas
/ /
air aero yell zebra
To delete a node from binary search tree, we have three different cases.
Node X has no children
Node X has one child
Node X has two children
Case 1:
If X has no children
workload
/
bus xmas
/ /
air aero yell zebra
Delete "zebra" from above binary search tree.
workload
/
bus xmas
/ /
air aero yell
Case 2:
If X has only one child, then delete x and point the parent of x to the child of x.
workload
/
bus xmas
/ /
air aero yell
Delete "xmas" from the above binary search tree.
workload
/
bus yell
/
air aero
Case 3:
If X has two children, then find its successor 'S'. Remove 'S' from the binary search tree. And replace X with 'S'
workload
/
bus xmas
/ /
air aero yell zebra
Remove "workload" from the above binary search tree. The successor for "workload"(smallest element in the right subtree of "workload") is "yell". Remove it and replace "workload with "yell".
yell
/
bus xmas
/
air aero zebra
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.