4 ms·
Splay tree – binary search tree with faster repeated access
- dj-wonk 12y agoI found splay trees because Wikipedia mentioned them as being particularly useful for discrete-event simulations: http://en.wikipedia.org/wiki/Discrete_event_simulation http://en.wikipedia.org/wiki/Discrete_event_simulation > The pending event set is typically organized as a priority queue, sorted by event time. That is, regardless of the order in which events are added to the event set, they are removed in strictly chronological order. Several general-purpose priority queue algorithms have proven effective for discrete-event simulation, most notably, the splay tree. More recent alternatives include skip lists, calendar queues, and ladder queues.
- tptacek 12y agoSplay trees are much easier to code than red-black trees, but have the very annoying property of being mutable even in pure read workloads.
- dj-wonk 12y agoGreat point. Perhaps it is important to distinguish "logical" and "physical" mutability. I say this because reading a splay tree doesn't change the return value in the future even though it changes the internals.
- dj-wonk 12y agoHere is a previous HN discussion about splay trees: https://news.ycombinator.com/item?id=1370986 https://news.ycombinator.com/item?id=1370986