5 ms·
My personal favorite of these is the Splay Tree[1]. I've never used it in production, but it's really simple to implement and reason about. Though my main exper
by nmwnmw 5y ago
My personal favorite of these is the Splay Tree[1]. I've never used it in production, but it's really simple to implement and reason about. Though my main experience was trying (and failing) to prove amortized bounds on the operations.
[1] https://en.wikipedia.org/wiki/Splay_tree https://en.wikipedia.org/wiki/Splay_tree
- jvanderbot 5y agoTarjan and Sleator are legends.
- 3PS 5y agoIf anything, the incredibly convoluted amortized analysis that goes into proving bounds on the cost of splay tree operations is perhaps more iconic than the actual splay tree data structure.