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

Re:Treaps: A Simple Balanced Binary Tree by pavpanchekha on Sunday September 11, 2011 @11:07AM (#2983902)
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...
Re:Treaps: A Simple Balanced Binary Tree by jrockway on Sunday September 11, 2011 @12:40PM (#2984103)
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.)

Re:Treaps: A Simple Balanced Binary Tree by pavpanchekha on Sunday September 11, 2011 @12:54PM (#2984141)
AVL trees give shorter path lengths. So the resulting structure ends up being better, depending on your exact balance of insertion and selection.
Re:Treaps: A Simple Balanced Binary Tree by SamReidHughes on Monday September 12, 2011 @08:19PM (#2989427)
Whaaa? AVL trees don't split the work between insertion and selection. Selections are plain old read-only BST lookups.
Re:Treaps: A Simple Balanced Binary Tree by sesqu on Sunday September 11, 2011 @12:56PM (#2984146)
I read a paper in the spring that purported to compare, among others, red-black trees and treaps. It found that treaps were better for ordered operations but worse for random operations.

edit: For the actual comparison between the three: treaps give no guarantees. Red-black trees sacrifice some lookup speed in favor of insertions.

Re:Treaps: A Simple Balanced Binary Tree by jbapple on Tuesday September 13, 2011 @10:50AM (#2991683)
I thought top trees were a data structure for implementing "dynamic trees" or "link-cut trees". How can they be used for implementing search trees?

Do the logarithmic update times in top trees take into account the time to locate the node to update?