3 ms·
> 2) It obscures the connection to B-trees, which is what leads one to derive all of the special cases after all. You mean 2-3-4 trees rather than general B-tr
by psykotic 15y ago
> 2) It obscures the connection to B-trees, which is what leads one to derive all of the special cases after all.
You mean 2-3-4 trees rather than general B-trees. Anyway, that is true of all implementations of red-black trees I have seen, and intentionally so. When you consider the number of possible parent/child configurations when splitting and merging 2-3-4 nodes, there's a whole lot of them. By expanding a 2-3-4 node as a cluster of red-black nodes, the local combinatorics are more manageable.
Even the presentations of red-black trees in textbooks (e.g. CLRS) usually obscure the connection with 2-3-4 trees, with one exception being Sedgewick's own book. That's too bad.
> 4) If you're doing rbtrees in Haskell, you might as well enforce your invariants with the type system.
If you're going to do that, it's probably easier to use the isomorphism with 2-3-4 trees and work with that. There's a standard trick for representing trees with the 2-3-4 invariant using non-regular data types:
data Tree a = Zero a | Succ (Tree (Node a))
data Node a = Node2 a a | Node3 a a a | Node4 a a a a
Alternatively, you could use left-leaning red-black trees, which have an isomorphism with 2-3 trees.
But it's not clear to me that there's much of a practical win in encoding the balance invariant in the type system here.
- Peaker 15y agoI think that Haskell's standard library implementation of a binary search tree (Data.Map) had long had a balancing bug... It probably doesn't anymore, but I guess it probably makes it a practical win to get type-level guarantees. Also, guarantees about correctness are easier to get from tools like QuickCheck. Balance errors will be harder to spot.
- blahedo 15y ago> Even the presentations of red-black trees in textbooks (e.g. CLRS) usually obscure the connection with 2-3-4 trees, with one exception being Sedgewick's own book. That's too bad. This continues to make me sad. My original (ugrad) algorithms class was taught from Sedgewick's book, and I always found RB trees to be elegant and conceptually simple (including the insertion and deletion cases); when I got to grad school, where CLR was the textbook of choice (and RB trees were actually taught in an earlier course anyway), man oh man was there a lot of wailing and gnashing of teeth over having to memorise the complicated deletion cases. Really? I just rederived them from scratch each time, and I was faster, and I was right. It's a serious disservice to teach someone the red-black tree algorithms without first teaching 2-3-4 trees and then teaching the isomorphism, and it's a shame that so many textbooks haven't figured this out.
- jbapple 15y ago> There's a standard trick for representing trees with the 2-3-4 invariant using non-regular data types: It should be noted that this puts a Theta(lg n) singly-linked list of Succ nodes at the top of the tree, thus doubling the effective height of the tree.