Re: Possible Glib BTree substitute

[Soeren Sandmann <sandmann daimi au dk>]

Derek Simkowiak <dereks@kd-dev.com> writes:

> 	I am only submitting this because I think it could be successfully
> used in projects where the data struct *is* a bottleneck, and Glib does
> not current have a fast searching data structure other than the binary
> tree.  Also, I think it may be a better addition to Glib than, say, an AVL
> tree.

The GTree *is* an AVL tree.

In my opinion, there should be only one O(log n) searching data
structure in GLib. These are some of the possibilities:

 - Skip lists:

      advantages: 
          A simple and, on the average/in the expected sense, very
          fast data structure.

      disadvantages: 
          It is randomized, which means that it's worst case
          behavoiour is O(n).

 - Balanced binary search trees (AVL, red/black, ...)

      advantages: 
          Guaranteed O(log n) worst case behaviour. There is already a
          working and bug-free implementation. 

      disadvantages: 
          The constant hidden in O(log n), while small, is larger than
          that for skip lists (I am not certain as I have not seen
          your skip list implementation).

 - Splay trees

      advantages: 
          Splay trees adapt to actual use, ie. frequently used items
          are close to the root. GMemChunk could be faster if
          implemented with a splay tree instead of an AVL tree.

      disadvantages: 
          Guarantees only O(log n) in the amortized sense. This may
          matter for real time applications. Also, even amortized, the
          constant hidden by O() is larger than for both AVL trees and
          skip lists, at least if you do not consider the caching
          behaviour.