algorithm - 一种可按插入顺序和数量级遍历的数据结构

Question

有没有一种数据结构可以同时遍历插入顺序和数量级O(n)，插入和删除至多O(log(n))？

换句话说，给定元素 5、1、4、3、2(按此顺序插入)，它可以遍历为 1,2,3,4,5 或 5,1,4,3,2 在 O(n) 时间内。

当然我可以使用数组并在遍历之前简单地对其进行排序，但这需要 O(n*log(n)) 预遍历步骤。另外，我可以使用多链表来实现 O(n) 的遍历，但在这种情况下，插入和删除操作也需要 O(n)，因为我不能保证最新的元素一定是最大的。

如果存在这样的数据结构，请为它提供一个正式名称，以便我进一步研究它，或者如果没有，请提供一个简短的表面描述。

谢谢

Answer 1

一个也允许次线性删除的解决方案是构建一个数据结构D，它使用链表D.L按插入顺序遍历，以及一个排序树D.T 为按数量级遍历。但是如何将它们链接起来以在亚线性时间内额外实现删除操作呢？诀窍在于 D.T 应该不存储值，而只是对相应链表元素的引用 D.L.

插入:在时间 O(1) 内附加到 D.L，并在时间 O(日志(n))。 D.T 中的任何比较当然是在引用值上进行的，而不是由引用本身进行的)

按插入顺序(或向后)遍历:简单地在时间 O(n) 内线性遍历 D.L

按数量级(或向后)遍历:通过树遍历在时间 O(n) 内简单地遍历 D.T

删除:首先在时间 O(log n) 内找到并删除 D.T 中的元素，这也为您提供了对 D.L 的正确元素引用，所以它可以在时间 O(1) 内从 D.L 中删除。