[GRASS-dev] Unused files
glynn at gclements.plus.com
Wed Apr 18 11:33:36 EDT 2007
Markus Neteler wrote:
> >>> lib/vector/dglib/avl.c | avl_allocator_default
> >> avl: libavl - library for manipulation of binary trees
> >> I think we have also lib/btree/ is that's the same purpose?
> > Yes; both provide essentially the same functionality.
> > AVL trees are balanced, so they have better worst-case performance.
> > Unbalanced trees are O(log(n)) for random data but degenerate to O(n)
> > for sorted data (you essentially end up with a linked list). Balanced
> > trees are always O(log(n)), although with a higher constant factor for
> > insertions due to the cost of rebalancing.
> Could this be a reason to drop
> and to replace it by a wrapper to
The interface is quite different. lib/btree has separate key/value,
while avl.c has a monolithic "item", with the user-supplied compare
function being used to determine matches.
IMHO, it would be better to modify lib/btree to use AVL trees (or
B-trees etc) if performance is considered an issue.
Glynn Clements <glynn at gclements.plus.com>
More information about the grass-dev