On 10/01/10 20:28, Ed Schouten wrote: > 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.
How many elements are held in vm_map trees? From the source it looks like one tree with all pages in the system and then one per-process? Trees have very varied real-time characteristics, e.g.: http://attractivechaos.awardspace.com/udb.html http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.6795&rep=rep1&type=pdf _______________________________________________ freebsd-hackers@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-hackers To unsubscribe, send any mail to "freebsd-hackers-unsubscr...@freebsd.org"
