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.
References
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
No solutions have been posted yet.