class: BinaryTreeNode
added:
#removRightLeftMostNode
#removeLeftMostNode
#removeRightLeftMostNode
comment/format in:
#insertNode:sortBlock:
#removeLeftRightMostNode
changed:5 methods
fix RegressionTests::BinaryTreeTester>>#test04_addingRemoving
--- a/BinaryTreeNode.st Thu Apr 04 09:58:59 2013 +0200
+++ b/BinaryTreeNode.st Mon Apr 08 16:36:27 2013 +0200
@@ -219,6 +219,7 @@
!BinaryTreeNode methodsFor:'insert & delete'!
insert:aBinaryTreeNode
+ <resource: #obsolete>
"insert a node, comparing nodes using a default sort rule"
self obsoleteMethodWarning.
@@ -228,6 +229,7 @@
!
insert:newBinaryTreeNode sortBlock:sortBlock
+ <resource: #obsolete>
"insert a node, comparing nodes using sortBlock"
self obsoleteMethodWarning.
@@ -258,8 +260,8 @@
node := self.
newValue := newBinaryTreeNode data.
[true] whileTrue:[
- "newValue is less the node data"
(sortBlock value:newValue value:node data) ifTrue:[
+ "newValue is less the node data"
left := node leftSubtree.
left isNil ifTrue:[
node leftSubtree:newBinaryTreeNode.
@@ -269,11 +271,11 @@
] ifFalse:[
"newValue is larger or equal than node data"
right := node rightSubtree.
- "if right data is less than node, we would be jumping back..."
right isNil ifTrue:[
node rightSubtree:newBinaryTreeNode.
^ self
].
+ "if right data is less than node, we would be jumping back..."
node := right
]
].
@@ -283,13 +285,13 @@
"/ leftSubtree isNil ifTrue:[
"/ leftSubtree := newBinaryTreeNode.
"/ ] ifFalse:[
-"/ leftSubtree insert:newBinaryTreeNode sortBlock:sortBlock
+"/ leftSubtree insertNode:newBinaryTreeNode sortBlock:sortBlock
"/ ]
"/ ] ifFalse:[
"/ rightSubtree isNil ifTrue:[
"/ rightSubtree := newBinaryTreeNode.
"/ ] ifFalse:[
-"/ rightSubtree insert:newBinaryTreeNode sortBlock:sortBlock
+"/ rightSubtree insertNode:newBinaryTreeNode sortBlock:sortBlock
"/ ]
"/ ]
@@ -315,8 +317,8 @@
ifTrue: [aStream nextPutAll: '--']
ifFalse: [
aStream nextPut: $(.
- self printDataOn: aStream. aStream nextPut: $ .
- leftSubtree printOn: aStream. aStream nextPut: $ .
+ self printDataOn: aStream. aStream space.
+ leftSubtree printOn: aStream. aStream space.
rightSubtree printOn: aStream.
aStream nextPut: $)]
@@ -347,6 +349,24 @@
!BinaryTreeNode methodsFor:'private helpers'!
+removeLeftMostNode
+ |left ll parent|
+
+ leftSubtree isNil ifTrue:[
+ self error:'should not happen'
+ ].
+
+ parent := self.
+ left := leftSubtree.
+ [ (ll := left leftSubtree) notNil ] whileTrue:[
+ parent := left.
+ left := ll.
+ ].
+ parent leftSubtree:(left rightSubtree).
+ left rightSubtree:nil.
+ ^ left.
+!
+
removeLeftRightMostNode
|rightMost|
@@ -364,11 +384,37 @@
tree := BinaryTreeNode data:4.
#(2 6 1 3 5 7)
do:[:word |
- tree insert:(BinaryTreeNode data:word).
+ tree insertNode:(BinaryTreeNode data:word).
].
tree printOn:Transcript indent:0. Transcript cr.
'---------------------------' printOn:Transcript. Transcript cr.
- tree removeLeftRightMostNode.
+ Transcript showCR:tree removeLeftRightMostNode.
+ tree printOn:Transcript indent:0. Transcript cr.
+ "
+!
+
+removeRightLeftMostNode
+ |leftMost|
+
+ rightSubtree leftSubtree isNil ifTrue:[
+ leftMost := rightSubtree.
+ rightSubtree := rightSubtree rightSubtree.
+ ^ leftMost.
+ ].
+
+ ^ rightSubtree removeLeftMostNode
+
+ "
+ |tree|
+
+ tree := BinaryTreeNode data:4.
+ #(2 6 1 3 5 7)
+ do:[:word |
+ tree insertNode:(BinaryTreeNode data:word).
+ ].
+ tree printOn:Transcript indent:0. Transcript cr.
+ '---------------------------' printOn:Transcript. Transcript cr.
+ Transcript showCR:tree removeRightLeftMostNode.
tree printOn:Transcript indent:0. Transcript cr.
"
!
@@ -387,6 +433,7 @@
right := rr.
].
parent rightSubtree:(right leftSubtree).
+ right leftSubtree:nil.
^ right.
"
@@ -395,7 +442,7 @@
tree := BinaryTreeNode data:4.
#(2 6 1 3 5 7)
do:[:word |
- tree insert:(BinaryTreeNode data:word).
+ tree insertNode:(BinaryTreeNode data:word).
].
Transcript showCR:tree.
Transcript showCR:(tree removeLeftRightMostNode).
@@ -426,14 +473,18 @@
rightSubtree isNil ifTrue:[
^ leftSubtree
].
- newTop := self removeLeftRightMostNode.
- newTop leftSubtree:leftSubtree.
- newTop rightSubtree:rightSubtree.
+ newTop := self removeRightLeftMostNode.
+"/ self assert:(rightSubtree isNil or:[(sortBlock value:rightSubtree data value:newTop data) not]).
+"/ self assert:(leftSubtree isNil or:[sortBlock value:leftSubtree data value:newTop data]).
+ newTop
+ leftSubtree:leftSubtree;
+ rightSubtree:rightSubtree.
^ newTop.
].
(sortBlock value:oldValue value:data) ifTrue:[
- "/ the value should be in the left part.
+ "oldValue is less the node data
+ and should be in the left part"
leftSubtree isNil ifTrue:[
^ nil
].
@@ -445,7 +496,8 @@
].
leftSubtree := newLeft.
] ifFalse:[
- "/ the value should be in the right part.
+ "oldValue is larger or equal (equal if doing identity-compare above)
+ than the node data and should be in the right part"
rightSubtree isNil ifTrue:[
^ nil
].
@@ -570,9 +622,10 @@
!BinaryTreeNode class methodsFor:'documentation'!
version
- ^ '$Header: /cvs/stx/stx/libbasic2/BinaryTreeNode.st,v 1.8 2012-08-06 06:05:51 cg Exp $'
+ ^ '$Header: /cvs/stx/stx/libbasic2/BinaryTreeNode.st,v 1.9 2013-04-08 14:36:27 stefan Exp $'
!
version_CVS
- ^ '$Header: /cvs/stx/stx/libbasic2/BinaryTreeNode.st,v 1.8 2012-08-06 06:05:51 cg Exp $'
+ ^ '$Header: /cvs/stx/stx/libbasic2/BinaryTreeNode.st,v 1.9 2013-04-08 14:36:27 stefan Exp $'
! !
+