Red-black trees revisited

t-t-travails.blogspot.com

17 points·kinetik··4 comments

My current favourite balanced tree is the treap:

http://en.wikipedia.org/wiki/Treap

In a treap the shape of the tree is uniquely determined by it being heap-ordered according to a random number associated with each node, in addition to the standard search tree ordering.

The various operations are fast and simple to implement. For example, deletion is as simple as rotating the node in question down until it is a leaf, then removing it. The rotations only need to preserve heap ordering, a much simpler invariant than the red/black one.

The standard description of the treap calls for a field in each node containing a random number, but you can eliminate that by just hashing the address of the node. That's what I did in GSequence in glib (http://git.gnome.org/browse/glib/tree/glib/gsequence.c).

For simplicity in implementation but guaranteed upper bounds I highly recommend AA-trees.

WikiPedia: http://en.wikipedia.org/wiki/AA_tree

Original paper: http://user.it.uu.se/~arnea/ps/simp.pdf

Tutorial giving intuition for this data structure: http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_t...

Other cool balanced trees: rank-balanced trees [1], which have O(1) amortized insertion, deletion, and rebalancing, and ravl trees [2], which do not rebalance on deletion in hopes that insertions will happen soon and seem to rotate fewer times than both red-black trees and rank-balanced trees in experiments.

[1]: http://www.cs.princeton.edu/~sssix/papers/rb-trees.pdf (2009)

[2]: http://www.cs.princeton.edu/~sssix/papers/ravl-trees.pdf (2010)

Wouldn't it be more profitable, in terms of real-world performance, to adapt B-trees to maximize locality in CPU data caches? (One could also apply stochastic optimization to a B-tree based algorithm to reduce the number of operations on delete.)

Reply on news.ycombinator.com