[fpc-devel] Re: [Lazarus] How to iterate through a TAvgLvlTree
nc-gaertnma at netcologne.de
Thu Mar 22 12:09:11 CET 2012
Marc Weustink <marc.weustink at cuperus.nl> hat am 22. März 2012 um 10:31
> 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.
> > 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).
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the fpc-devel