News for hackers. Stuff that matters.
Re:What are the lesser known but cool data structures? by pjscott on Saturday May 22, 2010 @11:32PM (#1371704)
Heh; it hit me that way, too. It seems obvious in retrospect. I found that this page has a nice mini-introduction:

http://www.imada.sdu.dk/~kslarsen/RelBal/

If requests that use a red-black tree tend to come in bursts, then you can probably get speedups by deferring rebalancing for idle periods, even single-threaded. That's pretty darn cool. I would like to see some programming language runtime that watched rb-tree access patterns and decided if this would be a good idea at runtime.

There are no comments on this comment yet.