[GRASS-dev] Unused files

[Glynn Clements]

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
> lib/btree/
> and to replace it by a wrapper to
> lib/vector/dglib/

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>