Purely Functional Worst Case Constant Time Catenable Sorted Lists

Gerth Stølting Brodal, Christos Makris, and Kostas Tsichlas

In Proc. 14th Annual European Symposium on Algorithms, volume 4168 of Lecture Notes in Computer Science, pages 172-183. Springer Verlag, Berlin, 2006.

Abstract

We present a purely functional implementation of search trees that requires O(log n) time for search and update operations and supports the join of two trees in worst case constant time. Hence, we solve an open problem posed by Kaplan and Tarjan as to whether it is possible to envisage a data structure supporting simultaneously the join operation in O(1) time and the search and update operations in O(log n) time.

Copyright notice

© Springer-Verlag Berlin Heidelberg 2006. All rights reserved.

Online version

esa06trees.pdf (137 Kb)

DOI

10.1007/11841036_18

Slides

esa06trees.pdf (72 Kb), esa06trees.ppt (169 Kb)

BIBT_EX entry

@incollection{esa06trees,
  author = "Gerth Stølting Brodal and Christos Makris and Kostas Tsichlas",
  booktitle = "Proc. 14th Annual European Symposium on Algorithms",
  doi = "10.1007/11841036_18",
  isbn = "978-3-540-38875-3",
  pages = "172-183",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "Purely Functional Worst Case Constant Time Catenable Sorted Lists",
  volume = "4168",
  year = "2006"
}