很多关于伪 LRU 算法的描述都涉及使用二叉搜索树，并在每次访问树时将标志设置为“指向远离”您正在搜索的节点。
这导致 LRU 的合理近似。然而，从描述来看，所有被认为是 LRU 的节点似乎都是叶节点。是否有一种伪 LRU 算法可以处理仍然表现良好的静态树，同时确定非叶节点是合适的 LRU 候选者？
编辑: 我已经使用 HashMap 和链表实现了 LRU。我有兴趣了解使用伪 lru 树的性能影响(尤其是在并发读取时)。 这就是为什么我特别询问伪 lru 树算法的原因，但我应该更清楚地说明这一点。
最佳答案
您始终可以使用旋转红黑树将内部节点下推到叶节点。
在这样做的同时保持树的平衡可能很困难。但是您确实可以选择下推哪个子树，所以也许并非不可能...
关于algorithm - 伪LRU树算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2759512/