logN中的搜索、插入、删除和DeleteLast操作
哪种数据结构最适合在O(log )时间内支持以下操作：
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不是一个好的解决方案，那么还可以告诉我们什么数据结构最适合处理所有四个查询。
回答 3
Stack Overflow用户
发布于 2015-06-15 18:57:03
感谢@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，编辑了
Stack Overflow用户
发布于 2015-06-15 19:24:51
简单地说，您可以维护一个指向最近插入的父元素的临时指针，node.This指针可用于删除最近插入的元素。
我希望这能有所帮助！
Stack Overflow用户
发布于 2015-06-16 00:19:15
正如您所提到的，要在O(log )时间内获得操作。
因此，可以使用AVL_TREE和双向链表来实现，方法是维护一个dualLink(biLink) b/w树中的节点和它在双向链表中的对应节点。
插入将在树中插入一个节点作为mynode，其中某些数据的关键字为x，并插入一个链接(在双向链表中将相应节点称为LN )，其中双向链表的对应节点是引用该树节点的节点，并将插入到双向链表的前面，以便双向链表的firstLink变量始终引用最近插入的元素 :：
1.)插入(X)：：在AVL树中插入关键字为x的数据。
首先创建一个双向链接的节点作为LN
现在，作为mynode的Tree节点
现在维护两个节点之间的双向链接
2.)delete(x):：用于从树中删除节点
首先在树中查找该节点
现在先删除该节点引用的doublyLinked节点，然后
然后在树中删除该节点。
3.)deleteLast():：为此，只需找到doublyLinked列表(firstLink)的第一个节点引用的树的引用节点。
现在通过调用delete(firstLink.mynode.key)函数删除该节点。
4.)search(x):：这很简单。
以上4种操作的时间复杂度均为O(Logn)，因为在doublyLinkedList上执行的所有操作的时间复杂度均为O(1)，而AVL_TREE在上述操作中的时间开销始终为O(Logn)。
对于AVL_TREE，请从https://github.com/vivekFuneesh/AVL_TREE下载
希望，这会有帮助的。
另外，我习惯用java编码，所以下面的代码是用java语言编写的。
class MyClass{
/* Create first and last reference to double link list */
static LinkNode firstLink=null,lastLink=null;
/* Create root of Complete BST i.e. AVL Tree */
static node rootAVL=null;
public static void main(String[] arg){
}
/*To remove most recently inserted element in O(Log n) ,just delete element referenced by firstLink.myNode*/
static void deleteLast(){
if(firstLink==null){System.out.println("EMPTY TREE");}
else{
deletenode(firstLink.myNode.key,rootAVL,rootAVL);
}
}
/* Insert into AVL Tree a node by maintaining a double reference to and fro b/w AVL Tree's node and corresponding doubly linked list node. */
/* Time Complexity:: O(Log n) */
static void insert(int key,int data){
LinkNode LN=new LinkNode();
node mynode=new node();
mynode.key=key;
mynode.data=data;
mynode.myLink=LN;
LN.myNode=mynode;
/* Insert double linklist node at first*/
/* Time Complexity:: O(1) */
insertLink(LN);
/* Now insert mynode in AVL Tree using mynode.key as key. */
}
/* delete node from AVL Tree in Time Cost ::O(Log n)*/
static void deletenode(int key,node node,node root){
if(node!=null){
if(node.key==key){
/* First remove it's corresponding doublyLinkednode */
/* Time Complexity:: O(1)*/
deleteLink(node.myLink);
/*Now delete this node in Time Complexity:: O(Log n)*/
}
else if(key<node.key){
deletenode(key,node.left,node);
}
else{deletenode(key,node.right,node);}
}
}
/* Your delete(x) function in O(Log n) */
static void delete(int key){
if(rootAVL!=null){
node MYNODE=null;
/* First find that node with key as key then::delete doublylinked node corresponding to that node then:: delete that. */
deletenode(key,rootAVL,rootAVL);
}
else System.out.println("EMPTY_TREE");
}
/* Delete LinkNode ln in Time Cost Of O(1) */
static void deleteLink(LinkNode ln){
if(firstLink==null){
System.out.println("ERROR");System.exit(1);
}
else{
if(firstLink==lastLink){
firstLink.myNode=null;
firstLink=lastLink=null;
}
else if(ln==lastLink){
ln.left.right=null;
ln.myNode=null;
lastLink=ln.left;
ln.left=null;
}
else if(ln==firstLink){
firstLink.right.left=null;
firstLink.myNode=null;
firstLink=firstLink.right;
firstLink.right=null;
}
else{
ln.left.right=ln.right;
ln.right.left=ln.left;
ln.right=ln.left=null;
}
}
}
/*Insert at First in O(1) so that recently inserted element will always be referenced by variable firstLink */
static void insertLink(LinkNode ln){
if(firstLink==null){
lastLink=firstLink=ln;
}
else{
firstLink.left=ln;
ln.right=firstLink;
firstLink=ln;
}
}
} AVL_TREE节点的数据结构
/* An AVL_TREE Node */
class node{
int key=0;
int data=0;
int height=0;/* For maintaining height in AVL Tree*/
node left=null,right=null;
LinkNode myLink=null;
} DoublyLinked列表节点的数据结构
/* A double LinkList node */
class LinkNode{
LinkNode left=null,right=null;
node myNode=null;
} https://stackoverflow.com/questions/30843120
复制相似问题
腾讯云开发者
