Re: tar is slow with --listed-incremental

[Ken Pizzini]

On 03 Oct 2000 05:56:04 -0200, Alexandre Oliva <address@hidden> wrote:
>>   Do you know where I can find GPL code for a balanced tree? 
>Check libiberty, in the GCC CVS repo.  There's splay-tree.c (I'm not
>sure whether it's automatically balanced or not, though)

A splay-tree is not guaranteed to be balanced; worst-case for a
single operation is a linear search.  But in terms of
*amortized* cost (i.e., the average cost of an operation, when
all adds/queries/updates/deletes to the data structure over its
lifetime), a splay tree is asymptotically equivalent to balanced
trees, and (depending on quality of implementation) will
typically have a lower constant of proportionality.

(Re: the worst case --- this can only happen if there were a
large sequence of operations which systematically ignored most
of the nodes (e.g., doing nothing but inserts on a sorted list),
and so the linear cost of the single instance has been more than
balanced by the small cost (a small constant in the sorted
inserts example) of the many operations that went before, and
so the amortized cost remains O(lg N).)

                --Ken Pizzini