Re: [gtk-list] Glib BTree & GTree wrapper

[Joe Pfeiffer <pfeiffer cs nmsu edu>]

	   It is my understanding that a Red/Black balancing binary tree is
   really just a BTree with a maximum of two child nodes.  Therefor, I would
   suggest that we replace the existing balancing binary tree code to use
   your BTree code, and having something like a function

There may be some sort of generalization possible by which you could
consider red/black trees and B trees in a common framework, but a
btree has (by definition) between N and 2N-1 children at each internal
node.  The max number of children has to be odd.

I didn't pay enough attention when this thread was starting -- why
exactly are btrees being proposed here?  While they are completely
balanced (using the path length definition of balanced), and not as
deep as binary trees, the number of comparisons to find an object is
actually greater than with a balanced binary tree.  Btrees were
developed for environments in which the cost of reading a node is much
greater than the cost of doing a comparison -- namely, data structures
on disk rather than in memory.

Unfortunately, it has become easier to find incorrect definitions of
btree on the web than correct ones....  I don't have my copy of Knuth
with me here so I can't give a page number, but that's where to look
to see it done right.
-- 
Joseph J. Pfeiffer, Jr., Ph.D.       Phone -- (505) 646-1605
Department of Computer Science       FAX   -- (505) 646-1002
New Mexico State University          http://www.cs.nmsu.edu/~pfeiffer
VL 2000 Homepage:  http://www.cs.orst.edu/~burnett/vl2000/