6 ms·

Treaps: A Simple Balanced Binary Tree

73 points by pavpanchekha 15y ago

IvoDankolov 15y ago
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.
- deleted 15y ago
  [deleted]
- eru 15y ago
  > 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. To be fair, Red-Black trees get much simpler in a functional setting. (If you don't look at deletion.)
- dmlorenzetti 15y ago
  I wrote a binary tree that used node counts in a similar way. However, the insertion rules included checking whether a rotation on the inserted node would result in a subtree that could again be rotated by the same rule. This gave a cutoff ratio of left-to-right counts, below which it didn't make sense to rotate-- and hence kept every subtree pretty nicely balanced. Another benefit to having the node counts-- and this, I think, was the original motivation-- was it made the tree "binary" not only for looking up a particular key, but also for looking up the Nth key-ordered entry (which was important in the application).
- ScottBurson 15y ago
  Keeping the element counts gives you something called weight-balanced binary trees. Here's a paper on them by Stephen Adams: http://groups.csail.mit.edu/mac/users/adams/BB/ I used a variation on these for my FSet functional collections library for Common Lisp.
tantalor 15y ago
> 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.
- ggchappell 15y ago
  >> 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. Don't think so. A Binary Search Tree is a Binary Tree in which an inorder traversal goes through the data -- keys, in this case -- in sorted order. Of course, usefulness dictates that keys typically have associated values, but they do not have to be there, for it to be a BST. (Why have keys with no associated values? That's one way to represent a set.)
  - tantalor 15y ago
    Well put.
tantalor 15y ago
See also: http://en.wikipedia.org/wiki/Treap http://en.wikipedia.org/wiki/Treap
katox 15y ago
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 https://github.com/katox/toptree
- pavpanchekha 15y ago
  I remember a paper that compared fast implementations of treaps, AVL, and red-black trees, and found that they are approximately equally well suited. rbtrees are best at insertion, AVL at selection, treaps at overall performance (if I recall correctly). I don't have the reference though...
  - jrockway 15y ago
    That result surprises me. Red-black trees do their work at insertion time, and AVL trees split the work between insertion and selection. This should make red-black trees faster at selection and AVL trees faster at insertion, and both should do a set of insertions and selections in the same time. (A red-black tree is a plain-old binary search tree for everything but modifications.)
    - pavpanchekha 15y ago
      AVL trees give shorter path lengths. So the resulting structure ends up being better, depending on your exact balance of insertion and selection.
    - SamReidHughes 15y ago
      Whaaa? AVL trees don't split the work between insertion and selection. Selections are plain old read-only BST lookups.
  - 15y ago
FredBrach 15y ago
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-means-heuristic-for-general-purpose-binary-search-trees-and-animated-data-sets-r2607 http://www.gamedev.net/page/resources/_//fsweet-snippet/k-me...
- sesqu 15y ago
  The problem that a binary search tree optimizes for is the lookup or sequence of lookups of data in a set with a total ordering. If you want to do range lookups instead, the binary search tree is still excellent, but possibly not optimal, though I'm under the impression that k-trees are usually just trivial extensions of a BST. As for your heuristic, I'm not clear on your meaning. It's true that the "best" greedy top-down heuristic for a BST is to cut at the conditional median - but whether this is the same as a datum partitioning the sought from the unsought depends on more detail, especially since we're now talking about range searches. Also, provided you have the distribution at hand and are willing to write a lot of hairy code, you can reduce the average path length by less than 1 (yay).
  - FredBrach 15y ago
    Thx for reply. The difference between BSTs and k-trees is that balancing the tree is a huge misconception for k-trees. Also, in my paper, I pose some basic hypothesis which are: data are points, without any indication of distribution and the search range is a convex in the point space. Something like a school case. With this hypothesis which are general, balancing the tree (ak. Octree) is a hard misconception coming from BST. It will be difficult to me to explain here why, but it's not really hard to see it. Take this exemple and my hypothesis: you have a logarithmic distribution of points in 1D (but you don't know it particularly) and you are searching the points in random continuous ranges, then the best tree is a total unbalanced tree. And note that my heuristic will gives you a total unbalanced tree. If you have regurlarly distributed points, my heuristic will gives you an octree. One day, I hope, I will find a damn good mathematician to prooves that the K-Means Tree is the best tree in the general hypothesis.:p or maybe i'm wrong =)
jrockway 15y ago
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.
- pavpanchekha 15y ago
  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.
deleted 15y ago
[deleted]
sesqu 15y ago
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.
- pavpanchekha 15y ago
  Simplicity of code, and the existence of hooks to add orthogonal functionality. Not all of programming is picking an optimal data structure and then implementing it; sometimes, it involves planning for maintenance and change.
  - sesqu 15y ago
    Fair enough, but I personally believe the AVL structure is sufficiently simple. Let me compare treaps and AVL trees: Both insert at the same point, then proceed to rebalance. The treap will rotate upwards until p_new>p_parent. The AVL will update balance information upwards until bal_parent%2==1, then update and possibly rotate once. That's a couple of conditional operations extra, and field operations instead of tree operations. The final step in particular is less elegant, but straggling cleanup operations are everyday things and well worth the better performance, to me.
- jbapple 15y ago
  > I've never understood the allure of treaps. Ignoring the simplicity argument, treaps can perform some other operations (local updates and nearby searches) in optimal expected time (see theorems 3.1 and 3.2): http://sims.berkeley.edu/~aragon/pubs/rst96.pdf http://sims.berkeley.edu/~aragon/pubs/rst96.pdf > 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. The randomness treaps use should be independent of the input keys, so ordered input should produce a treap with a shape drawn from the same distribution as the one for unordered input.

