在O（logn）中添加、删除和插入元素

Question

我们被要求创建一个在O（logn）中最坏情况下运行的算法

该算法由3个函数组成：getmin（）；getmax（）；添加（）

第一个从堆栈中弹出最小的元素，并返回它；getmax从堆栈中弹出最大的元素并返回它；在堆栈上添加put元素。

我在想一个RB树；但我意识到这很难由我自己实现（从零开始）。

还有其他树或数据结构实现起来不那么复杂，并且在O（logn）中运行？

我可以只使用基本的python操作（即仅列表，...）




Answer 1

我建议来一杯Treap。在我看来，这是最容易实现的平衡二叉搜索树，因为你只需要2个基本的旋转。

要搜索给定的键值，请在二元搜索树中应用标准的二元搜索算法，忽略优先级。

要将新密钥x插入到treap中，请为x生成随机优先级y。在树中对x进行二进制搜索，并在叶子位置创建一个新节点，其中二进制搜索确定x的节点应该存在。然后，只要x不是树的根，并且优先级数大于其父z，则执行树旋转，以反转x和z之间的父子关系。

要从treap中删除节点x，如果x是树的叶子，只需将其删除。如果x有一个子z，则从树中删除x，并使z成为x的父对象的子对象（如果x没有父对象，则使z成为树的根对象）。最后，如果x有两个子对象，则按排序顺序将其在树中的位置与其直接后续子对象z的位置交换，从而产生前面的一种情况。在最后一种情况下，交换可能违反z的堆排序属性，因此可能需要执行额外的旋转来恢复此属性。

获取最小值和最大值可以通过从根向左移动以获取最小值，并向右移动以获取最大值来完成。