[fpc-devel] Re: [Lazarus] How to iterate through a TAvgLvlTree

[Mattias Gaertner]

Marc Weustink <marc.weustink at cuperus.nl> hat am 22. März 2012 um 10:31
geschrieben:

> Felipe Monteiro de Carvalho wrote:
> > Can I add a routine to access the AvgLvlTree as an array? To make it a
> > better substitute to TFPList in objects which offer an indirect
> > interface to the internal list, such as TLazAccessibleObject.
> >
> > My idea is defining:
> > Index zero = Tree.FindLowest
> > Indez Count-1= Tree.FindHighest
> >
> > On each access store the last accessed node and if the next call wants
> > a node index=oldindex+1 or -1 then just use:
> >
> >   Tree.FindSuccessor(Node)
> >   Tree.FindPrecessor(Node)
> >
> > Because almost always I use the array access only to iterate in a loop.
>
> Lazarus has a TMap implementations where a AvgLvlTree is used for
> looking up items and has a own AvgLvlTreeItem which is a double linked
> list so items can be iterated.
> Tree.FindSuccessor(Node)/Tree.FindPrecessor(Node) can cause a lot of
> nodes traveled.


True. But practically it hardly matters due to the AVL feature of the tree.

Half of the time it will travel 1 node.
1/4 of the time it travels 2 nodes.
1/8 it travels 3 nodes.
1/16 it travels 4 nodes.
...

That means in a tree with 1 million nodes there is exactly one case where
it travels 20 nodes, two cases where it travels 19 nodes, ... and 500.000
nodes where it travels 1 node.



On average it travels 2 nodes.



Iterating an AVL tree needs 2*n steps.



>
> Marc
>
> >
> > Non-ordened access ofcourse would be slow because it would require a
> > loop till the index is found.


This is where TIndexedAVLTree is better. It needs at most log(n).

Mattias
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freepascal.org/pipermail/fpc-devel/attachments/20120322/362266c6/attachment.html>