7 votes

What are the must-read search trees paper?

Sleator-Tarjan '85 and Demaine et al '09 definitely belong on any such list. There is a lot of other recent work related to splay trees and dynamic optimality, for instance: Applications of forbidden ...
David Eppstein's user avatar
5 votes

Treewidth of two complete binary trees joined at their leaves

Indeed, this graph has treewidth 2. It's a well-known result in phylogenetics where the leaves are labelled. See Bryant, David, and Jens Lagergren. "Compatibility of unrooted phylogenetic trees is FPT....
steven kelk's user avatar
1 vote

Find an approximate argmax using only approximate max queries

Extended comment of an idea or two toward a lower bound. Let $B = \Theta(\log n)$, say (though the best choice may be different), and let $\{v_1,\dots,v_n\} = \{\frac{1}{n}B, \dots, \frac{n-1}{n}B, B\}...
usul's user avatar
  • 7,615
1 vote

Amortized analysis of red-black trees

You may need to look at this report: https://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf Each individual operation takes $O(\log n)$ but when you apply amortized ...
Hung Le's user avatar
  • 305

Only top scored, non community-wiki answers of a minimum length are eligible