algorithm - 伪LRU树算法

Question

很多关于伪 LRU 算法的描述都涉及使用二叉搜索树，并在每次访问树时将标志设置为“指向远离”您正在搜索的节点。

这导致 LRU 的合理近似。然而，从描述来看，所有被认为是 LRU 的节点似乎都是叶节点。是否有一种伪 LRU 算法可以处理仍然表现良好的静态树，同时确定非叶节点是合适的 LRU 候选者？

编辑:我已经使用 HashMap 和链表实现了 LRU。我有兴趣了解使用伪 lru 树的性能影响(尤其是在并发读取时)。这就是为什么我特别询问伪 lru 树算法的原因，但我应该更清楚地说明这一点。

Answer 1

您始终可以使用旋转红黑树将内部节点下推到叶节点。

在这样做的同时保持树的平衡可能很困难。但是您确实可以选择下推哪个子树，所以也许并非不可能...