Re: [gtk-list] Re: GLIB's N-ary trees

[Owen Taylor <otaylor redhat com>]

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

> > > Ah, so a GNode is not a BTree because it doesn't do any kind of
> > > balancing.
> [...]
> > The GTree is allready able to auto-balance (have a small look in
> > gtree.c : g_tree_insert() actually calls the g_tree_node_insert()
> > static - and this one calls g_tree_node_balance() if needed).
> > So you don't have to build your own Btree.
> 
> 	I need a tree that has more than two children per node.  As far as
> I can tell, GTree will only work as a binary tree, not a BTree (although I
> admit I have not looked at the source very thoroughly).
> 
> 	Assuming GTree is using Red/Black to do its balancing, I could
> probably just adapt the GTree code to have multiple children.  I haven't
> had time to look at it closely yet...

GTree isn't Red/Black but some other balanced-tree algorithm - I
forget the name right now.

Josh Macdonald apparently has a BTree implementation in the GLib style
that he was proposing for addition at one time. I could see adding
more tree implementations to GLib, but it would require somebody to go
and figure out what the tradeoffs are between the different types,
which ones provided compelling advantages and should be included, and
how much of the interface should be shared between the different tree
types.

Regards,
                                        Owen