title: Pseudo LRU tree algorithm
body: <p>A lot of descriptions of Pseudo LRU algorithms involve using a binary search tree, and setting flags to "point away" from the node you're searching for every time you access the tree.</p>
  
  <p>This leads to a reasonable approximation of LRU. However, it seems from the descriptions that all of the nodes deemed LRU would be leaf nodes. Is there a pseudo-LRU algorithm that deals with a static tree that will still perform reasonably well, while determining that non-leaf nodes are suitable LRU candidates?</p>
  
  <p>edit:
  I've already implemented an LRU using hashmaps and linkedlists. I'm interested in seeing the performance implications of using a pseudo lru tree (especially on concurrent reads).
  That is why I specifically asked about pseudo lru tree algorithms, but I should have made that clearer.</p>