#DOCUMENTATION by cg
class: AATree class
comment/format in:
#documentation
#performance
--- a/AATree.st Thu Jun 14 11:37:52 2018 +0200
+++ b/AATree.st Fri Jun 15 12:12:11 2018 +0200
@@ -1,3 +1,5 @@
+"{ Encoding: utf8 }"
+
"
COPYRIGHT (c) 2009 by eXept Software AG
All Rights Reserved
@@ -42,13 +44,14 @@
AA trees are named for Arne Andersson, their inventor.
AA trees are a variation of the red-black tree, which in turn is an enhancement to the
- binary search tree. One caveat with the implementation is that it needs an extra level instvar
- in the treeNode; this results in 25% more storage overhead as compared to a Red/Black or plain Binary tree.
- For performance data, see performance.
+ binary search tree.
+ One caveat with the implementation is that it needs an extra level instvar in the treeNode,
+ which results in 25% more storage overhead as compared to a Red/Black or plain Binary trees.
+ For performance data, red the comment in the performance documentation method.
Usage:
As seen in the performance charts, AA trees offer better average and worst case
- performance, with a slightly lower best case performance.
+ performance compared to SortedCollection, with a slightly lower best case performance.
Thus providing a more predictable performance
(within a factor of 2, as opposed to a much wider range for sortedCollections)
@@ -305,7 +308,7 @@
It is super fast, when adding in 'almost sorted' or almost reverse-sorted order,
or when only a few elements are to be added later.
To create a big sorted collection, it is better to first collect them all unsorted in
- an orderedCollection, then convert in one operation using asSortedCollection.
+ an OrderedCollection, then convert in one operation using #asSortedCollection.
Time to insert random 100000 individually into SortedCollection: 6037ms
Time to insert random 100000 en-bloque into SortedCollection: 172ms