3 ms·
with append-only data structures, you could turn the fact that you rewrite the path from the node to the root to your advantage and rebalance. This means you ab
by toolslive 3y ago
with append-only data structures, you could turn the fact that you rewrite the path from the node to the root to your advantage and rebalance. This means you abandon the "balanced" property and use update statistics to get an optimal shape. Who cares about the length of paths to parts of the tree you never visit?
- kragen 3y agothis is how splay trees work, but you might actually care about the lengths of paths to parts of the tree you rarely visit; for many real systems, worst-case response time is more important than throughput