Кэширование в деревьях двоичного поиска

Question

У меня есть программа, в которой я вводю ключи и значение позиции из списка ввода в красно-черное дерево. Если во входном массиве ключ встречается более одного раза, ключ не вводится снова в дерево; вместо этого значение позиции обновляется.

Например, для списка входных сигналов S E A R C H T R E E, в первый раз, когда E встречается, он вводится и его значение позиции сохраняется как 1 (значение позиции начинается с 0); второй раз, когда E встречается в списке, он не добавляется снова к дереву; только его значение позиции обновляется до 8. В третий раз встречается E, его значение позиции обновляется до 9.

В течение всей программы я хочу отслеживать последний доступ к узлу, следующая клавиша во входном списке такая же, как и предыдущая, я могу получить доступ в постоянное время к узлу, содержащему этот ключ, и изменить значение позиции без необходимости проходить через дерево и искать узел, содержащий этот ключ, для изменения значения позиции , Это похоже на кеширование.

Возможно ли это?

Ввод выполняется с помощью метода меток. Я сохраняю ключ последнего ввода, но я понятия не имею, как я могу напрямую обращаться к узлу, содержащему этот ключ, без необходимости поиска в дереве. Поиск в дереве потребует цикла, который не приведет к постоянному времени для доступа к узлу.

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, boolean colour, int N){ 
      this.key = key; 
      this.val = val; 
      this.colour = colour; 
      this.N = N; 
     } 
    } 

    //get sequence order of given key; start searching at root 
    public Value get(Key key){ 
     return get(root, key); 
    } 

    //get position of given key; start searching at subtree rooted at x 
    public Value get(Node x, Key key){ 
     int cmp; 
     while (x != null){ 
      cmp = key.compareTo(x.key); //compare key being searched for with current key read 
      if (cmp < 0){ //key being searched for is smaller than current key 
       x = x.left; //go to left child of current key 
      }else if (cmp > 0){ //key being searched for is larger than current key 
       x = x.right; //go to right child of current key 
      }else{ //key being searched for is equal to current key 
       return x.val; //return sequence order 
      } 
     } 
     return null; //given key not found 
    } 

    //insert key-value pair; start at root 
    //if key already present, overwrite old value with new value 
    //therefore, if a key occurs at several positions in input list, last position is the one saved 
    public void put(Key key, Value val){ 
     if (latestKey != null && (latestKey.compareTo(key) == 0)){ 
      //how to find the node containing that key? 
     } 
     root = put(root, key, val); 
     root.colour = BLACK; 
     latestKey = key; 
    } 

    //insert key-value pair in subtree rooted at x 
    public Node put(Node x, Key key, Value val){ 
     if (x == null){ //do standard insert, with red link to parent 
      N = N + 1; 
      return new Node(key, val, RED, 1); 
     } 
     int cmp = key.compareTo(x.key); //compare key to be inserted with current key read 
     if (cmp < 0){ //key to be inserted is smaller than current key 
      x.left = put(x.left, key, val); //recursive call to insert key-value pair in subtree rooted at current key's left child 
     }else if (cmp > 0){ //key to be inserted is larger 
      x.right = put(x.right, key, val); //recursive call to insert key-value pair in subtree rooted at current key's right child 
     }else{ //key to be inserted is current key read 
      x.val = val; //overwrite value (store last position up to now) 
     } 

     //fix any right-leaning links 
     if (isRed(x.right) && !isRed(x.left)){ //right-leaning red link that needs to be rotated to lean to the left 
      x = rotateLeft(x); 
     } 
     if (isRed(x.left) && isRed(x.left.left)){ //rotate right a node with two left-leaning red links 
      x = rotateRight(x); 
     } 
     if (isRed(x.left) && isRed(x.right)){ //flips colours to pass a red link up the tree (when passing 4-node) 
      flipcolours(x); 
     } 
     x.N = size(x.left) + size(x.right) + 1; 
     return x; 
    } 

    //other methods... 
} 

Answer 1

я заменил private Key latestKey с private Node latest и сделал следующие изменения.

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 
}