Andre, * Andre Oppermann <andre_at_freebsd.org> wrote: > A splay tree is an interesting binary search tree with insertion, > lookup and removal performed in O(log n) *amortized* time. With > the *amortized* time being the crucial difference to other binary trees. > On every access *including* lookup it rotates the tree to make the > just found element the new root node. For all gory details see: > http://en.wikipedia.org/wiki/Splay_tree Even though a red-black tree is quite good since it guarantees a $2 \log n$ upperbound, the problem is that it's quite computationally intensive. Maybe it would be worth looking at other types of balanced trees? For example, another type of tree which has only $O(\log n)$ amortized insertion/removal/lookup time, but could already be a lot better in practice, is a Treap. Greetings, -- Ed Schouten <ed_at_80386.nl> WWW: http://80386.nl/
This archive was generated by hypermail 2.4.0 : Wed May 19 2021 - 11:40:07 UTC