Open thread, September 4 - September 10, 2017

Thomas

If it's worth saying, but not worth its own post, then it goes here.

Notes for future OT posters:

1. Please add the 'open_thread' tag.

2. Check if there is an active Open Thread before posting a new one. (Immediately before; refresh the list-of-threads page before posting.)

3. Open Threads should start on Monday, and end on Sunday.

4. Unflag the two options "Notify me of new top level comments on this article" and "Make this post available under..." before submitting

If it's worth saying, but not worth its own post, then it goes here.

Notes for future OT posters:

1. Please add the 'open_thread' tag.

2. Check if there is an active Open Thread before posting a new one. (Immediately before; refresh the list-of-threads page before posting.)

3. Open Threads should start on Monday, and end on Sunday.

4. Unflag the two options "Notify me of new top level comments on this article" and "Make this post available under..." before submitting

Has anyone studied the Red Black Tree algorithms recently? I've been trying to implement them using my Finite State technique that enables automatic generation of flow diagrams. This has been working well for several other algorithms.

But the Red Black tree rebalancing algorithms seem ridiculously complicated. Here is an image of the deletion process (extracted from this Java code) - it's far more complicated than an algorithm like MergeSort or HeapSort, and that only shows the deletion procedure!

I'm weighing two hypotheses:

Keeping a binary tree balanced in N log N time is an intrinsically complex task.
There is some much simpler method to efficiently maintain balance in a binary tree, but nobody bothered looking for it after the RB tree algorithms and analysis were published.

I'm leaning toward the latter theory. It seems to me that most of the other "elementary" algorithms of computer science are comparatively simple, so the weird overcomplexity of the tool we use for binary tree balancing is some kind of oversight. Here is the Wiki page on RB trees - notice how the description of the algorithm is extremely hard to understand.

An intuition is that red-black trees encode 2-3-4 trees (B-trees of order 4) as binary trees.

For a simpler case, 2-3 trees (Ie. B-trees of order 3) are either empty, a (2-)node with 1 value and 2 subtrees, or a (3-)node with 2 values and 3 subtrees. The idea is to insert new values in their sorted position, expand 2-nodes to 3-nodes if necessary, and bubble up the extra values when a 3-node should be expanded. This keeps the tree balanced.

A 2-3-4 tree just generalises the above.

Now the intuition is that red means "I am part of a bigger node." Tha... (read more)

6gjm9y

There are other kinds of binary tree with simpler rebalancing procedures, most notably the AVL tree mentioned by cousin_it. I think red-black tends to dominate for some combination of these reasons: * Tradition. Some influential sources (e.g., Sedgwick's algorithms book[1], SGI's STL implementation) used, or gave more visibility to, red-black trees, and others copied them. * Fewer rotations in rebalancing. In some circumstances (certainly deletion; I forget whether it's true for insertion too) AVL trees may need to do Theta(log n) rotations, whereas red-black never need more than O(1). * Does this mean an actual advantage in performance? Maaaaybe. Red-black trees are, in the worst case at least, worse-balanced, which may actually matter more. Such benchmarks as I've seen don't suggest a very big advantage for either red-black or AVL over the other. * Persistence. If you want to make a persistent data structure out of a binary tree, whether for practical reasons or just to show your students in Haskell, it's easier with a red-black tree. * Metadata requirements. A red-black tree needs one bit per node, to store the redness/blackness. An AVL tree needs one and a half bits :-) to store the -1/0/+1 height difference. Perhaps in some implementations it's OK to "waste" one bit per node but not two. [1] I think. I don't have a copy myself. Surely it must at least mention AVL trees too, but my hazy recollection is that the balanced-tree algorithm Sedgwick gives most space to is red-black.

2cousin_it9y

I always felt that AVL trees were easier to understand than red-black. Just wrote some Haskell code for you. As you can see, both insertion and deletion are quite simple and rely on the same rebalancing operation.