Treaps: A Simple Balanced Binary Tree

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.

Writing tree structures is always fun. Writing it in an optimized way is a lot of work though. And what's worse one needs to reimplement quite a few things if the problem solved by the particular tree changes.

To avoid that issue Tarjan and Werneck designed self-adjusting trees so the user doesn't have to understand implementation details while still having access to an effective data structure. There is a free implementation (with relevant papers linked) so if you don't want to reinvent the wheel have a look :)

https://github.com/katox/toptree

Interesting, though it's balanced only on average. I suppose it's possible that you can both get elements inserted in order and have the random priorities selected in decreasing order. The chance of ending in a worst case for a tree of non-trivial size would be exceedingly low so I don't see it causing much issue in practice. It is random, though, and sometimes you might prefer systems that are deterministic (say if you absolutely can't afford bad cases).

Anyway, when it comes to simplicity I will admit it is much more appealing than red-black trees and their 5 billion cases for insert and delete - none of them unreasonable, true, but I didn't like debugging that thing at all the first time I attempted to implement it. So, yeah, that's something you can reliably implement when you don't have time/ can't be bothered to look up the ridiculously complicated stuff and you just want to dish out a fast data structure that you know works (binary heap - 1, suffix tree - 0, treap - 1, RBTree - 0).

As for the problem, it should be quite simple if you just keep tabs on the element count on the left and right subtrees, which is small price to pay (under a few million elements, but even with you're working with hundreds of millions - suck it up and buy an extra gig of ram). Something like this pseudocode (hopefully with added error checking) :

  pos n root =
    if root.right.count >= n then
      pos n root.right
    else if n == 1 || root.right.count - n == 1 then
      (root.key, root.value)
    else
      pos (n - root.right.count) root.left

Overall, quite an interesting mix of ordered (search) trees and heaps, I like it.

See also: http://en.wikipedia.org/wiki/Treap

I've never understood the allure of treaps. As long as it's only probabilistically balanced, the only thing it offers beyond random binary search trees is unpredictability in the face of ordered input.

In essence, the treap is the same approach to balancing as the skip list. What's wrong with AVL trees?

edit: that said, if you do have a genuine need to prioritize some nodes, the observation that the BST property does not preclude the heap property is a very nice one.

> What I'm calling a "binary tree" here is normally called a binary search tree.

This is because it associates keys with values. Standard binary trees usually skip the values.

I wonder why BST are not implemented as a standard binary tree plus a hash table. I suppose the trade off depends on the size of the values.

I've worked alot on binary search trees. Note that balancing a tree is only good when you will seek only one leaf in each request. If you may seek from zero to n leaves in one request, the fact the tree is balanced is absolutely not particularly a good thing. In this case, here is my theory:

A binary tree is good when the probability of a node to cut its set into a sought set and a not-sought set is the highest on average. And here is a draft of mine of such a binary tree but I don't know in fact if it is right :p

http://www.gamedev.net/page/resources/_//fsweet-snippet/k-me...