由网友(青春微凉不悲伤)分享简介：有什么可以支持以下操作O型最适合的数据结构（log n）的时间：What can be best suited data structure that supports the following operations in O(log n) time: search(x) finds the element wit...

有什么可以支持以下操作O型最适合的数据结构（log n）的时间：

What can be best suited data structure that supports the following operations in O(log n) time:

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

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

I know that a binary search tree can handle first three operations pretty good. But how to handle fourth query. If BST is not a good solution than also tell what can be best suited data structure for handling all four queries.

推荐答案

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

Credit to @ThomasJungblut for bringing this solution up.

首先，建立一个BST抱着你需要在树上的叶子信息。 这是自我解决了搜索，插入和放大器;删除的要求。 为了解决删除最近插入的元素的要求，我们添加到每个叶 $ P $光伏＆放大器的结构; 下一步字段，因此这样的：

First, build a BST to hold the information you need in the leaves of the tree. This in it self solves the search, insert & delete requirements. To address the "delete most recently inserted element" requirement we add to the structure of each leaf prev & next fields, so this:

struct leaf
{
    int key;
    INFO_STRUCT info;
}

成为本：

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

和除持有BST的根，也持叶*最后。每一个新的元素添加时，其指向之一，最后更新之前。

And except for holding the root of the BST, also hold leaf *last. Every time a new element is added, it point to the one before and last is updated.

注意：这除了只帮助找到所需项，删除本身需要的log（n）

Note: This addition only helps finding the requested item, the deletion itself takes log(n).

EDITED 由于@AlexeiShestakov

EDITED thanks to @AlexeiShestakov