Subject: Re: libkern's rb tree
To: Joerg Sonnenberger <firstname.lastname@example.org>
From: SODA Noriyuki <email@example.com>
Date: 10/19/2007 11:49:46
>>>>> On Fri, 19 Oct 2007 03:05:28 +0200,
Joerg Sonnenberger <firstname.lastname@example.org> said:
> Splay trees are also a lot worse for the CPU caches due to the constant
That's not always true, it depends on the access pattern of the
If there is high locality in the application, splay tree may be
more cache-friendly than redblack tree.
> The operations on splay trees are only cheap on average, individual
> operations can be O(n).
But usually that isn't a problem, because amortised cost is O(log(N)),
and average cost is often more cheaper than redblack tree.
> That makes it not very attractive for a number of important use
> cass. Splay trees are only attractive if a high locality of access is
> expected and IMO many cases just don't satisfy that property.
At least benchmarking is needed to determine which is better.