From: "Eric I." <rubytraining@...>
Date: 2007-12-15T02:15:04+09:00
Subject: Re: Programmer Ping-Pong (#150)

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