News for hackers. Stuff that matters.
Re:Treaps: A Simple Balanced Binary Tree by jrockway on Sunday September 11, 2011 @12:37PM (#2984096)
I don't think the left-rotation and right-rotation functions in this implementation look much different from the "special cases" in red-black trees. People hate red-black trees because they learned them in Java or C, where they do suck. But if you implement them in Haskell, you'll see how beautiful they are.

Here's what my implementation from some time ago looks like:

    data Color = Red | Black deriving (Show, Eq)
    data Tree a = Nil | Tree Color (Tree a) a (Tree a) deriving Show

    insert :: Ord a => a -> Tree a -> Tree a
    insert x t = case ins x t of
      Tree _ l x r -> Tree Black l x r

    ins :: Ord a => a -> Tree a -> Tree a
    ins x Nil = Tree Red Nil x Nil
    ins x t@(Tree c l y r) = case compare x y of
      EQ -> t
      LT -> balance $ Tree c (ins x l) y r
      GT -> balance $ Tree c l y (ins x r)

    balance (Tree Black (Tree Red (Tree Red a x b) y c) z d) = balanced a b c d x y z
    balance (Tree Black a x (Tree Red b y (Tree Red c z d))) = balanced a b c d x y z
    balance (Tree Black a x (Tree Red (Tree Red b y c) z d)) = balanced a b c d x y z
    balance (Tree Black (Tree Red a x (Tree Red b y c)) z d) = balanced a b c d x y z
    balance x = x

    balanced a b c d x y z = Tree Red (Tree Black a x b) y (Tree Black c z d)
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.
Re:Treaps: A Simple Balanced Binary Tree by Peaker on Sunday September 11, 2011 @05:19PM (#2984875)
Here's an interesting partial implementation (no delete):

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.

Re:Treaps: A Simple Balanced Binary Tree by pavpanchekha on Sunday September 11, 2011 @02:50PM (#2984454)
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.

Re:Treaps: A Simple Balanced Binary Tree by psykotic on Sunday September 11, 2011 @04:29PM (#2984732)
> 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.

Re:Treaps: A Simple Balanced Binary Tree by blahedo on Sunday September 11, 2011 @07:20PM (#2985166)
> 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.

Re:Treaps: A Simple Balanced Binary Tree by Peaker on Sunday September 11, 2011 @05:21PM (#2984882)
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.

Re:Treaps: A Simple Balanced Binary Tree by jbapple on Tuesday September 13, 2011 @10:46AM (#2991663)
> 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.

Re:Treaps: A Simple Balanced Binary Tree by jbapple on Sunday September 11, 2011 @08:08PM (#2985274)
Deletion is trickier:

http://matt.might.net/articles/red-black-delete/

I suspect treap delete is simpler.