[Lazarus] In search of a component for holding a table of strings

[Mattias Gaertner]

On Tue, 10 Jan 2017 14:01:51 +0100
Werner Pamler via Lazarus <lazarus at lists.lazarus-ide.org> wrote:

>[...]A standard 
> "Add" of the tree calls "FindInsertPos" which seeks for the correct 
> position of the new cell. But every time this search starts from the 
> root which is unnecessary from my pov because the new cell should be at 
> the end. There is no "Append" or "AddtoEnd" method.

An AddHighest can be added. Note that from a theoretical pov it still
costs O(log n).

 
> Maybe I should remember the node of the previously added cell, and when 
> the next cell is to be added I should attach it as a right child of this 
> node.

That's what AddAscendingSequence does.

 
> Unfortunately I am not very experienced with this kind of trees. For 
> example: Is it necessary to rebalance the AVLtree immediately after each 
> insertion,

Yes, because the Balance factors are only valid for at most one error.

> or can I wait until all nodes exist? There is a 
> "BalanceAfterInsert" method with the new node as a parameter - this 
> indicates that balancing should occur immediately after insert. But this 
> method is private and thus cannot be called from a derived tree 
> implementing an "AddToEnd" method.

Well, theoretically you can create an optimized method that creates a
fresh tree from a sorted list in O(n).

In TAvgLvlTree the BalanceAfterInsert is protected.
I will send a new version to FPC.

Mattias