Path conjecture for preorder access in binary search trees
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.
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.