Date: Fri, 1 Oct 2010 20:28:56 +0200 From: Ed Schouten <ed@80386.nl> To: Andre Oppermann <andre@freebsd.org> Cc: freebsd-hackers <freebsd-hackers@freebsd.org>, freebsd-current@freebsd.org Subject: Re: Examining the VM splay tree effectiveness Message-ID: <20101001182856.GF87427@hoeg.nl> In-Reply-To: <4CA4BCD2.4070303@freebsd.org> References: <4CA4BCD2.4070303@freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
--bNOIqPvWVsuhXMpy Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Andre, * Andre Oppermann <andre@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, --=20 Ed Schouten <ed@80386.nl> WWW: http://80386.nl/ --bNOIqPvWVsuhXMpy Content-Type: application/pgp-signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.16 (FreeBSD) iEYEARECAAYFAkymKGgACgkQ52SDGA2eCwVl5wCdHzG4YpvaU5cPp4uU0BB5fUM8 rd4An2KVKMItdIuTQVBkEopnKVc8/X+B =WSCh -----END PGP SIGNATURE----- --bNOIqPvWVsuhXMpy--
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20101001182856.GF87427>