On 2007-12-14, Eric I. <rubytraining / gmail.com> wrote:
> On Dec 14, 10:58 am, Ken Bloom <kbl... / gmail.com> wrote:
>>    def test_tree_height_of_one_or_two_nodes_is_one
>>      @tree << 5
>>      assert_equal 1, @tree.height
>>      @tree << 6
>>      assert_equal 1, @tree.height
>>    end
>>    def test_tree_height_of_three_nodes_is_two
>>      @tree << 5
>>      @tree << 6
>>      @tree << 7
>>      assert_equal 2, @tree.height
>>    end
>
> Ken,
>
> I think you've led us astray.  Since all the examples of AVL trees
> cited by James show that the data is stored in the interior nodes (and
> not just the leaf nodes), it seems to me that the height of a tree
> with two or three pieces of data should be larger (by one) than that
> of a tree with only one piece of data.
>
> The only issue is whether height of a tree with a single piece of data
> is 0 or 1 (i.e., are we measuring the number of nodes from root to
> leaf or the number of "edges").  Given that the Wikipedia article
> says, "an AVL tree's height is limited to 1.44 * lg n", I think we
> should measure height by nodes.
>
> I figured a discussion would be better than simply modifying your code
> to fit my conceptions.  So what do you think?
>
> Eric

I had the solution to Rob's ping (but stopped posting it so I could get
an answer as to who's in charge of this quiz) and also started from 1 as
nodes are usually counted, not edges.

Basically, imho, height should return log2(@content.lenght) + 1.


-- 
everything is simple, we're stupid
contact at gmail