Lucier's split conjecture for online binary search trees
Lucier's split conjecture for online binary search trees
Let be an online binary search tree algorithm. Starting with any initial tree with elements, consider any sequence of splits. A split at an element deletes and produces two trees, whose elements are respectively smaller and larger than , each subject to further splitting. Split conjecture. The cost of splitting by any such sequence is . 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.