eXept Software AG Logo

Smalltalk/X Webserver

Documentation of class 'AATree':
Home

Documentation
www.exept.de
Everywhere
for:
[back]

Class: AATree

Inheritance:

   Object
   |
   +--Collection
      |
      +--BinaryTree
         |
         +--AATree
Package:
stx:libbasic2
Category:
Collections-Ordered-Trees
Version:
rev: 1.13 date: 2016/10/13 22:09:43
user: cg
file: AATree.st directory: libbasic2
module: stx stc-classLibrary: libbasic2
Author:
Original algorithm by Arne Andersson
ported from wikipedia to Smalltalk code by Claus Gittinger

Description:


An AA tree is a form of balanced tree used for storing and retrieving ordered data efficiently.
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.

Usage:
    As seen in the performance charts, AA trees offer better average and worst case
    performance, 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)

[instance variables:]
    treeRoot             TreeNode        the top node
    sortBlock            Block           sorter; 
                                         gets two args a,b and should return true if a is
                                         to come before b in the collection

Related information:

    BTree
    SortedCollection
    [ttps]

Instance protocol:

adding & removing
o  add: anObject
add the argument, anObject to the receiver.
Returns the object (sigh).

WARNING: do not add/remove elements while iterating over the receiver.
Iterate over a copy to do this.

o  treeNodeClass

Examples:


    |coll|

    coll := AATree new.
    (1 to:10) do:[:i | coll add:i].
    coll addAll:(20 to:30).
    coll inspect   

    |tree|

    tree := AATree new.
    tree add:'hello'.
    tree add:'aaaa'.
    tree add:'AAAb'.
    tree add:'aaaC'.
    tree add:'world'.
    tree asOrderedCollection     

    |tree|

    tree := AATree sortBlock:[:a :b | a asLowercase < b asLowercase].
    tree add:'hello'.
    tree add:'aaaa'.
    tree add:'AAAb'.
    tree add:'aaaC'.
    tree add:'world'.
    tree asOrderedCollection
timing 1: 
    |N randomNumbers coll1_BT coll2_AT coll3_SC coll4_AVL t1_BT t2_AT t3_SC t4_AVL|

    N := 1000000.
    randomNumbers := (1 to:N) collect:[:i | Random nextInteger].

    ObjectMemory garbageCollect.
    t1_BT := Time millisecondsToRun:[
        coll1_BT := BinaryTree new.
        coll1_BT addAll:randomNumbers
    ].
    coll1_BT := nil.
    ObjectMemory garbageCollect.

    t2_AT := Time millisecondsToRun:[
        coll2_AT := AATree new.
        coll2_AT addAll:randomNumbers
    ].
    coll2_AT := nil.
    ObjectMemory garbageCollect.

    t3_SC := Time millisecondsToRun:[
        coll3_SC := SortedCollection new.
        coll3_SC addAll:randomNumbers
    ].
    coll3_SC := nil.
    ObjectMemory garbageCollect.

    t4_AVL := Time millisecondsToRun:[
        coll4_AVL := AVLTree new.
        coll4_AVL addAll:randomNumbers
    ].
    coll4_AVL := nil.
    ObjectMemory garbageCollect.

    randomNumbers := nil.

    Transcript show:'Time to insert random '; show:N; show:' into SortedCollection: '; show:t3_SC; showCR:'ms'.
    Transcript show:'Time to insert random '; show:N; show:' into BinaryTree: '; show:t1_BT; showCR:'ms'.
    Transcript show:'Time to insert random '; show:N; show:' into AATree: '; show:t2_AT; showCR:'ms'.
    Transcript show:'Time to insert random '; show:N; show:' into AVLTree: '; show:t4_AVL; showCR:'ms'.

    ObjectMemory garbageCollect.
    t1_BT := Time millisecondsToRun:[
        coll1_BT := BinaryTree new.
        coll1_BT addAll:(1 to:100000).
    ].
    coll1_BT := nil.
    ObjectMemory garbageCollect.

    t2_AT := Time millisecondsToRun:[
        coll2_AT := AATree new.
        coll2_AT addAll:(1 to:100000)
    ].
    coll2_AT := nil.
    ObjectMemory garbageCollect.

    t3_SC := Time millisecondsToRun:[
        coll3_SC := SortedCollection new.
        coll3_SC addAll:(1 to:100000)
    ].
    coll3_SC := nil.
    ObjectMemory garbageCollect.

    t4_AVL := Time millisecondsToRun:[
        coll4_AVL := AVLTree new.
        coll4_AVL addAll:(1 to:100000)
    ].
    coll4_AVL := nil.
    ObjectMemory garbageCollect.

    Transcript show:'Time to insert ordered '; show:N; show:' into SortedCollection: '; show:t3_SC; showCR:'ms'.
    Transcript show:'Time to insert ordered '; show:N; show:' into BinaryTree: '; show:t1_BT; showCR:'ms'.
    Transcript show:'Time to insert ordered '; show:N; show:' into AATree: '; show:t2_AT; showCR:'ms'.
    Transcript show:'Time to insert ordered '; show:N; show:' into AVLTree: '; show:t4_AVL; showCR:'ms'.

    ObjectMemory garbageCollect.
    t1_BT := Time millisecondsToRun:[
        coll1_BT := BinaryTree new.
        coll1_BT addAll:(100000 downTo:1).
    ].
    coll1_BT := nil.
    ObjectMemory garbageCollect.

    t2_AT := Time millisecondsToRun:[
        coll2_AT := AATree new.
        coll2_AT addAll:(100000 downTo:1)
    ].
    coll2_AT := nil.
    ObjectMemory garbageCollect.

    t3_SC := Time millisecondsToRun:[
        coll3_SC := SortedCollection new.
        coll3_SC addAll:(100000 downTo:1)
    ].
    coll3_SC := nil.
    ObjectMemory garbageCollect.

    t4_AVL := Time millisecondsToRun:[
        coll4_AVL := AVLTree new.
        coll4_AVL addAll:(100000 downTo:1)
    ].
    coll4_AVL := nil.
    ObjectMemory garbageCollect.

    Transcript show:'Time to insert reverse ordered '; show:N; show:' into SortedCollection: '; show:t3_SC; showCR:'ms'.
    Transcript show:'Time to insert reverse ordered '; show:N; show:' into BinaryTree: '; show:t1_BT; showCR:'ms'.
    Transcript show:'Time to insert reverse ordered '; show:N; show:' into AATree: '; show:t2_AT; showCR:'ms'.
    Transcript show:'Time to insert reverse ordered '; show:N; show:' into AVLTree: '; show:t4_AVL; showCR:'ms'.