73 points by pavpanchekha 15y ago

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.

deleted 15y ago
[deleted]
eru 15y ago
> 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. To be fair, Red-Black trees get much simpler in a functional setting. (If you don't look at deletion.)
dmlorenzetti 15y ago
I wrote a binary tree that used node counts in a similar way. However, the insertion rules included checking whether a rotation on the inserted node would result in a subtree that could again be rotated by the same rule. This gave a cutoff ratio of left-to-right counts, below which it didn't make sense to rotate-- and hence kept every subtree pretty nicely balanced. Another benefit to having the node counts-- and this, I think, was the original motivation-- was it made the tree "binary" not only for looking up a particular key, but also for looking up the Nth key-ordered entry (which was important in the application).
ScottBurson 15y ago
Keeping the element counts gives you something called weight-balanced binary trees. Here's a paper on them by Stephen Adams: http://groups.csail.mit.edu/mac/users/adams/BB/ I used a variation on these for my FSet functional collections library for Common Lisp.

tantalor 15y ago

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

ggchappell 15y ago
>> 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. Don't think so. A Binary Search Tree is a Binary Tree in which an inorder traversal goes through the data -- keys, in this case -- in sorted order. Of course, usefulness dictates that keys typically have associated values, but they do not have to be there, for it to be a BST. (Why have keys with no associated values? That's one way to represent a set.)
- tantalor 15y ago
  Well put.

tantalor 15y ago

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

katox 15y ago

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 https://github.com/katox/toptree

pavpanchekha 15y ago
I remember a paper that compared fast implementations of treaps, AVL, and red-black trees, and found that they are approximately equally well suited. rbtrees are best at insertion, AVL at selection, treaps at overall performance (if I recall correctly). I don't have the reference though...
- jrockway 15y ago
  That result surprises me. Red-black trees do their work at insertion time, and AVL trees split the work between insertion and selection. This should make red-black trees faster at selection and AVL trees faster at insertion, and both should do a set of insertions and selections in the same time. (A red-black tree is a plain-old binary search tree for everything but modifications.)
  - pavpanchekha 15y ago
    AVL trees give shorter path lengths. So the resulting structure ends up being better, depending on your exact balance of insertion and selection.
  - SamReidHughes 15y ago
    Whaaa? AVL trees don't split the work between insertion and selection. Selections are plain old read-only BST lookups.
- 15y ago

FredBrach 15y ago

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-means-heuristic-for-general-purpose-binary-search-trees-and-animated-data-sets-r2607 http://www.gamedev.net/page/resources/_//fsweet-snippet/k-me...

sesqu 15y ago
The problem that a binary search tree optimizes for is the lookup or sequence of lookups of data in a set with a total ordering. If you want to do range lookups instead, the binary search tree is still excellent, but possibly not optimal, though I'm under the impression that k-trees are usually just trivial extensions of a BST. As for your heuristic, I'm not clear on your meaning. It's true that the "best" greedy top-down heuristic for a BST is to cut at the conditional median - but whether this is the same as a datum partitioning the sought from the unsought depends on more detail, especially since we're now talking about range searches. Also, provided you have the distribution at hand and are willing to write a lot of hairy code, you can reduce the average path length by less than 1 (yay).
- FredBrach 15y ago
  Thx for reply. The difference between BSTs and k-trees is that balancing the tree is a huge misconception for k-trees. Also, in my paper, I pose some basic hypothesis which are: data are points, without any indication of distribution and the search range is a convex in the point space. Something like a school case. With this hypothesis which are general, balancing the tree (ak. Octree) is a hard misconception coming from BST. It will be difficult to me to explain here why, but it's not really hard to see it. Take this exemple and my hypothesis: you have a logarithmic distribution of points in 1D (but you don't know it particularly) and you are searching the points in random continuous ranges, then the best tree is a total unbalanced tree. And note that my heuristic will gives you a total unbalanced tree. If you have regurlarly distributed points, my heuristic will gives you an octree. One day, I hope, I will find a damn good mathematician to prooves that the K-Means Tree is the best tree in the general hypothesis.:p or maybe i'm wrong =)

jrockway 15y ago

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.

pavpanchekha 15y ago
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.

deleted 15y ago

[deleted]

sesqu 15y ago

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.

pavpanchekha 15y ago
Simplicity of code, and the existence of hooks to add orthogonal functionality. Not all of programming is picking an optimal data structure and then implementing it; sometimes, it involves planning for maintenance and change.
- sesqu 15y ago
  Fair enough, but I personally believe the AVL structure is sufficiently simple. Let me compare treaps and AVL trees: Both insert at the same point, then proceed to rebalance. The treap will rotate upwards until p_new>p_parent. The AVL will update balance information upwards until bal_parent%2==1, then update and possibly rotate once. That's a couple of conditional operations extra, and field operations instead of tree operations. The final step in particular is less elegant, but straggling cleanup operations are everyday things and well worth the better performance, to me.
jbapple 15y ago
> I've never understood the allure of treaps. Ignoring the simplicity argument, treaps can perform some other operations (local updates and nearby searches) in optimal expected time (see theorems 3.1 and 3.2): http://sims.berkeley.edu/~aragon/pubs/rst96.pdf http://sims.berkeley.edu/~aragon/pubs/rst96.pdf > 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. The randomness treaps use should be independent of the input keys, so ordered input should produce a treap with a shape drawn from the same distribution as the one for unordered input.