Previous results WS Ref Insert/ Search(e) Predecessor/Additional prop. Delete(e) Successor(e) words M1986 O(log2 n O(log2 n) None FGMP 2002 O(log 2 n/loglog n)O(log2 n/ loglog n None FG2006 O(log n)amor. O(log n) O(log n) one FG2003 O(log n) O(log n O(log n) None I2001+o(0gn) O(log le O(log le* o(n) BHM 2009 o(log n) O(log /e) exp O(log n O(loglog n) BHM 2009 O(log n) O(log /) exp O(log le*)exp. O(vn) BKT O(log n) O(log le) O(log n) None 2010 BK2011 o(log n) O(log min(p(ey ler Iste)) o(log le+) None e"is the predecessor/successor of e earmarks undforskringsfond Casper Kejlberg-Rasmussen maDalgo- 6/16 UNIVERSIT CENTER FOR MASSIVE DATA ALGORITHMICSCasper Kejlberg-Rasmussen 6/16 Previous Results Ref. WS prop. Insert/ Delete(e) Search(e) Predecessor/ Successor(e) Additional words M1986 - O(log2 n) O(log2 n) - None FGMP 2002 - O(log2 n/loglog n) O(log2 n/ loglog n) - None FG2006 - O(log n) amor. O(log n) O(log n) None FG2003 - O(log n) O(log n) O(log n) None I2001 + O(log n) O(log le) O(log le*) O(n) BHM 2009 + O(log n) O(log le) exp. O(log n) O(loglog n) BHM 2009 + O(log n) O(log le) exp. O(log le*) exp. O(√n) BKT 2010 + O(log n) O(log le) O(log n) None BK2011 + O(log n) O(log min(lp(e), le, ls(e))) O(log le*) None e * is the predecessor/successor of e