timing 2: 
    |allSelectors coll1_SC coll2_BT coll3_AT coll4_Trie t1_SC t2_BT t3_AT t4_Trie|

    allSelectors := OrderedCollection new.
    Smalltalk allClassesDo:[:cls |
        cls instAndClassSelectorsAndMethodsDo:[:sel :mthd |
            allSelectors add:sel.
        ].
    ].
    Transcript show:'Unique selectors: '; show:allSelectors asSet size; showCR:''.

    t1_SC := Time millisecondsToRun:[
        coll1_SC := SortedCollection new.
        allSelectors do:[:sel |
            coll1_SC add:sel
        ].
    ].
    Transcript show:'Time to insert '; show:coll1_SC size; show:' selectors into SortedCollection: '; show:t1_SC; showCR:'ms'.

    t2_BT := Time millisecondsToRun:[
        coll2_BT := BinaryTree new.
        allSelectors do:[:sel |
            coll2_BT add:sel
        ].
    ].
    Transcript show:'Time to insert '; show:coll2_BT size; show:' selectors into BinaryTree: '; show:t2_BT; showCR:'ms'.

    t3_AT := Time millisecondsToRun:[
        coll3_AT := BinaryTree new.
        allSelectors do:[:sel |
            coll3_AT add:sel
        ].
    ].
    Transcript show:'Time to insert '; show:coll3_AT size; show:' selectors into AATree: '; show:t3_AT; showCR:'ms'.

    t4_Trie := Time millisecondsToRun:[
        coll4_Trie := TrieCollection new.
        allSelectors do:[:sel |
            coll4_Trie add:sel
        ].
    ].
    Transcript show:'Time to insert '; show:coll4_Trie size; show:' selectors into Trie: '; show:t4_Trie; showCR:'ms'.

    t1_SC := Time millisecondsToRun:[
        allSelectors do:[:sel |
            coll1_SC remove:sel
        ].
    ].
    self assert:(coll1_SC isEmpty).
    Transcript show:'Time to remove selectors from SortedCollection: '; show:t1_SC; showCR:'ms'.

    t2_BT := Time millisecondsToRun:[
        allSelectors do:[:sel |
            coll2_BT remove:sel
        ].
    ].
    self assert:(coll2_BT isEmpty).
    Transcript show:'Time to remove selectors from BinaryTree: '; show:t2_BT; showCR:'ms'.

    t3_AT := Time millisecondsToRun:[
        allSelectors do:[:sel |
            coll3_AT remove:sel
        ].
    ].
    self assert:(coll3_AT isEmpty).
    Transcript show:'Time to remove selectors from AATree: '; show:t3_AT; showCR:'ms'.

    t4_Trie := Time millisecondsToRun:[
        allSelectors do:[:sel |
            coll4_Trie remove:sel
        ].
    ].
    self assert:(coll4_Trie isEmpty).
    Transcript show:'Time to remove selectors from Trie: '; show:t4_Trie; showCR:'ms'.

ST/X 7.1.0.0; WebServer 1.663 at exept.de:8081; Mon, 04 Aug 2025 14:25:19 GMT