On 8 Jul 2019, at 05:51, ducasse <stepharo@netcourrier.com> wrote:
On 7 Jul 2019, at 23:12, Smiljana Knezev <smilja.knezev@gmail.com <mailto:smilja.knezev@gmail.com>> wrote:
Dear all,
I've written about implementing binary search trees: https://pharokeepers.github.io/pharo/2019/07/07/SmiljanaBinarySearchTreeinPh... <https://pharokeepers.github.io/pharo/2019/07/07/SmiljanaBinarySearchTreeinPh...>
Feedback and opinions is always welcome :)
pay attention to the formatting of your code. It makes is difficult to read (I do not know if this is wordpress effect or not).
Once you have your tree implementation and tests I would really like to see if you can get another implementation and measure the impact of introducing a NullNode to remove all the isNil checks.
Also no need of extra parentheses between binary and keywords depth:aNode "Returns depth of a tree starting from the given node" | leftDepth rightDepth | leftDepth := -1. aNode leftChild isNotNil ifTrue: [ leftDepth := self depth: aNode leftChild ]. rightDepth := -1. aNode rightChild isNotNil ifTrue: [ rightDepth := self depth: aNode rightChild ]. ( leftDepth > rightDepth ) ifTrue: [ ^ (1 + leftDepth) ] ifFalse: [^ (1 + rightDepth ) ]. => leftDepth > rightDepth ifTrue: [ ^ 1 + leftDepth ] ifFalse: [^ 1 + rightDepth ]. And even better move out of block returns when possible ^ leftDepth > rightDepth ifTrue: [ 1 + leftDepth ] ifFalse: [ 1 + rightDepth ]. With a nullNode the code should look like depth:aNode "Returns depth of a tree starting from the given nodeâ | leftDepth rightDepth | leftDepth := self depth: aNode leftChild. rightDepth := self depth: aNode rightChild. ^ leftDepth > rightDepth ifTrue: [ 1 + leftDepth ] ifFalse: [1 + rightDepth ]
Best regards, Smiljana Knezev