[Lazarus] How to iterate through a TAvgLvlTree

[Mattias Gaertner]

On Fri, 16 Mar 2012 11:36:08 +0100
Felipe Monteiro de Carvalho <felipemonteiro.carvalho at gmail.com> wrote:

> Can I add a routine to access the AvgLvlTree as an array?

No.

A tree in general has no first or 0 element.

If you want to iterate through all nodes, use an enumerator or the
findlowest+findsuccessor.

If you want a hybrid of array and avl tree use a differential tree.
Martin has implemented a specific one. Maybe a descendant of
TAvgLvlTree can be implemented as a generic one.


> 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.

That's one specific use case.
For other examples how avl trees can be used see the hundreds of places
in the IDE.

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

Keep the last node. It can be found in O(logn).
Why use an integer to refer to an element?

Mattias