Path conjecture for preorder access in binary search trees
Let be an online binary search tree algorithm. Starting with any initial tree with elements, let be the preorder sequence of a binary search tree that is a path. Path conjecture. The cost of accessing is . The source states that this conjecture is implied by the deque, traversal, and split conjectures, making it an easier common consequence; 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
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.