伪LRU树算法

许多伪LRU算法的描述都涉及到使用二叉搜索树,以及在每次访问树时将标志设置为“指向”要搜索的节点。

这导致了LRU的合理近似。然而,从描述来看,所有被视为LRU的节点都将是叶节点。有没有一个伪LRU算法处理一个静态树,它仍然可以很好地执行,同时确定非叶节点是合适的LRU候选节点?

编辑: 我已经使用hashmaps和linkedlists实现了一个LRU。我对使用伪lru树(特别是并发读取)的性能影响很感兴趣。 这就是为什么我特别问伪lru树算法,但我应该让它更清楚。