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

Groups > comp.programming > #6528

Re: on an n-element heap and its nodes of height h

Show all headers | View raw

Philip Lantz <prl@canterey.us> writes:

> Richard Heathfield wrote:
> Ben Bacarisse wrote:
>> > Richard Heathfield writes:
>> >> Ben Bacarisse wrote:
>> >>> Richard Heathfield writes:
>> >>>> Let's show it for h = 4:
>> >>>>
>> >>>> 1:...........*...........
>> >>>> 2:.....*...........*.....
>> >>>> 3:..*.....*.....*.....*..
>> >>>> 4:.*.*...*.*...*.*...*.*.
>> >>>>
>> >>>> At level 4, we have 8 = 2^(4-1) nodes, not 16 = 2^4 nodes.
>> >>>
>> >>> Most people would call that a tree of height 3.  I've never seen your
>> >>> counting used for tree height, but I have led a sheltered life.
>> >>
>> >> One can envisage nodes in a tree as if they were rooms in a building,
>> >> and the height is the number of storeys. h=4
>> >>
>> >> One can envisage nodes in a tree as if they were posts in a fence, and
>> >> the height is the number of fence-rails you need. h=3
>> >
>> > One could, but why would one?  Why is that analogy better than others
>> > where height is usually a measured length?
>> 
>> You're assuming that I thought it all through, instead of shooting from 
>> the hip. Why would you make that assumption?
<snip>
> For what it's worth, I thought you were right. It would never have occurred
> to me to count it any other way.

That's the nub of it.  It's not that you and Richard are counting "the
other way" it's that you are counting rather than measuring.  The
measure of "height" (upwards) and "depth" (downwards) are used in lots
of ways when talking about trees.  One talks of a node having a certain
height above another one, with the height of a tree being the (maximal)
height of the root above the leaves.

Using it as a measure rather than a count makes zero far too useful a
value to ignore, quite apart from the oddity of a node having a non-zero
height above itself.

-- 
Ben.

Back to comp.programming | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

on an n-element heap and its nodes of height h Daniel Bastos <dbastos@toledo.com> - 2016-04-18 08:48 -0300
  Re: on an n-element heap and its nodes of height h Wally W. <ww84wa@aim.com> - 2016-04-18 08:08 -0400
  Re: on an n-element heap and its nodes of height h Öö Tiib <ootiib@hot.ee> - 2016-04-18 05:47 -0700
    Re: on an n-element heap and its nodes of height h Daniel Bastos <dbastos@toledo.com> - 2016-04-18 13:56 -0300
  Re: on an n-element heap and its nodes of height h Richard Heathfield <rjh@cpax.org.uk> - 2016-04-18 14:41 +0100
    Re: on an n-element heap and its nodes of height h Daniel Bastos <dbastos@toledo.com> - 2016-04-18 13:36 -0300
      Re: on an n-element heap and its nodes of height h Richard Heathfield <rjh@cpax.org.uk> - 2016-04-18 21:45 +0100
        Re: on an n-element heap and its nodes of height h Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-04-19 01:55 +0100
          Re: on an n-element heap and its nodes of height h Richard Heathfield <rjh@cpax.org.uk> - 2016-04-19 02:05 +0100
            Re: on an n-element heap and its nodes of height h Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-04-19 02:28 +0100
              Re: on an n-element heap and its nodes of height h Richard Heathfield <rjh@cpax.org.uk> - 2016-04-19 02:30 +0100
                Re: on an n-element heap and its nodes of height h Philip Lantz <prl@canterey.us> - 2016-04-18 21:24 -0700
                Re: on an n-element heap and its nodes of height h Richard Heathfield <rjh@cpax.org.uk> - 2016-04-19 09:23 +0100
                Re: on an n-element heap and its nodes of height h Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-04-20 11:01 +0100

csiph-web