1

I'm using a BST. Given a key, how will I find the successor key? This is the code I have so far. I've managed to insert a new key and retrieve a value given the key. Now, I need to finish the next method. How would I approach this?

class BST<K extends Comparable<K>, V> implements RangeMap<K,V> {
class Node {
    Node left;
    Node right;
    Node parent;
    KVPair<K,V> kv;
    K key;
    V value;
    public Node(K key, V value) {
        this.key = key;
        this.value = value;
        parent = left = right = sentinel;
    }
}

private Node root;


public void add(K key, V value) {
    // TODO: Implement me(basic score)
    root = add (root, key, value);
}

private Node add(Node x, K key, V value){
    if (x == null){
        return new Node(key, value); }
        int cmp = key.compareTo(x.key);
        if (cmp < 0){
            x.left = add(x.left, key, value);}
            else if (cmp > 0 ){
                x.right = add(x.right, key, value);}
                else if (cmp == 0){
                    x.value = value;} 
    return x;
}


public V get(K key) {
    Node x = root;
    while (x != null){
        int cmp = key.compareTo(x.key);
        if (cmp < 0){
            x = x.left;}
            else if (cmp > 0 ){
                x = x.right;}
               else if (cmp == 0){
                   return x.value;}
      }
    return null;
}


public K next(K key) {
amelia
  • 11
  • 4

1 Answers1

0
  1. You would need a private method to getNode of key
  2. Then you get successor of that node and return its value
  3. You should also update your "V get(K key)" method to use the getNode(K Key) method to avoid code duplication

I've written all 3 methods below

    private Node getNode(K key) {
        Node x = root;
        while (x != null){
            int cmp = key.compareTo(x.key);
            if (cmp < 0){
                x = x.left;
            } else if (cmp > 0 ) {
                x = x.right;
            } else if (cmp == 0){
                return x;
            }
          }
        return null;
    }

    public K next(K key) {
        Node x = getNode(key);
        if (x.right != null) {
            x = x.right;
            while (x.left != null) {
                x = x.left;
            }
            return x.key;
        }
        Node p = x.parent;
        while (p != null && p.right == x) {
            p = p.parent;
            x = x.parent;
        }
        return p.key;
    }

    public V get(K key) {
        Node x = getNode(key);
        return x==null?null:x.value;
    }
abhaybhatia
  • 599
  • 1
  • 7
  • 16
  • this is a stupid question, but it says it cannot find the symbol parent. Would I add that in my Node constructor? if so, how? so far, I have public Node(K key, V value) { this.key = key; this.value = value; – amelia Mar 31 '16 at 04:42
  • what is the "it" that says it cannot find parent. Where in the code is this occurring. The method next() is a part of your BST class right ?... and the inner class Node has a parent field defined ... so the next() method should be able to access the parent field – abhaybhatia Mar 31 '16 at 05:20
  • ah yes that's my problem I don't have the parent field defined, but I'm not quite sure how – amelia Mar 31 '16 at 15:39
  • do I simply just add "Node parent;" in the constructor class? – amelia Mar 31 '16 at 15:53
  • class Node { Node left; Node right; Node parent; KVPair kv; K key; V value; public Node(K key, V value) { this.key = key; this.value = value; } – amelia Mar 31 '16 at 17:27
  • also what does "return x==null?null:x.value;" mean in the get method? – amelia Mar 31 '16 at 17:27
  • Questions mark operator - http://stackoverflow.com/questions/10336899/what-is-a-question-mark-and-colon-operator-used-for – abhaybhatia Mar 31 '16 at 17:36
  • your node class looks fine - can you show me the line of code where you get the error message -- and also the exact wording of the error – abhaybhatia Mar 31 '16 at 17:38
  • I am no longer getting the error message! Is the last get method necessary for the entire next method to work? – amelia Mar 31 '16 at 17:44
  • you had a get method already which is similar in code to my getNode method ... since it is not a good idea to have duplicate code - i basically rewrote your get method to use the getNode method that I wrote. So this last get method is a replacement for the get method you have already – abhaybhatia Mar 31 '16 at 17:47
  • I have to keep the get method though:( with the same parameters – amelia Apr 01 '16 at 04:59
  • If you mean you have to keep the signature of the get method the same, then the signature is the same for the one you have and the one I wrote – abhaybhatia Apr 01 '16 at 05:37
  • If you mean you have to keep the implementation of the get method the same , then sure you can keep the original one and remove the one I wrote. Things will still work correctly but you'll have code duplication like I mentioned before – abhaybhatia Apr 01 '16 at 05:40
  • wait but yours returns a Node and mine returns the V – amelia Apr 01 '16 at 21:58
  • you get method and my get method both return V ... my getNode method return a Node – abhaybhatia Apr 02 '16 at 00:57
  • hey, if this answer solved your problem, accept it please – abhaybhatia Apr 02 '16 at 19:13