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.knezev@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