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

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

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

Most naive try

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

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

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

First trial

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

Second trial

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