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

[Derek Simkowiak <dereks kd-dev com>]

> GTree isn't Red/Black but some other balanced-tree algorithm - I
> forget the name right now.
[...]
> 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.

	A Red/Black binary tree is a merely a BTree for which "B" is set
to 2.  B is the maximum number of nodes per branch before that branch is
re-balanced (by moving one of the nodes up one level), so when B is two
(aka Red/Black) you have a binary tree.

	From my readings (which is 3 or 4 off-the-shelf C algorithm books
and three or four articles I found on the Internet) the BTree is the most
balanced type of tree, and it works no matter what order your data is in
(unlike a non-balancing binary tree).  It is not as popular because there
is some relatively complicated special-case code that needs to get
written, and has traditionally been used in systems where entire
sub-branches of the tree need to be written to disk (read: too much data
to fit into RAM).  However, the writings I've seen imply BTree is the
fastest well-understood algorithm.

	As I understand it, we could simply add a parameter to the GTree
that lets you specify the minimum and maximum number of children per node
(which is the factor that determines the height of your BTree) and the
rest of the API could remain the same.  We may even be able to have some
wrapper #define macros that invoke a default of 2, so the API would
default to being a balanced binary tree based on Red/Black.

	This would give us fast balancing binary trees *AND* a BTree
implementation.  If anyone is interested, I can point you to at least two
BTree implementations (one in Perl and one in the Tk GUI toolkit, in the
TkText widget).

	Disclaimer: I am not a CS guy.  I do not understand trees from a
theoretical perspective.


--Derek