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

Mattias Gaertner nc-gaertnma at netcologne.de
Sun Mar 18 03:20:52 CET 2012


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? 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.
> 
> Non-ordened access ofcourse would be slow because it would require a
> loop till the index is found.

I implemented a TIndexedAVLTree.
This allows log(n) access to items via the position. For example to
get the fourth node:

Node:=Tree[3];

It has the above caching mechanism to speed up common queries. So,
running with a "for i:=0 to Tree.Count-1 do" needs O(n).

Otherwise it is a normal AVL tree, so insertion, deletion and finding
takes O(log(n)).

I also added a second enumerator to TAvgLvlTree to run from highest to
lowest and I removed the nodememmanager making it is easier
to use with threads.

Mattias





More information about the Lazarus mailing list