https://github.com/yairchu/red-black-tree/blob/master/RedBla...
The AVL has a fuller implementation:
https://github.com/yairchu/red-black-tree/blob/master/AvlTre...
It's significantly more complex, but it gives a type-level/compile-time guarantee that the RB tree invariants are kept, which is nice.
However, there are several things I don't like about it.
1) There are still specific cases that require memory. The cases for treaps are always the obvious ones --- comparing priorities and comparing keys.
2) It obscures the connection to B-trees, which is what leads one to derive all of the special cases after all.
3) Maybe I'm dumb, but the running time guarantees aren't obvious.
4) If you're doing rbtrees in Haskell, you might as well enforce your invariants with the type system.
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.
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.
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.
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.
http://matt.might.net/articles/red-black-delete/
I suspect treap delete is simpler.
Here's what my implementation from some time ago looks like:
It's very simple; insert just ensures that the tree we get from ins is Black. ins inserts a node into the correct side of the tree, then balances it. balance takes the four cases of unbalanced subtrees and balances them into their most-balanced representation. It's quite a beautiful data structure.