algorithm - logN 中的搜索、插入、删除和删除最后操作

Question

什么是最适合在 O(log n) 时间内支持以下操作的数据结构:

search(x) finds the element with key x 
insert(x) insert an element with a key x    
delete(x) delete an element with a key x    
deleteLast() removes the most recently inserted element

我知道二叉搜索树可以很好地处理前三个操作。但是如何处理第四个查询。如果 BST 不是一个好的解决方案，那么还要告诉我们什么是最适合处理所有四个查询的数据结构。

Answer 1

感谢@ThomasJungblut 提出了这个解决方案。

首先，构建一个 BST 以在树叶中保存所需的信息。
这本身就解决了搜索、插入和删除的需求。
为了满足“删除最近插入的元素”的要求，我们添加到每个叶 prev 和 next 字段的结构，因此:

struct leaf
{
    int key;
    INFO_STRUCT info;
}

变成这样:

struct leaf
{
    int key;
    INFO_STRUCT info;
    leaf *prev;
    leaf *next;
}

并且除了保存 BST 的根之外，还保存leaf *last。每次添加新元素时，它都会指向之前的元素，并且 last 会更新。

注意:此添加仅有助于查找请求的项目，删除本身需要 log(n)。

已编辑感谢@AlexeiShestakov