Examining the VM splay tree effectiveness

[Ed Schouten]

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/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 196 bytes
Desc: not available
Url : http://lists.freebsd.org/pipermail/freebsd-hackers/attachments/20101001/f0436daa/attachment.pgp