Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #47053

Re: Tutorial on threaded binary tree part 1: simple unthreaded tree

Show all headers | View raw

On Sat, 3 Dec 2016 00:58:19 +0100
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> wrote:

> On 02.12.2016 16:55, Mr Flibble wrote:
> >>  
> [snip]
> >> Possibilities include:
> >>
> >> • Inserting a new node with value V at the very top of an existing
> >> chain of V, reducing the insertion complexity to logarithmic.
> >>
> >> • Adding a value count in each node, and just incrementing it.
> >>   This precludes using the tree to associate different info with
> >> each key V.
> >>
> >> • Treating the tree as a simple set, and failing or doing nothing
> >> if V already exists.
> >>
> >> I think there may be some complexity hidden in the first
> >> possibility.
> >>
> >> But anyway, as you can see, avoiding square time /in general/ so
> >> as to make the structure generally useful, involves a decision
> >> about what the tree is used for, and modifying the `add` routine
> >> accordingly:
> >>
> >> a set (last bullet), a multiset (middle bullet), or a multimap
> >> (first bullet)?  
> >
> > You are wrong about how multiset and multimap differ: certainly
> > they do not correspond to your bullet points.  multiset and
> > multimap have identical data structures: the only difference is
> > multimap value_type is a pair in which the key is the first part.  
> 
> Hm, the above two sentences contradict each other. :)
> 
> The last sentence even contradicts itself.
> 
> As you note in the last part of that sentence, with a multimap
> multiple occurrences of the same key need to be distinguished,
> because they can be associated with different values.

You are wrong. Value is completely non essential for that data
structure. With that said, I can't figure out purpose of multiset at
all... but generally you are right. multiset does not needs to store
actual nodes. count and key are enough.




-- 
press any key to continue or any other to quit

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Tutorial on threaded binary tree part 1: simple unthreaded tree "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-01 10:32 +0100
  Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-01 20:23 +0000
    Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Jerry Stuckle <jstucklex@attglobal.net> - 2016-12-01 16:54 -0500
    Re: Tutorial on threaded binary tree part 1: simple unthreaded tree "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-02 03:15 +0100
      Re: Tutorial on threaded binary tree part 1: simple unthreaded tree leigh.v.johnston@googlemail.com - 2016-12-02 05:45 -0800
        Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Öö Tiib <ootiib@hot.ee> - 2016-12-02 08:30 -0800
      Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-02 15:32 +0000
        Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-02 16:15 +0000
      Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-02 15:55 +0000
        Re: Tutorial on threaded binary tree part 1: simple unthreaded tree "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-03 00:58 +0100
          Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Melzzzzz <mel@zzzzz.com> - 2016-12-03 01:51 +0100
            Re: Tutorial on threaded binary tree part 1: simple unthreaded tree "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-03 03:04 +0100
          Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-03 01:54 +0000
            Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-03 02:07 +0000
              Re: Tutorial on threaded binary tree part 1: simple unthreaded tree "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-03 03:11 +0100
                Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-03 02:17 +0000
                Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Öö Tiib <ootiib@hot.ee> - 2016-12-03 01:31 -0800
    Re: Tutorial on threaded binary tree part 1: simple unthreaded tree ruben safir <ruben@mrbrklyn.com> - 2016-12-02 17:39 -0500
  Re: Tutorial on threaded binary tree part 1: simple unthreaded tree legalize+jeeves@mail.xmission.com (Richard) - 2016-12-01 21:34 +0000
    Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-01 22:23 +0000
    Re: Tutorial on threaded binary tree part 1: simple unthreaded tree "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-02 00:32 +0100
      Re: Tutorial on threaded binary tree part 1: simple unthreaded tree legalize+jeeves@mail.xmission.com (Richard) - 2016-12-01 23:57 +0000
        Re: Tutorial on threaded binary tree part 1: simple unthreaded tree "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-02 01:14 +0100
          Re: Tutorial on threaded binary tree part 1: simple unthreaded tree legalize+jeeves@mail.xmission.com (Richard) - 2016-12-02 22:06 +0000
      Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Daniel <danielaparker@gmail.com> - 2016-12-01 20:12 -0800
        Re: Tutorial on threaded binary tree part 1: simple unthreaded tree "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-02 05:53 +0100
    Re: Tutorial on threaded binary tree part 1: simple unthreaded tree ruben safir <ruben@mrbrklyn.com> - 2016-12-02 17:45 -0500
      Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Ian Collins <ian-news@hotmail.com> - 2016-12-03 11:48 +1300
        Re: Tutorial on threaded binary tree part 1: simple unthreaded tree ruben safir <ruben@mrbrklyn.com> - 2016-12-02 17:49 -0500
          Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Ian Collins <ian-news@hotmail.com> - 2016-12-03 11:52 +1300
          Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Jerry Stuckle <jstucklex@attglobal.net> - 2016-12-02 19:44 -0500
  Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Tim Rentsch <txr@alumni.caltech.edu> - 2016-12-09 22:05 -0800

csiph-web