Greedy BST is O(log log n)-competitiveResearch Paper
A binary search tree (BST) on the keys answers a sequence of searches. A balanced tree costs per search, but an adaptive tree that reshapes itself can do much better on structured sequences: repeated requests, sequential scans, requests clustered in time or in key order. The dynamic optimality problem asks whether a single online BST…