3 ms·

Your implementation is indeed elegant and simple. However, there are several things I don't like about it. 1) There are still specific cases that require memo

Your implementation is indeed elegant and simple. 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.

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 ago
  I 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.

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 ago
I 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.