--- a/BinaryTree.st Tue Dec 09 17:17:01 2003 +0100
+++ b/BinaryTree.st Wed Dec 10 10:54:24 2003 +0100
@@ -1,6 +1,6 @@
"{ Package: 'stx:libbasic2' }"
-SequenceableCollection subclass:#BinaryTree
+Collection subclass:#BinaryTree
instanceVariableNames:'treeRoot sortBlock'
classVariableNames:''
poolDictionaries:''
@@ -55,19 +55,66 @@
N := 1000000.
randomNumbers := (1 to:N) collect:[:i | Random nextInteger].
+ ObjectMemory garbageCollect.
t1 := Time millisecondsToRun:[
coll1 := BinaryTree new.
coll1 addAll:randomNumbers
].
+ coll1 := nil.
+ ObjectMemory garbageCollect.
t2 := Time millisecondsToRun:[
- coll1 := SortedCollection new.
- coll1 addAll:randomNumbers
+ coll2 := SortedCollection new.
+ coll2 addAll:randomNumbers
].
Transcript show:'Time to insert '; show:N; show:' into BinaryTree: '; show:t1; showCR:'ms'.
Transcript show:'Time to insert '; show:N; show:' into SortedCollection: '; show:t2; showCR:'ms'.
[exEnd]
+ timing 2:
+ [exBegin]
+ |allSelectors coll1 coll2 t0 t1 t2|
+
+ allSelectors := OrderedCollection new.
+ Smalltalk allClassesDo:[:cls |
+ cls instAndClassSelectorsAndMethodsDo:[:sel :mthd |
+ allSelectors add:sel.
+ ].
+ ].
+
+ t1 := Time millisecondsToRun:[
+ coll1 := SortedCollection new.
+ allSelectors do:[:sel |
+ coll1 add:sel
+ ].
+ ].
+ Transcript show:'Time to insert '; show:coll1 size; show:' selectors into SortedCollection: '; show:t1; showCR:'ms'.
+
+ t2 := Time millisecondsToRun:[
+ coll2 := BinaryTree new.
+ allSelectors do:[:sel |
+ coll2 add:sel
+ ].
+ ].
+ Transcript show:'Time to insert '; show:coll2 size; show:' selectors into BinaryTree: '; show:t2; showCR:'ms'.
+
+ t1 := Time millisecondsToRun:[
+ allSelectors do:[:sel |
+ coll1 remove:sel
+ ].
+ ].
+ self assert:(coll1 isEmpty).
+ Transcript show:'Time to remove selectors from SortedCollection: '; show:t1; showCR:'ms'.
+
+ t2 := Time millisecondsToRun:[
+ allSelectors do:[:sel |
+ coll2 remove:sel
+ ].
+ ].
+ self assert:(coll2 isEmpty).
+ Transcript show:'Time to remove selectors from BinaryTree: '; show:t2; showCR:'ms'.
+ [exEnd]
+
"
! !
@@ -108,6 +155,81 @@
"
BinaryTree new add:1; add:2; yourself
"
+!
+
+includesIdentical:anElement
+ treeRoot isNil ifTrue:[
+ ^ false.
+ ].
+ ^ treeRoot includesIdenticalValue:anElement sortBlock:sortBlock.
+
+ "
+ BinaryTree new
+ addAll:#(4 2 1 3 6 5 7);
+ includesIdentical:4
+ "
+
+ "
+ BinaryTree new
+ addAll:#(4 2 1 3 6 5 7);
+ includesIdentical:8
+ "
+!
+
+remove:oldObject ifAbsent:exceptionValue
+ |newRoot|
+
+ treeRoot isNil ifTrue:[
+ ^ exceptionValue value.
+ ].
+ newRoot := treeRoot removeValue:oldObject sortBlock:sortBlock.
+ newRoot isNil ifTrue:[
+ treeRoot data = oldObject ifFalse:[
+ ^ exceptionValue value.
+ ].
+ ].
+ treeRoot := newRoot
+
+ "
+ BinaryTree new
+ addAll:#(4 2 1 3 6 5 7);
+ removeIdentical:4;
+ yourself
+ "
+
+ "
+ BinaryTree new
+ addAll:#(4 2 1 3 6 5 7);
+ removeIdentical:7;
+ yourself
+ "
+!
+
+removeIdentical:oldObject ifAbsent:exceptionValue
+ |newRoot|
+
+ treeRoot isNil ifTrue:[
+ ^ exceptionValue value.
+ ].
+ newRoot := treeRoot removeIdenticalValue:oldObject sortBlock:sortBlock.
+ newRoot isNil ifTrue:[
+ ^ exceptionValue value.
+ ].
+ treeRoot := newRoot
+
+ "
+ BinaryTree new
+ addAll:#(4 2 1 3 6 5 7);
+ removeIdentical:4;
+ yourself
+ "
+
+ "
+ BinaryTree new
+ addAll:#(4 2 1 3 6 5 7);
+ removeIdentical:7;
+ yourself
+ "
! !
!BinaryTree methodsFor:'initialization'!
@@ -297,7 +419,7 @@
].
! !
-!BinaryTree::BinaryTreeNode methodsFor:'insertion'!
+!BinaryTree::BinaryTreeNode methodsFor:'insert & delete'!
insert:aBinaryTreeNode
"insert a node, comparing nodes using a default sort rule"
@@ -313,46 +435,110 @@
insert:newBinaryTreeNode sortBlock:sortBlock
"insert a node, comparing nodes using sortBlock"
- "/ the following might be ugly - however, it it 10 times faster
- "/ than the stuff below.
- "/ (we MUST have lco in smalltalk for this to be automatically fast)
-
- |node newValue left right|
+"/ "/ the following might be ugly - however, it it slightly faster
+"/ "/ than the stuff below.
+"/ "/ (we MUST have LCO in smalltalk for this to be automatically fast)
+"/
+"/ |node newValue left right|
+"/
+"/ node := self.
+"/ newValue := newBinaryTreeNode data.
+"/ [true] whileTrue:[
+"/ (sortBlock value:newValue value:node data) ifTrue:[
+"/ left := node leftSubtree.
+"/ left isNil ifTrue:[
+"/ node leftSubtree:newBinaryTreeNode.
+"/ ^ self
+"/ ].
+"/ node := left
+"/ ] ifFalse:[
+"/ right := node rightSubtree.
+"/ right isNil ifTrue:[
+"/ node rightSubtree:newBinaryTreeNode.
+"/ ^ self
+"/ ].
+"/ node := right
+"/ ]
+"/ ].
+"/ "not reached"
- node := self.
- newValue := newBinaryTreeNode data.
- [true] whileTrue:[
- (sortBlock value:newValue value:node data) ifTrue:[
- left := node leftSubtree.
- left isNil ifTrue:[
- node leftSubtree:newBinaryTreeNode.
- ^ self
- ].
- node := left
+ (sortBlock value:newBinaryTreeNode data value:data) ifTrue:[
+ leftSubtree isNil ifTrue:[
+ leftSubtree := newBinaryTreeNode.
+ ] ifFalse:[
+ leftSubtree insert:newBinaryTreeNode sortBlock:sortBlock
+ ]
+ ] ifFalse:[
+ rightSubtree isNil ifTrue:[
+ rightSubtree := newBinaryTreeNode.
] ifFalse:[
- right := node rightSubtree.
- right isNil ifTrue:[
- node rightSubtree:newBinaryTreeNode.
- ^ self
- ].
- node := right
+ rightSubtree insert:newBinaryTreeNode sortBlock:sortBlock
]
+ ]
+!
+
+removeIdenticalValue:oldValue sortBlock:sortBlock
+ "remove a value - returns a new treeNode, or nil if the value is not in the tree"
+
+ |newTop|
+
+ data == oldValue ifTrue:[
+ leftSubtree isNil ifTrue:[
+ ^ rightSubtree
+ ].
+ rightSubtree isNil ifTrue:[
+ ^ leftSubtree
+ ].
+ newTop := self removeLeftRightMostNode.
+ newTop leftSubtree:leftSubtree.
+ newTop rightSubtree:rightSubtree.
+ ^ newTop.
].
- "not reached"
-"/ (sortBlock value:aBinaryTreeNode value:self) ifTrue:[
-"/ leftSubtree isNil ifTrue:[
-"/ leftSubtree := aBinaryTreeNode.
-"/ ] ifFalse:[
-"/ leftSubtree insert:aBinaryTreeNode sortBlock:sortBlock
-"/ ]
-"/ ] ifFalse:[
-"/ rightSubtree isNil ifTrue:[
-"/ rightSubtree := aBinaryTreeNode.
-"/ ] ifFalse:[
-"/ rightSubtree insert:aBinaryTreeNode sortBlock:sortBlock
-"/ ]
-"/ ]
+ (sortBlock value:oldValue value:data) ifTrue:[
+ leftSubtree isNil ifTrue:[
+ ^ nil
+ ].
+ leftSubtree := leftSubtree removeIdenticalValue:oldValue sortBlock:sortBlock.
+ ^ self.
+ ].
+ rightSubtree isNil ifTrue:[
+ ^ nil
+ ].
+ rightSubtree := rightSubtree removeIdenticalValue:oldValue sortBlock:sortBlock.
+ ^ self.
+!
+
+removeValue:oldValue sortBlock:sortBlock
+ "remove a value - returns a new treeNode, or nil if the value is not in the tree"
+
+ |newTop|
+
+ data = oldValue ifTrue:[
+ leftSubtree isNil ifTrue:[
+ ^ rightSubtree
+ ].
+ rightSubtree isNil ifTrue:[
+ ^ leftSubtree
+ ].
+ newTop := self removeLeftRightMostNode.
+ newTop leftSubtree:leftSubtree.
+ newTop rightSubtree:rightSubtree.
+ ^ newTop.
+ ].
+
+ (sortBlock value:oldValue value:data) ifTrue:[
+ leftSubtree isNil ifTrue:[
+ ^ nil
+ ].
+ leftSubtree := leftSubtree removeValue:oldValue sortBlock:sortBlock.
+ ^ self.
+ ].
+ rightSubtree isNil ifTrue:[
+ ^ nil
+ ].
+ rightSubtree := rightSubtree removeValue:oldValue sortBlock:sortBlock.
+ ^ self.
! !
!BinaryTree::BinaryTreeNode methodsFor:'printing'!
@@ -370,6 +556,59 @@
aStream nextPut: $)]
! !
+!BinaryTree::BinaryTreeNode methodsFor:'private helpers'!
+
+removeLeftRightMostNode
+ |rightMost|
+
+ leftSubtree rightSubtree isNil ifTrue:[
+ rightMost := leftSubtree.
+ leftSubtree := leftSubtree leftSubtree.
+ ^ rightMost.
+ ].
+
+ ^ leftSubtree removeRightMostNode
+
+ "
+ |tree|
+
+ tree := BinaryTreeNode data:4.
+ #(2 6 1 3 5 7)
+ do:[:word |
+ tree insert:(BinaryTreeNode data:word).
+ ].
+ Transcript showCR:tree.
+ tree removeLeftRightMostNode.
+ "
+!
+
+removeRightMostNode
+ |removedNode|
+
+ rightSubtree isNil ifTrue:[
+ self error:'should not happen'
+ ].
+ rightSubtree rightSubtree notNil ifTrue:[
+ ^ rightSubtree removeRightMostNode.
+ ].
+ removedNode := rightSubtree.
+ rightSubtree := nil.
+ ^ removedNode
+
+ "
+ |tree|
+
+ tree := BinaryTreeNode data:4.
+ #(2 6 1 3 5 7)
+ do:[:word |
+ tree insert:(BinaryTreeNode data:word).
+ ].
+ Transcript showCR:tree.
+ Transcript showCR:(tree removeLeftRightMostNode).
+ Transcript showCR:tree.
+ "
+! !
+
!BinaryTree::BinaryTreeNode methodsFor:'queries'!
depth
@@ -387,11 +626,45 @@
!
inOrderSuccessor
- "Returns the in-order successor (a BST) of receiver.
+ "Returns the in-order successor the of receiver.
+ (that is the leftMost node on the right side)
If receiver is empty then returns the receiver."
rightSubtree isNil ifTrue:[^ self].
- rightSubtree inOrderDo: [:each | ^ each].
+ ^ rightSubtree leftMostNode
+!
+
+includesIdenticalValue:aValue sortBlock:sortBlock
+ "return true, if aValue is contained as some node's data"
+
+ data == aValue ifTrue:[ ^ true ].
+ (sortBlock value:aValue value:data) ifTrue:[
+ leftSubtree isNil ifTrue:[
+ ^ false
+ ].
+ ^ leftSubtree includesIdenticalValue:aValue sortBlock:sortBlock.
+ ].
+ rightSubtree isNil ifTrue:[
+ ^ false
+ ].
+ ^ rightSubtree includesIdenticalValue:aValue sortBlock:sortBlock.
+!
+
+includesValue:aValue sortBlock:sortBlock
+ "return true, if some node's data is equal to aValue"
+
+ data = aValue ifTrue:[ ^ true ].
+
+ (sortBlock value:aValue value:data) ifTrue:[
+ leftSubtree isNil ifTrue:[
+ ^ false
+ ].
+ ^ leftSubtree includesIdenticalValue:aValue.
+ ].
+ rightSubtree isNil ifTrue:[
+ ^ false
+ ].
+ ^ rightSubtree includesIdenticalValue:aValue.
!
isEmpty
@@ -406,6 +679,13 @@
^ ((leftSubtree isNil) and: [rightSubtree isNil])
!
+leftMostNode
+ "Returns the leftMost (smallest-valued) node"
+
+ leftSubtree isNil ifTrue:[^ self].
+ ^ leftSubtree leftMostNode
+!
+
level
"Returns the depth of the binary tree"
@@ -421,6 +701,13 @@
^ l + 1
!
+rightMostNode
+ "Returns the rightMost (largest-valued) node"
+
+ rightSubtree isNil ifTrue:[^ self].
+ ^ rightSubtree rightMostNode
+!
+
size
"Returns the size of the binary tree by traversing each element inorder"
@@ -434,5 +721,5 @@
!BinaryTree class methodsFor:'documentation'!
version
- ^ '$Header: /cvs/stx/stx/libbasic2/BinaryTree.st,v 1.1 2003-12-09 16:17:01 cg Exp $'
+ ^ '$Header: /cvs/stx/stx/libbasic2/BinaryTree.st,v 1.2 2003-12-10 09:54:24 cg Exp $'
! !