Search trees (which come in many varieties) are good for collections in
which
adding, deleting, and lookup are interleaved, where there is an order on the
elements (if used as a set) or the keys (if used as a dictionary). So are
hash tables. But (balanced) search trees have guaranteed O(lg n) worst case
time, which hash tables do not. And search trees let you enumerate their
contents in ascending or descending order, at any time. And search trees
can
support queries like
- tell me all the elements {<, <=, >, >=} x
- tell me all the elements between L and U
- tell me the next element (before,after) x
My Smalltalk library includes Sorted{Set,Bag,Dictionary} implemented as
splay trees.
Some time I must try an alternative.
in time O(lg n + number of answers).
On Thu, 11 Jul 2019 at 04:53, 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.
>
> 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
>
>
>
