Dana Jansens <d...@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 _______________________________________________ gtk-devel-list mailing list gtk-devel-list@gnome.org http://mail.gnome.org/mailman/listinfo/gtk-devel-list