我正在寻找一种可以有效解决 Order-maintenance problem 的数据结构.换句话说,我需要高效地
- 插入(在中间),
- 删除(在中间),
- 比较容器中元素的位置。
我找到了讨论这个问题的好文章:
- Two Algorithms for Maintaining Order in a List ,
- Two Simplified Algorithms for Maintaining Order in a List .
算法非常有效(对于所有操作,某些状态为 O(1)),但它们似乎并不简单,我想知道是否有这些或类似数据结构的开源 C++ 实现.
我见过 related topic ,建议了一些时间复杂度为 O(log n) 的更简单的方法,用于所有操作,但这里我正在寻找现有的实现。
如果有其他一些流行语言的示例,那也很好,这样我至少可以在尝试自己实现之前进行试验。
详情
我要去
- 维护一个指向对象的指针列表,
- 有时我需要更改对象的顺序(删除+插入),
- 给定一个对象子集,我需要能够快速对它们进行排序并以正确的顺序处理它们。
注意
标准排序容器(std::set、std::map)不是我想要的,因为它们会为我维持秩序,但我需要自己订购元素。类似于我对 std::list 所做的,但位置比较将是线性的,这是 Not Acceptable 。
最佳答案
如果您同时在寻找易于实现且高效的解决方案,您可以使用平衡二叉搜索树(AVL 或红黑树)构建此结构。您可以按如下方式实现操作:
- insert(X, Y)(按总顺序在 Y 之后立即插入 X) - 如果为 X 没有右 child 设置X的右 child 为Y,否则让Z为 Root过的树的最左边节点X.right(表示最低的 Z = X.right.left.left.left... 不为 NULL)并将其设置为 的左 child Z 为 Y。必要时保持平衡。您可以看到总复杂度为 O(log n)。
- delete(X) - 只需从树中删除节点 X 即可。复杂度 O(log n)。
- compare(X,Y) - 找到从 X 到根的路径以及从 Y 到根的路径。您可以从这两条路径中找到 Z ,即 X 和 Y 的最低共同祖先。现在,您可以比较 X 和 Y 取决于它们是在 Z 的左子树还是右子树(它们不能从那时起,Z 将不再是它们的最低共同祖先)。复杂度 O(log n)。
所以你可以看到这种实现的优点是所有操作的复杂度都是 O(log n) 并且很容易实现。
关于c++ - C++中的订单维护数据结构,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32839578/