--- 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 $'
 ! !
+