algorithm - Splay Trees中节点的插入和删除

Question

我有 2 个关于八角树的问题:

<强>1。删除节点

我正在使用的书是这样说的:''当删除键 k 时，我们展开被删除的节点 w 的父节点。删除 8 的示例:

但是，我正在做的是:如果删除的节点不是根节点，我展开它(到根节点)，删除它，然后展开左子树最右边的节点。但由于在这种情况下，被删除的节点是根节点，我只是将其删除并立即展开左子树的最右侧节点。像这样:

这种方式是否也正确？请注意，它是完全不同的(就像我的根是 7 而不是我书中所说的 6)。

<强>2。 splay 树中的值是按什么顺序插入的？

是否可以“获取”上面左树示例中插入的值的顺序？换句话说，这棵树是如何制作的(按照什么顺序插入节点来生成下面的树)。有办法解决这个问题吗？

Answer 1

重新删除一个节点:两种算法都是正确的，并且都需要时间 O(log n) 摊销。展开一个节点的成本为 O(log n)。在根附近创建一个新链接的成本为 O(log n)。 Splay 树在访问和重组方面具有很大的灵 active 。

重新重构插入顺序:假设insert方式是通常的非平衡insert和splay，那么root就是最后插入的。不幸的是，一般来说，它可以通过多种方式传播到根部。明显的 O(n!poly(n)) 时间蛮力算法的渐近改进是使用内存进行穷举搜索，其成本为 O(4^n poly(n))。