|
Class: AATree
Object
|
+--Collection
|
+--BinaryTree
|
+--AATree
- Package:
- stx:libbasic2
- Category:
- Collections-Ordered-Trees
- Version:
- rev:
1.14
date: 2018/06/15 10:12:11
- 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
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,
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 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)
[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
BTree
SortedCollection
[ttps]
adding & removing
-
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.
-
treeNodeClass
-
|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'.
|
|