Search, Insert, Delete and DeleteLast operations in logN

Question

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

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.

Answer 1

Simply you can maintain a separate temporary pointer to the parent element of the most recently inserted node.This pointer can be used to delete the most recently inserted element.

I hope this may help!

Answer 2

Credit to @ThomasJungblut for bringing this solution up.

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;
}

Becomes this:

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

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.

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

EDITED thanks to @AlexeiShestakov

Answer 3

As you mentioned to get operations in O(log n) time.
So it can be done using AVL_TREE and a doubly linked list by maintaining a dualLink(biLink) b/w the node in Tree and it's corresponding node in doubly linked List.

Insertion will insert a node as mynode with SOME data with key as x and a link (reference to corresponding node as LN in double linked list) in Tree where the corresponding node of double linked list is a node with reference to that node of Tree and will be inserted at front of double linked list so that firstLink variable of double linked list will always refer to recently inserted element ::
1.) insert(x):: Insert data with key as x in AVL Tree.
First create a doubly linked node as LN
Now a Tree node as mynode
Now maintain a bilink between both nodes
2.) delete(x):: For deleteing a node from Tree
First find that node in Tree
Now delete that node's referenced doublyLinked node first and
than delete that node in Tree.
3.) deleteLast():: For This Simply Find the referenced node of Tree which is being refernced by first node of doublyLinked List (firstLink).
Now delete that node by calling delete(firstLink.mynode.key) function.
4.) search(x):: This is simple .

Time Complexity of All Above 4 Operations is in O(Logn) because all the operations performing on doublyLinkedList are in O(1) and AVL_TREE always gives O(Log n) Time Cost in above operations.

For AVL_TREE, download it from https://github.com/vivekFuneesh/AVL_TREE

Hope,This Will Help.
Also, I am habitual of coding in java so below code is in java language

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;
    }
  }

}  

Data Structure for AVL_TREE Node

/* 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;
}  

Data Structure For DoublyLinked List Node

/* A double LinkList node */  
class LinkNode{
  LinkNode left=null,right=null;
  node myNode=null;
}