[GSoC blog post] Binary Search Trees
Dear all, I've written about implementing binary search trees: https://pharokeepers.github.io/pharo/2019/07/07/SmiljanaBinarySearchTreeinPh... Feedback and opinions is always welcome :) Best regards, Smiljana Knezev
On 7 Jul 2019, at 23:12, Smiljana Knezev <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.
Best regards, Smiljana Knezev
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
More feedback :) Do not return nil Check the last lecture of the mooc Did you read Pharo with Style? I do not know if LinkedList is the one of the system used by Process but in that case use the alternate implementation. bfs: info "Breadth fisrt search for an information. If there is no key containing given infomration returns nil. If the info is found returns a node containing it" | queue | self isEmpty ifTrue: [ ^nil ]. queue := LinkedList new. queue addLast: self root. [ queue isNotEmpty ] whileTrue: [ | node | node := queue removeFirst. node key == info ifTrue: [ ^node ]. node leftChild isNotNil ifTrue: [ queue addLast: node leftChild ]. node rightChild isNotNil ifTrue: [ queue addLast: node rightChild ]. ]. ^nil. => bfs: info "Breadth fisrt search for an information. If there is no key containing given infomration returns nil. If the info is found returns a node containing it" | queue | self isEmpty ifTrue: [ ^ self ]. queue := LinkedList new. queue addLast: self root. [ queue isNotEmpty ] whileTrue: [ | node | node := queue removeFirst. node key == info ifTrue: [ ^node ]. node leftChild isNotNil ifTrue: [ queue addLast: node leftChild ]. node rightChild isNotNil ifTrue: [ queue addLast: node rightChild ]. ]
On 8 Jul 2019, at 05:57, ducasse <stepharo@netcourrier.com> wrote:
More feedback :)
Do not return nil Check the last lecture of the mooc
Did you read Pharo with Style?
I do not know if LinkedList is the one of the system used by Process but in that case use the alternate implementation.
Sorry Iâ still jet lagged and sleepy But - bfs: is a bad name. - Also why not having a block to specify what we are looking for?
bfs: info "Breadth fisrt search for an information. If there is no key containing given infomration returns nil. If the info is found returns a node containing it" | queue | self isEmpty ifTrue: [ ^nil ]. queue := LinkedList new. queue addLast: self root.
[ queue isNotEmpty ] whileTrue: [ | node | node := queue removeFirst. node key == info ifTrue: [ ^node ]. node leftChild isNotNil ifTrue: [ queue addLast: node leftChild ]. node rightChild isNotNil ifTrue: [ queue addLast: node rightChild ]. ]. ^nil.
=>
bfs: info "Breadth fisrt search for an information. If there is no key containing given infomration returns nil. If the info is found returns a node containing it" | queue | self isEmpty ifTrue: [ ^ self ]. queue := LinkedList new. queue addLast: self root.
[ queue isNotEmpty ] whileTrue: [ | node | node := queue removeFirst. node key == info ifTrue: [ ^node ]. node leftChild isNotNil ifTrue: [ queue addLast: node leftChild ]. node rightChild isNotNil ifTrue: [ queue addLast: node rightChild ]. ]
bfs: aValue => findBreadthFirst: aValue dfs: info node: aNode => findDeepFirst: aValue startingFrom: aNode
I agree #bfs: is not explicit, but #breadthFirstSearch: is a well know term, why not just that? Or even #breathFirstSearchFor: In comparison #findBreadthFirst: and #findDeepFirst: feel a bit awkward to me. (I think its the repetition rhythm of "f" words) cheers -ben On Mon, 8 Jul 2019 at 12:55, ducasse <stepharo@netcourrier.com> wrote:
bfs: aValue
=>
findBreadthFirst: aValue
dfs: info node: aNode
=>
findDeepFirst: aValue startingFrom: aNode
Thank you all very much. This is quite useful for me and I can learn a lot. best regards, Smiljana Knezev ÑÑе, 10. ÑÑл 2019. Ñ 12:29 Ben Coman <btc@openinworld.com> Ñе напиÑао/ла:
I agree #bfs: is not explicit, but #breadthFirstSearch: is a well know term, why not just that? Or even #breathFirstSearchFor:
In comparison #findBreadthFirst: and #findDeepFirst: feel a bit awkward to me. (I think its the repetition rhythm of "f" words)
cheers -ben
On Mon, 8 Jul 2019 at 12:55, ducasse <stepharo@netcourrier.com> wrote:
bfs: aValue
=>
findBreadthFirst: aValue
dfs: info node: aNode
=>
findDeepFirst: aValue startingFrom: aNode
Smiljana Knezev wrote
Dear all,
I've written about implementing binary search trees: https://pharokeepers.github.io/pharo/2019/07/07/SmiljanaBinarySearchTreeinPh...
Feedback and opinions is always welcome :)
Best regards, Smiljana Knezev
Your implementation is unnecesarily complicated. Remember, tree is a recursive data structure. You may have have reasons to split tree and node into different classes, but at least delegate operations to node. For example, #depth and #size can be defined as following methods of Node class: depth self isLeaf ifTrue: [ ^ 0 ]. ^ leftChild depth max: rightChild depth size self isLeaf ifTrue: [ ^ 1 ]. ^ leftChild size + rightChlid size Most other operations can also be defined in similar fashion. -- Sent from: http://forum.world.st/Pharo-Smalltalk-Users-f1310670.html
Hello Smiljana, Thanks for having written down this document. I am not expert in algorithm, so I would consider myself a simple user. I have developed complex software for some times and I have never seen the need of having a binary search tree. I guess this is probably partly because of my lack of expertise in binary search tree and partly because experts in binary search trees assume that people know what it is about and in what it is useful. My question is, when should a programmer ever need to use binary search tree? Can you add some examples on what these trees are good for, and how an average programmer should look into it. I think this will be a valuable and easy way to expand your blog. Cheers, Alexandre
On Jul 7, 2019, at 5:12 PM, Smiljana Knezev <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 :)
Best regards, Smiljana Knezev
participants (5)
-
Alexandre Bergel -
Ben Coman -
ducasse -
Smiljana Knezev -
webwarrior