On Mon, Mar 9, 2015 at 7:59 PM, vax mzn wrote: > w.r.t, https://gcc.gnu.org/wiki/Speedup_areas where we want to improve the > performance of splay trees. > > The function `splay_tree_node splay_tree_lookup (splay_tree, splay_tree_key);' > updates the nodes every time a lookup is done. > > IIUC, There are places where we call this function in a loop i.e., we lookup > different elements every time. > e.g., > In this exaple we are looking for a different `t' in each iteration.
If that's really true, then a splay tree is a horrible choice of data structure. The splay tree will simply degenerate to a linked list. The right thing to do would be, not to "break" one of the key features of splay trees (i.e. the latest lookup is always on top), but to use another data structure. Ciao! Steven
