Why does the printing stop with no errors?

user_18982610 0
Viewed 58

I try to print the result of boolean insert(K) in a for loop but after the first insertion the printing stops, that indicates the second insertion is not fully successful.

and inside method insert(K), the method "retrieves(K)" is called, to check if K has been already inserted.

    for (int i = 100; i > 0; i--) {
        System.out.println(m.insert(i +1, 22));
        System.out.println("dd");
        System.out.println(m.retrieve(i+1).first + ",,,"+m.retrieve(i+1).second);
        System.out.println(i + " insertion done");
        System.out.println("---------");
    }

and the result is

-------------------
true
dd
true,,,22
100 insertion done
---------
true
dd

After removing the "retrieves(K)" call in the insert() method, the print runs just fine, so i am assuming there is an issues with the method "retrieves(K)", and since there is no error + cpu usage is higher, it might be an infinite loop, the problem is, i don't see it.

here is the method "retrieves(K)"

    public Pair<Boolean, T> retrieve(K k) {

    Pair<Boolean, T> ff = new Pair<Boolean, T>(false, null);
    BSTMapNode<K, T> p = root;
    if(root==null) {
        return new Pair<Boolean,T>(false,null);
    }
    else
    while (p != null) {
        if (k.compareTo(p.key) == 0) {
            ff.first=true;
            ff.second=p.data;
            return new Pair<Boolean,T>(true,p.data);
        } else if (k.compareTo(p.key) < 0) {
            p = p.left;
        } else
            p = p.right;
    }
    return new Pair<Boolean,T>(false,null);
}

EDIT: added insert method

public boolean insert(K k, T e) {
    BSTMapNode<K, T> p = current;
    BSTMapNode<K, T> q = current;
    // ISSUE HERE
    if (retrieve(k).first == true) {
        current = q;
        return false;
        //
    }
    BSTMapNode<K, T> tmp = new BSTMapNode<K, T>(k, e);
    if (root == null) {
        root = current = tmp;
        return true;
    } else {
        if (k.compareTo(current.key) < 0)
            current.left = p;
        else
            current.right = p;
        current = p;
        return true;
    }
while-loop java
1 Answers

The issue is with the insert() method. When it is called for the second time, root is non-null, so execution gets into the else branch. There, it sets current.left = p with current == p, so p is now its own p.left. When the retrieve() method arrives at that node, it sets p = p.left which changes nothing, causing the infinite loop.

Your approach using a current node does not work. In insert(), you have to search the insertion position of the new node from the root every time, similar to what you do in retrieve(). Just keep going down until you reach a leaf. Then insert the new node there.

The code could look like this:

public boolean insert (K key, T value) {
    if (root == null) {
        root = new BSTMapNode<>(key, value);
        return true;
    } else {
        BSTMapNode<K, T> p = root;
        while (true) {
            if (key.compareTo(p.key) == 0) {
                return false; // Already in BST
            } else if (key.compareTo(p.key) < 0) {
                if (p.left == null) {
                    p.left = new BSTMapNode<>(key, value);
                    return true;
                } else {
                    p = p.left;
                }
            } else {    
                // Analogous for right sub-tree
            }
        }
    }
}
user_188508350
Related