搜索，插入，删除和logN个中操作DeleteLast [英] Search, Insert, Delete and DeleteLast operations in logN

问题描述

有什么可以支持以下操作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

这篇关于搜索，插入，删除和logN个中操作DeleteLast的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！