Question
package tesfaibstst; /** * Ordered symbol table interface. * * @author Sedgewick and Wayne, Acuna * @param search key * @param return type */ public
package tesfaibstst; /** * Ordered symbol table interface. * * @author Sedgewick and Wayne, Acuna * @param
package tesfaibstst; /** * Symbol table interface. * * @author Sedgewick and Wayne, Acuna * @param
/** * A binary search tree based implementation of a symbol table. * * @author (your name), Sedgewick and Wayne, Acuna * @version (version) */ import java.util.Collections; import java.util.LinkedList; import java.util.Queue; public class BaseBSTST
private class Node { private final Key key; private Value val; private Node left, right; private int N;
public Node(Key key, Value val, int N) { this.key = key; this.val = val; this.N = N; } } @Override public int size() { return size(root); } private int size(Node x) { if (x == null) return 0; else return x.N; } @Override public Value get(Key key) { return get(root, key); } private Value get(Node x, Key key) { // Return value associated with key in the subtree rooted at x; // return null if key not present in subtree rooted at x. if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp 0) return get(x.right, key); else return x.val; } @Override public void put(Key key, Value val) { root = put(root, key, val); } private Node put(Node x, Key key, Value val) { // Change keys value to val if key in subtree rooted at x. // Otherwise, add new node to subtree associating key with val. if (x == null) return new Node(key, val, 1); int cmp = key.compareTo(x.key); if (cmp 0) x.right = put(x.right, key, val); else x.val = val; x.N = size(x.left) + size(x.right) + 1; return x; } @Override public Key min() { return min(root).key; } private Node min(Node x) { if (x.left == null) return x; return min(x.left); } @Override public Key max() { return max(root).key; } private Node max(Node x) { if (x.right == null) return x; return min(x.right); } @Override public Key floor(Key key) { Node x = floor(root, key); if (x == null) return null; return x.key; } private Node floor(Node x, Key key) { if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp == 0) return x; if (cmp k) return select(x.left, k); else if (t 0) return 1 + size(x.left) + rank(key, x.right); else return size(x.left); } @Override public void deleteMin() { root = deleteMin(root); } private Node deleteMin(Node x) { if (x.left == null) return x.right; x.left = deleteMin(x.left); x.N = size(x.left) + size(x.right) + 1; return x; } @Override public void delete(Key key) { root = delete(root, key); } private Node delete(Node x, Key key) { if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp 0) x.right = delete(x.right, key); else { if (x.right == null) return x.left; if (x.left == null) return x.right; Node t = x; x = min(t.right); x.right = deleteMin(t.right); x.left = t.left; } x.N = size(x.left) + size(x.right) + 1; return x; }
@Override public Iterable
@Override public boolean isEmpty() { throw new UnsupportedOperationException("Not supported yet."); }
@Override public Key ceiling(Key key) { throw new UnsupportedOperationException("Not supported yet."); } @Override public void deleteMax() { throw new UnsupportedOperationException("Not supported yet."); }
@Override public void size(Key lo, Key hi) { throw new UnsupportedOperationException("Not supported yet."); } public void balance() { throw new UnsupportedOperationException("Not supported yet."); } public void printLevel(Key key) { throw new UnsupportedOperationException("Not supported yet."); }
/** * entry point for testing. * * @param args the command line arguments */ public static void main(String[] args) { BaseBSTST
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started