On Tue, 10 Jan 2017 14:01:51 +0100 Werner Pamler via Lazarus <lazarus@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 -- _______________________________________________ Lazarus mailing list Lazarus@lists.lazarus-ide.org http://lists.lazarus-ide.org/listinfo/lazarus
