我有两个关于splay树的问题：
1. Deletion of a node
我正在使用的书中说明了以下内容：''当删除密钥k时，我们展示了被删除的节点w的父节点 . 删除8的示例：
但是，我正在做的是：如果删除的节点不是根节点，我将其展开（到根节点），删除它，并显示左子树的最右边节点 . 但是因为在这种情况下，删除的节点是根，我只是删除它并立即展开左子树的最右边节点 . 像这样：
这种方式也正确吗？请注意，它完全不同（就像我的根是7而不是像我的书所说的那样） .
2. In which order are the values in a splay tree inserted?
是否有可能“获得”上面左侧树例中插入的值的顺序？换句话说，这棵树是如何形成的（插入节点的顺序是生成下一棵树） . 有没有办法解决这个问题？
1 回答
重新删除节点：两种算法都是正确的，并且都需要时间O（log n）分摊 . 飞节点成本为O（log n） . 在根成本附近创建新链接O（log n） . Splay树在访问和重组方面具有很大的灵活性 .
重新构建插入序列：假设插入方法是通常的不 balancer 插入和展开，那么根是最后一次插入 . 不幸的是，一般来说，有几种方法可以展示给根 . 对明显的O（n！poly（n）） - 时间强力算法的渐近改进是使用memoization进行穷举搜索，其成本为O（4 ^ n poly（n）） .