package tesfaibstst; /** * Ordered symbol table interface. * * @author Sedgewick

ID: 3806463 • Letter: P

Question

package tesfaibstst;
/**
* Ordered symbol table interface.
*
* @author Sedgewick and Wayne, Acuna
* @param <Key> search key
* @param <Value> return type
*/
public interface OrderedSymbolTable<Key, Value> extends SymbolTable<Key, Value> {

    //smallest key
    Key min();

    //largest key
    Key max();

    //largest key less than or equal to key
    Key floor(Key key);

    //smallest key greated than or equal to key
    Key ceiling(Key key);

    //number of keys less than key
    int rank(Key key);

    //key of rank k
    Key select(int k);

    //delete smallest key
    void deleteMin();

    //delete largest key
    void deleteMax();

    //number of keys in [lo..hi]
    int size(Key lo, Key hi);

    //keys in [lo..hi] in sorted order
    Iterable<Key> keys(Key lo, Key hi);
}

package tesfaibstst;
/**
* Symbol table interface.
*
* @author Sedgewick and Wayne, Acuna
* @param <Key> search key
* @param <Value> return type
*/
public interface SymbolTable<Key, Value> {
    // put key-value pair into the table
    void put(Key key, Value val);

    //get value paired with key
    Value get(Key key);

    //remove key (and its value) from table
    void delete(Key key);

    //is there a value paired with key?
    boolean contains(Key key);

    //is the table empty?
    boolean isEmpty();

    //number of key-value pairs
    int size();

    //all keys in the table, in sorted order
    Iterable<Key> keys();
}

/**
* 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<Key extends Comparable<Key>, Value> implements OrderedSymbolTable<Key, Value> {
private Node root;

    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.left, key);
        else 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 keyâ€™s 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.left = put(x.left, key, val);
        else 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 < 0) return floor(x.left, key);
        Node t = floor(x.right, key);
        if (t != null) return t;
        else return x;
    }

    @Override
    public Key select(int k) {
        return select(root, k).key;
    }

    private Node select(Node x, int k) {
        if (x == null) return null;
        int t = size(x.left);
        if (t > k) return select(x.left, k);
        else if (t < k) return select(x.right, k-t-1);
        else return x;
    }

    @Override
    public int rank(Key key) {
        return rank(key, root);
    }

    private int rank(Key key, Node x) {
        // Return number of keys less than x.key in the subtree rooted at x.
        if (x == null) return 0;
        int cmp = key.compareTo(x.key);
        if (cmp < 0) return rank(key, x.left);
        else if (cmp > 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.left = delete(x.left, key);
        else 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<Key> keys() {
        return keys(min(), max());
    }

    @Override
    public Iterable<Key> keys(Key lo, Key hi)
    {
        Queue<Key> queue = new LinkedList<>();
        keys(root, queue, lo, hi);
        return queue;
    }

    private void keys(Node x, Queue<Key> queue, Key lo, Key hi)
    {
        if (x == null) return;
        int cmplo = lo.compareTo(x.key);
        int cmphi = hi.compareTo(x.key);
        if (cmplo < 0) keys(x.left, queue, lo, hi);
        if (cmplo <= 0 && cmphi >= 0) queue.add(x.key);
        if (cmphi > 0) keys(x.right, queue, lo, hi);
    }

    @Override
    public boolean contains(Key key) {
        throw new UnsupportedOperationException("Not supported yet.");
    }

    @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<Integer, String> bst = new BaseBSTST();

        bst.put(10, "TEN");
        bst.put(3, "THREE");
        bst.put(1, "ONE");
        bst.put(5, "FIVE");
        bst.put(2, "TWO");
        bst.put(7, "SEVEN");

        System.out.println("Before balance:");
        bst.printLevel(10); //root

        System.out.println("After balance:");
        bst.balance();
        bst.printLevel(5); //root
    }
}

Implementing a Binary Search Tree Summary: In this assignment, you will complete the implementation of a Binary Search Tree, and write veral methods that manipulate it 1 Background In order to practice implementing symbol tables, you will implement a binary search tree. A BST can actually be considered to be another type of data structure that we can use to implement an ADT. Since symbol tables are about finding values based on keys (the "search" problem), it's appropriate to use a BST to implement them. B are nice structures for searching, because they mimic the process of a binary search STs CO(logn)). Unfortunately, fast O(logn) look ups only work in BSTs that are balanced. Any time we remove or add nodes, there is a chance the tree will become stilted, which can degrade search t look like O(n) After we finish the implementation of a BST, we will go on to address this problem This document is separated into four sections: Background, Requirements, Testing, and Submission You have almost finished reading the Background section already. In Requirements, we will discuss what xpected of you in this homework. In Testing, we give some basic suggestions on how the tree additions should be tested. Lastly, Submission discusses how your source code should be submitted on BlackBoard 2 Requirements 150 pointsl In this assignment you will practice implementing symbol tables using BST's. Download the attached base file and then rename it, and the class inside, to include your last name instead of Base You will only need to change the base file The purpose of orderedSymbolTable and SymbolTable are only to define the ADT which the BST data structure supports Implement contains 0, isEmpty0, ceiling(), deleteMax0, and size 10 points Recursive methods are nice since it is easy to tell they work, however, they tend to be slo than non recursive methods. Give non-recursive implementations of get0 and put (Hint: the book contains the solution for one of these.) 15 pointsl Write a method that balances an existing BST, call it balance If the tree is balanced, then searching for keys will take act like binary search and require only logn comparisons. (Come up with a way yourself don't skip to 3.3.) 120 pointsl Sedgewick 3.2.37: Write a method print Level (Key key) that takes a Key as argument and prints the keys in the subtree rooted at that node in level order (in order of their distance from the root, with nodes on each level in order from left to right). Hint: Use a elle. I15 points

Explanation / Answer

import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

public class BaseBSTST<Key extends Comparable<Key>, Value> implements OrderedSymbolTable<Key, Value> {
private Node root;

    private class Node
    {
        private final Key key;
        private Value val;
        private Node left, right;
        private int N;

    @Override
    public boolean isEmpty() {
        throw new UnsupportedOperationException("Not supported yet.");
    }

Navigate

package templates; import java.util.*; public classTemplates1Main { /** * @param

package test: import java.util.Scanner; public class IntrestRate { public static

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

package tesfaibstst; /** * Ordered symbol table interface. * * @author Sedgewick

Question

Explanation / Answer

Related Questions

Navigate