Re: [Pharo-users] [GSoC blog post] Binary Search Trees

[Alexandre Bergel via Pharo-users]

--- Begin Message ---

Thanks for your detailed answers

Cheers,
Alexandre

> On Jul 12, 2019, at 8:49 AM, Richard O'Keefe <rao...@gmail.com> wrote:
> 
> 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 <mailto: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 
>> <mailto: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
>>  
>> <https://pharokeepers.github.io/pharo/2019/07/07/SmiljanaBinarySearchTreeinPharo.html>
>> 
>> Feedback and opinions is always welcome :)
>> 
>> Best regards,
>> Smiljana Knezev
> 

--- End Message ---