News for hackers. Stuff that matters.
Re:Treaps: A Simple Balanced Binary Tree by tantalor on Sunday September 11, 2011 @06:57AM (#2983605)
> 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.

Re:Treaps: A Simple Balanced Binary Tree by ggchappell on Sunday September 11, 2011 @07:02AM (#2983609)
>> 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.)

Re:Treaps: A Simple Balanced Binary Tree by tantalor on Sunday September 11, 2011 @08:27AM (#2983677)
Well put.