|
Class: AATree
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
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
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'.
|
|