Andre, * Andre Oppermann <an...@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 <e...@80386.nl> WWW: http://80386.nl/
pgppFv0Ft9fqs.pgp
Description: PGP signature
