Saiyan February 2016

Caching in binary search trees

I have a program where I input keys and the position value from the input list into a red-black tree. If a key occurs more than once in the input array, the key is not inserted again into the tree; instead, the position value is updated.

For example, for the input list S E A R C H T R E E, the first time E is encountered, it is input and its position value is stored as 1 (position value starts at 0); the second time E is encountered in the list, it is not added again to the tree; only its position value is updated to 8. The third time E is encountered, its position value is updated to 9.

Throughout the program, I want to keep track of the last node that has been accessed, so that if the next key in the input list is the same as the previous one, I can access in constant time the node containing that key and modify the position value without having to go through the tree and search for the node containing that key to modify the position value. It is like a form of caching.

Is this possible?

Input is done through put method. I store the key of the last input but I have no idea how I can directly access the node containing that key without having to search the tree. Searching the tree would require a loop, which would not result constant time for accessing the node.

public class RedBlackTree<Key extends Comparable, Value> {

    private static final boolean RED = true;
    private static final boolean BLACK = false;
    private Node root;
    private int N; //number of nodes in RBT
    private Key latestKey; //most recently input key

    private class Node{
        private Key key; //key (data stored in node)
        private Value val; //sequence order (whether the key was input first (0), second (1), third (2), etc)
        private Node left, right; //links to left and right subtrees
        private boolean colour; //colour of node
        private int N; //subtree count

        public Node (Key key, Value val,        

Answers


Saiyan February 2016

I replaced private Key latestKey with private Node latest and made the following changes.

public void put(Key key, Value val){
    if ((latest != null) && (latest.key.compareTo(key) == 0)){
        latest.val = val;
        return;
    }
    root = put(root, key, val);
    root.colour = BLACK;
}

public Node put(Node x, Key key, Value val){
    if (x == null){
        N = N + 1;
        latest = new Node(key, val, RED, 1);
        return latest;
    }
    if (x != null){
        latest = x;
    }
    int cmp = key.compareTo(x.key); //compare key to be inserted with current key read
    //etc
}

Post Status

Asked in February 2016
Viewed 3,904 times
Voted 8
Answered 1 times

Search




Leave an answer