Caching in binary search trees -

i have program input keys , position value input list red-black tree. if key occurs more once in input array, key not inserted again tree; instead, position value updated.

for example, input list s e r c h t r e e, first time e encountered, input , position value stored 1 (position value starts @ 0); second time e encountered in list, not added again tree; position value updated 8. third time e encountered, position value updated 9.

throughout program, want keep track of last node has been accessed, if next key in input list same previous one, can access in constant time node containing key , modify position value without having go through tree , search node containing key modify position value. form of caching.

is possible?

input done through put method. store key of last input have no idea how can directly access node containing key without having search tree. searching tree require loop, not result constant time accessing 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 input key      private class node{         private key key; //key (data stored in node)         private value val; //sequence order (whether key input first (0), second (1), third (2), etc)         private node left, right; //links left , right subtrees         private boolean colour; //colour of node         private int n; //subtree count          public node (key key, value val, boolean colour, int n){             this.key = key;             this.val = val;             this.colour = colour;             this.n = n;         }     }      //get sequence order of given key; start searching @ root     public value get(key key){         return get(root, key);     }      //get position of given key; start searching @ subtree rooted @ x     public value get(node x, key key){         int cmp;         while (x != null){             cmp = key.compareto(x.key); //compare key being searched current key read             if (cmp < 0){ //key being searched smaller current key                 x = x.left; //go left child of current key             }else if (cmp > 0){ //key being searched larger current key                 x = x.right; //go right child of current key             }else{ //key being searched equal current key                 return x.val; //return sequence order             }         }         return null; //given key not found     }      //insert key-value pair; start @ root     //if key present, overwrite old value new value     //therefore, if key occurs @ several positions in input list, last position 1 saved     public void put(key key, value val){         if (latestkey != null && (latestkey.compareto(key) == 0)){             //how find node containing key?         }         root = put(root, key, val);         root.colour = black;         latestkey = key;     }      //insert key-value pair in subtree rooted @ x     public node put(node x, key key, value val){         if (x == null){ //do standard insert, red link parent             n = n + 1;             return new node(key, val, red, 1);         }         int cmp = key.compareto(x.key); //compare key inserted current key read         if (cmp < 0){ //key inserted smaller current key             x.left = put(x.left, key, val); //recursive call insert key-value pair in subtree rooted @ current key's left child         }else if (cmp > 0){ //key inserted larger             x.right = put(x.right, key, val); //recursive call insert key-value pair in subtree rooted @ current key's right child         }else{ //key inserted current key read             x.val = val; //overwrite value (store last position now)         }          //fix right-leaning links         if (isred(x.right) && !isred(x.left)){ //right-leaning red link needs rotated lean left             x = rotateleft(x);         }         if (isred(x.left) && isred(x.left.left)){ //rotate right node 2 left-leaning red links             x = rotateright(x);         }         if (isred(x.left) && isred(x.right)){ //flips colours pass red link tree (when passing 4-node)             flipcolours(x);         }         x.n = size(x.left) + size(x.right) + 1;         return x;     }      //other methods... } 

i replaced private key latestkey private node latest , made 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 inserted current key read     //etc }