Re: Fwd: Persistent Binary Search Trees

[Soeren Sandmann <sandmann daimi au dk>]

Dana Jansens <dana cg scs carleton ca> writes:

> There are 2 other BSTs that would work effectively to provide a
> persistent BST, while also maintaining a very efficient implementation
> for when persistence is not used.  They are:
>  - Treaps
>  - Red-Black Trees

> Treaps can be expected to outperform Red-Black Trees for any sized
> tree.  The constant in the search cost for a Treap is Approximately
> equal to AVL trees (and slightly less for large trees), and is always
> smaller than Red-Black Trees. (It's a small constant regardless.)
> Treaps are also much simpler to implement, requiring less complicated
> code. However Treaps are a randomized data structure, which some
> people try to stay away from.
 
For what it's worth the GSequence data structure, which is already in
GLib, is a treap internally, but it has a list-like API
externally. Even though it is a treap internally, it is not really
randomized. It hashes pointers instead of randomizing, which has
mostly the same effect.


Soren