[算法思考] 有什么好方法来维护一个指针让它始终指向一棵 splay tree 的最深节点

[littleMaple]

应用场景是要维护一棵有节点总数量限制的 splay tree。每次插入节点的时候，检查总数量有没有超出阈值，没有的话可以继续插入，如果超出了阈值，就需要删除掉另外一个节点来为新插入的节点腾出空间。现在我们面对的问题是如何选择哪个旧节点来删除掉。

我们知道 splay tree 的特点是越经常用到的节点往往越靠近树的顶端，而越不常访问的节点就埋在越深的底端。所以比较自然的想法是去删掉那个最不常用的节点，也就是删掉这棵树最深的节点。

Most naive try

按照最简单的实现方法，我们可以做一次广度优先搜索，找到位于层数最深的节点，然后删掉它。这样做需要遍历每个节点，其算法复杂度是与节点总数量成_线性_的。

如果用户从来不对 splay tree 发起删除命令，那么这棵树在满了之后的每次插入都会伴随一次删除最深节点的操作。插入操作复杂度大概是_对数_，而删除最深节点的操作复杂度是_线性_（至少需要我们遍历所有的节点），这意味着这样的策略会大大拖慢原本的整个插入操作。

所以我们想，有没有可能做出比较巧妙的设计，例如在插入或者删除操作的时候同时维护某些信息或者做某些副作用，从而可以让删除最深节点的时候复杂度降到对数。

First trial

第一种思路：有没有可能维护一个指针，让它始终指向最深的节点。在平常插入删除操作的时候顺便巧妙的更新这个指针。

Second trial

第二种思路：让每个节点附加存储一个「高度」信息，（也就是从它向下到某个叶子的最长的距离）。如果每个节点都存储了这样一个信息，我们将可以在对数时间找到最深节点。我们剩下需要做的就是设计如何在平常的插入删除操作中巧妙地维护每个节点的高度信息。

[GtDzx]

一时没想到怎么维护 splay 中最深的节点

不过针对你的需求我觉得可以另搞一个 LRU 来决定删除哪个节点(不一定是最深的)

[cnnblike]

第二个在 splay 的时候做一下不就完了？把最常用的扭上来之后更新被扭的那个节点的高度就成了

[cnnblike]

高度设定成 node.height = max{node.left.height, node.right.height} + 1, splay(x)的时候顺手维护，在取的时候就找一条路满足 node.height = node.[left/right]+1 就可以一路找到最长路了

[littleMaple]

@GtDzx 维护 LRU 的话要多一倍的空间占用呢，之所以限制 splay tree 的节点数量就是为了限制它的空间占用

[littleMaple]

@cnnblike 正解，这样做对插入操作和 splay 操作的原本复杂度都没影响，感谢你的建议 XD