Use a binary search tree to implement a dictionary that contains the keywords in
ID: 3538040 • Letter: U
Question
Use a binary search tree to implement a dictionary that contains the keywords in the Java language. Test it. Note that you can use the programs from the previous exercises.
public class BinarySearchTree
{
public BinarySearchTree()
{
root = new Node(); //dummy node as the root
root.setLeftChild(null);
root.setRightChild(null);
root.setInfo(-1);
}
public boolean isEmpty()
{
return root.getLeftChild()==null;
}
public void display()
{
inorderDisplay(root.getLeftChild());
System.out.println();
}
public boolean contains(int x)
{
return search(x, root.getLeftChild());
}
public void add(int x)
{
if (root.getLeftChild() == null)
{
Node p = new Node();
p.setNode(x, null, null);
root.setLeftChild(p);
}
else insert(x, root.getLeftChild());
}
public int getMin()
{
return getMin(root);
}
private Node root;
private void inorderDisplay(Node p)
{
if (p != null)
{
inorderDisplay(p.getLeftChild());
System.out.print(p.getInfo() + " ");
inorderDisplay(p.getRightChild());
}
}
private boolean search(int x, Node p)
{
if (p == null) return false;
else
if (x == p.getInfo()) return true;
else
if (x < p.getInfo()) return search(x, p.getLeftChild());
else return search(x, p.getRightChild());
}
private void insert(int x, Node p)
{
if (x < p.getInfo())
if (p.getLeftChild() == null)
{
Node q = new Node();
q.setNode(x, null, null);
p.setLeftChild(q);
}
else insert(x, p.getLeftChild());
else
if (p.getRightChild() == null)
{
Node q = new Node();
q.setNode(x, null, null);
p.setRightChild(q);
}
else insert(x, p.getRightChild());
}
private int getMin(Node p)
{
if (p.getLeftChild() == null) return p.getInfo();
else return getMin(p.getLeftChild());
}
}
Explanation / Answer
package username.bst;
import java.io.PrintWriter;
import java.util.Comparator;
import username.dict.Dict;
import username.dict.NoSuchKeyException;
/**
* An implementation of dictionaries using binary search trees.
*
implements Dict<K,V>
{
// +----------------------+------------------------------------
// | Implementation Notes |
// +----------------------+
/*
(1) A binary search tree is a binary tree in which the left
subtree contains keys less than the key stored in the root
and the right subtree contains keys greater than the key
stored in the root.
(2) No duplicate keys are allowed.
(3) To support dictionary-type operations, we store both a
key and a value in each node.
(4) Because putting a value can change the tree, we implement
it recursively using a helper method (putInSubtree) that
also takes a subtree as a parameter and returns the modified
subtree.
*/
// +--------+--------------------------------------------------
// | Fields |
// +--------+
/**
* The node that serves as the root of the tree.
*/
BSTNode<K,V> root;
/**
* The comparator used to determine ordering.
*/
Comparator<K> order;
// +--------------+--------------------------------------------
// | Constructors |
// +--------------+
/**
* Create a new binary search tree with a particular comparator.
*/
public BST(Comparator<K> _order)
{
this.root = null;
this.order = _order;
} // BST()
// +--------------------+--------------------------------------
// | Dictionary Methods |
// +--------------------+
public void put(K key, V value)
{
this.root = this.putInSubtree(this.root, key, value);
} // put(K,V)
public V get(K key)
throws NoSuchKeyException
{
return this.get(this.root, key);
} // get(K)
public void dump(PrintWriter pen)
{
this.dump(this.root, pen, "");
} // dump(PrintWriter)
// +---------------+-------------------------------------------
// | Local Helpers |
// +---------------+
/**
* Add something to the subtree rooted at n. Return the
* new subtree.
*/
BSTNode<K,V> putInSubtree(BSTNode<K,V> top, K key, V value)
{
// If we've reached the end of the tree, return a new node.
if (top == null) {
return new BSTNode<K,V>(key, value);
}
// Compare the top to the searched value.
int relationship = order.compare(key, top.key);
// Too small? Look in the left
if (relationship < 0) {
top.left = this.putInSubtree(top.left, key, value);
}
// Too large? Look in the right
else if (relationship > 0) {
top.right = this.putInSubtree(top.right, key, value);
}
// Otherwise, update the node
else {
top.value = value;
}
return top;
} // put(BSTNode<K,V>, K, V)
/**
* Get the value in the node with key key.
*/
V get(BSTNode<K,V> top, K key)
throws NoSuchKeyException
{
// If we've reached the end of the tree, give up.
if (top == null)
throw new NoSuchKeyException(key.toString());
// Compare the current key to the searched value.
int relationship = order.compare(key, top.key);
// Is the desired key smaller? If so, look in the left.
if (relationship < 0) {
return get(top.left, key);
}
// Is the desired key larger? If so, look in the right.
else if (relationship > 0) {
return get(top.right, key);
}
// Default: matched
else {
return top.value;
} // else
} // get(BSTNode<K,V>, key)
/**
* Remove the element with key key.
*/
public void remove(K key)
{
// STUB
} // remove(K)
/**
* Dump the tree with a certain indendation
*/
public void dump(BSTNode<K,V> top, PrintWriter pen, String indent)
{
// Sanity check
if (top == null) return;
// Dump away
pen.println(indent + top.key + " => " + top.value);
dump(top.left, pen, indent + " L ");
dump(top.right, pen, indent + " R ");
} // dump(BSTNode<i,V>, PrintWriter, String)
} // class BST
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.