Lucier's split conjecture for online binary search trees

Let A{\mathcal{A}} be an online binary search tree algorithm. Starting with any initial tree TT with nn elements, consider any sequence of nn splits. A split at an element xx deletes xx and produces two trees, whose elements are respectively smaller and larger than xx, each subject to further splitting. Split conjecture. The cost of splitting TT by any such sequence is O(n)O(n). This is one of the classical deque-, traversal-, and split conjectures for splay trees; its status is not resolved in the supplied source.

Sources & referencesView supporting material

Primary source

Parinya Chalermsook, Mayank Goswami, Laszlo Kozma, Kurt Mehlhorn and Thatchaphol Saranurak, “Pattern-avoiding access in binary search trees”, arXiv:1507.06953 (2015).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.