<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"><html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type"/>
</head>
<body>
<p style="margin: 0pt;">
<span>
<span></span>
</span>
</p>
<p style="margin: 0px; "></p>
<div style="margin: 5px 0px;">
<br/>
Marc Weustink <marc.weustink@cuperus.nl> hat am 22. März 2012 um 10:31 geschrieben:
<br/>
<br/>
> Felipe Monteiro de Carvalho wrote:
<br/>
> > Can I add a routine to access the AvgLvlTree as an array? To make it a
<br/>
> > better substitute to TFPList in objects which offer an indirect
<br/>
> > interface to the internal list, such as TLazAccessibleObject.
<br/>
> >
<br/>
> > My idea is defining:
<br/>
> > Index zero = Tree.FindLowest
<br/>
> > Indez Count-1= Tree.FindHighest
<br/>
> >
<br/>
> > On each access store the last accessed node and if the next call wants
<br/>
> > a node index=oldindex+1 or -1 then just use:
<br/>
> >
<br/>
> > Tree.FindSuccessor(Node)
<br/>
> > Tree.FindPrecessor(Node)
<br/>
> >
<br/>
> > Because almost always I use the array access only to iterate in a loop.
<br/>
>
<br/>
> Lazarus has a TMap implementations where a AvgLvlTree is used for
<br/>
> looking up items and has a own AvgLvlTreeItem which is a double linked
<br/>
> list so items can be iterated.
<br/>
> Tree.FindSuccessor(Node)/Tree.FindPrecessor(Node) can cause a lot of
<br/>
> nodes traveled.
</div>
<p style="margin: 0px;"> </p>
<p style="margin: 0px;">True. But practically it hardly matters due to the AVL feature of the tree. </p>
<p style="margin: 0px;">Half of the time it will travel 1 node.</p>
<p style="margin: 0px;">1/4 of the time it travels 2 nodes.</p>
<p style="margin: 0px;">1/8 it travels 3 nodes.</p>
<p style="margin: 0px;">1/16 it travels 4 nodes. </p>
<p style="margin: 0px;">...</p>
<p>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. </p>
<p style="margin: 0px;"> </p>
<p>On average it travels 2 nodes. </p>
<p> </p>
<p>Iterating an AVL tree needs 2*n steps. </p>
<p style="margin: 0px;"> </p>
<div style="margin: 5px 0px;">
>
<br/>
> Marc
<br/>
>
<br/>
> >
<br/>
> > Non-ordened access ofcourse would be slow because it would require a
<br/>
> > loop till the index is found.
</div>
<p style="margin: 0px;"> </p>
<p style="margin: 0px;">This is where TIndexedAVLTree is better. It needs at most log(n). </p>
<p style="margin: 0px;"> </p>
<p style="margin: 0px;">Mattias</p>
<p style="margin: 0px;"> </p>
</body>
</html>