RB tree improvements

[davidtgoldblatt]

A few things I thought of in preparing #2042.

• After Red black tree summarize/filter functionality #2042, there's some duplication in the filtered/unfiltered variants of searching and whatnot. This can be eliminated by pulling the filtered implementation into an always-inlined version, with the unfiltered version passing in filters that always return true. This should be optimizable into the original versions, except for iteration (which does take a minor hit). Or, we could not force-inline the implementation, and just have the non-filtered version call the filtered version directly, and take some function-call overhead. Red-black tree pathways are slow anyway, so we may consider code size more important.
• In various parts of the insert/remove pathways, we'll need the color of a node, but not anything else about the node (to decide whether or not to rotate), and, we'll take a cache miss to get it. Instead, we can store a node's color in its parent (i.e. steal a bit from each of the two child pointers in a node; each will store that child's color). In that case, when we don't have to take a cache miss in the nodes where we don't rotate.
• I wonder if a more standard rbtree algorithm might serve us better in todays world.
  -- Most of the benchmarking I know about of the rbtrees was done in cache-friendly situations, but in real programs we should expect to take a cache miss on every rbtree node traversal. Things like rotations to stay left-leaning are a cost we don't necessarily have to pay, but currently do.
  -- Parent pointers? RB nodes no longer live in any space-sensitive data structures; being able to do often-O(1) summary updates or removals may be more valuable in the future.

[jasone]

Re: typical red-black trees with parent pointers, they're a reasonable alternative if structure space isn't a critical design consideration. The most important performance differences between implementations are due to 1) fixup cost (lazy two-pass is better than conservative single-pass), and 2) short-circuit unwind if lazy two-pass is done early.