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