Question: Complete the Binary Search Tree implementation in java, get, minimum, deleteMax, DeleteMin, maxumum and put public class TreeMap implements Map Iterable { protected Node root;
Complete the Binary Search Tree implementation in java, get, minimum, deleteMax, DeleteMin, maxumum and put
public class TreeMap
protected Node root;
private int size;
protected class Node {
public Key key;
public Value value;
public Node left;
public Node right;
public Node(Key key, Value value) {
this.key = key;
this.value = value;
}
}@Override
public void clear() {
root = null;
size = 0;
}
@Override
public boolean empty() {
return size() == 0;
}
@Override
public int size() {
return size;
}
@Override
public boolean contains(Key key) {
if (key == null) {
throw new IllegalArgumentException("argument has a null");
}
return get(key) != null;
}
@Override
public Value get(Key key) {
// finish this function
return null;
}
@Override
public void put(Key key, Value value) {
if (key == null) {
throw new IllegalArgumentException("calls puts with a null key");
}
if (value == null) {
delete(key);
return;
}
Size = size+1;
// finish this function
}
public void deleteMinimum() {
if (isEmpty()) {
throw new NoSuchElementException("Symbol table underflow");
}
root = deleteMinimum(root);
Size = size -1;
}
private Node deleteMininimum(Node node) {
//finish this function
return null;
}
@Override
public void delete(Key key) {
if (key == null) {
throw new IllegalArgumentException("calls delete() with a null key");
}
root = delete(root, key);
size--;
}
public void deleteMaximum() {
if (isEmpty()) {
throw new NoSuchElementException("Symbol table underflow");
}
root = deleteMaximum(root);
size = size -1;
}
private Node deleteMax(Node node) {
// finish this function
return null;
}
public Key minimum() {
if (empty()) {
throw new NoSuchElementException("returns maximum with empty symbol tablee");
}
return minimum(root).key;
}
private Node minimum(Node node) {
// finish this function
return null;
}
private Node delete(Node node, Key key) {
if (node == null) {
return null;
}
int cmp = key.compareTo(node.key);
if (cmp < 0) {
node.left = delete(node.left, key);
} else if (cmp > 0) {
node.right = delete(node.right, key);
} else {
if (node.right == null) {
return node.left;
}
if (node.left == null) {
return node.right;
}
Node t = node;
node = min(t.right);
node.right = deleteMin(t.right);
node.left = t.left;
}
return node;
}
public Key maximum() {
if (empty()) {
throw new NoSuchElementException("returns maximum with empty symbol table");
}
return maximum(root).key;
}
private Node maximum(Node node) {
// finish
return null;
}
public boolean isBST() {
return isBST(root, null, null);
}
private boolean iBSTTrue(Node node, Key min, Key maximum) {
if (node == null) {
return true;
}
if (maximum != null && node.key.compareTo(max) >= 0) {
return false;
}
if (min != null && node.key.compareTo(min) <= 0) {
return false;
}
return BSTTrue(node.left, min, node.key) && BSTTrue(node.right, node.key, max);
}
@Override
public Iterator
Queue
Queue
queue.enqueue(root);
while (!queue.isEmpty()) {
Node node = queue.dequeue();
if (node == null) {
continue;
}
keys.enqueue(node.key);
queue.enqueue(node.left);
queue.enqueue(node.right);
}
return new Iterator
private Iterator
@Override
public boolean hasNext() {
return itr.hasNext();
}
@Override
public Key next() {
return itr.next();
}
};
}
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help