>>>>> On Thu, 18 Oct 2007 23:31:51 +0200,
      Joerg Sonnenberger <joerg@britannica.bec.de> said:

> The third concern is generality. The only use of sys/tree.h in the
> kernel is uvm right now

arch/x86/x86/pmap.c uses <sys/tree.h> as well.
It does not use redblack tree, but splay tree though.

> The last concern is about memory usage.  If doing all the above, only two
> bits of storage are needed for each node (color and position). 

If you choose splay tree, you don't need even the two bits.
So, I think it's better to measure which tree algorithm is faster.
-- 
soda