C++中的订单维护数据结构

Question

我正在寻找一种能够有效解决订单维护问题的数据结构.换句话说,我需要有效率

我找到了讨论这个问题的好文章:

算法非常有效(某些状态对于所有操作都是O(1)),但它们似乎并不是微不足道的,我想知道是否存在这些或类似数据结构的开源C++实现.

我已经看到了相关的主题,建议了所有操作的时间复杂度为O(log n)的一些更简单的方法,但在这里我正在寻找现有的实现.

如果在其他一些流行的语言中有一个例子,它也会很好,这样我至少可以在尝试自己实现它之前尝试它.

细节

我要去

注意

标准的订购容器(std :: set,std :: map)不是我想要的,因为它们会维护我的订单,但我需要自己订购元素.类似于我对std :: list的处理,但是位置比较是线性的,这是不可接受的.

Answer 1

如果您同时寻找易于实施和高效的解决方案，您可以使用平衡二叉搜索树（AVL 或红黑树）构建此结构。您可以按如下方式实施操作：

插入（X，Y） （插入X后立即Ÿ在总订单） -如果X没有右子集的右子X是Ÿ，否则让ž是树的根与最左边的节点X.正确的（这意味着最低的Z = X.right.left.left.left ......这不是NULL），并设置它的左子ž是ÿ。必要时平衡一下。您可以看到总复杂度为 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) 并且很容易实现。