Subject: Splay tree in pmap
To: None <tech-kern@netbsd.org>
From: Charles M. Hannum <abuse@spamalicious.com>
List: tech-kern
Date: 10/23/2003 17:13:17
I have to say that at first sight, using a splay tree in this fashion seems a 
bit strange.  You're inserting and looking up nodes in the tree in exactly 
one place -- there is no locality to be gained WRT looking up the same node 
more than once.  It seems to me that the real gain of the splay tree in this 
case is not from the rebalancing and self-optimization, but from the simple 
fact that on average it's somewhere closer to an AVL tree than a completely 
unbalanced tree, and so the average search time is better.  However, an AVL 
tree would bound the worst case time as well...