On Wed, Jul 10, 2019 at 9:53 AM Alexandre Bergel via Pharo-users < pharo-users@lists.pharo.org> wrote:
> 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. > Hi Alexandre, I can tell you that GemStone/S makes extensive use of b-trees and variants in its internal data structures. Two examples are the object table itself and the index data structures. I agree that the average programmer may never have a need for them, but I don't like to close doors on (other) developers. Smiljana, Others have suggested things like the Null Object pattern for the left and right links, but an alternative or supplement to that would be a space optimizing leaf node which doesn't have instance variables for left and right sub-trees. But, don't go down the optimizing paths until you have good solutions for everything else. i.e. make right, then make it fast. I noted your code looks "C-like", which I suspect arises from being inspired by implementation in other languages. For example, I think only an empty tree should answer 0 for depth. A tree with one node should answer 1 while a tree with 2 or 3 nodes should answer 2, etc. If you drew a tree out on paper, how many levels would you see? That is the depth, in my opinion. Another example arises from one of the most powerful idioms in Smalltalk. Call it the #at:ifAbsent: pattern. (See also #detect:ifNone:) Someone else mentioned the passing around of nil and suggested you not do that. The #at:ifAbsent: pattern is the key to avoiding that: tell the receiver what *you* want to *do* if the thing can't be found by passing in your own block. Additionally, you will want your nodes to support various payloads. Right now the payload is the object held in the key. That works for identity structures, but it won't work for more advanced needs, such as one would find in a database index structure. Eventually, you will want the ability to have nodes that support additional attribute(s). I've found P. J Plauger's "0, 1, infinity" rule to be a superb design guideline. In short, once you go beyond having one of something (e.g. the key itself), you need to design things so that you can have an arbitrarily large number. The step from 1 to >1 is huge and messy if retrofitted, but easy when planned in. Eventually, you will need queries against the tree, allowing range selection, identity versus equality, etc. The tree should provide a basic infrastructure for searching, but a separate modelling of queries will be necessary. That may be out of scope for GSOC, of course. Good work and good luck with the rest of the project! > 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.kne...@gmail.com> > wrote: > > Dear all, > > I've written about implementing binary search trees: > https://pharokeepers.github.io/pharo/2019/07/07/SmiljanaBinarySearchTreeinPharo.html > > Feedback and opinions is always welcome :) > > Best regards, > Smiljana Knezev > > >
