From: Rob Biedenharn Date: 2007-12-16T10:47:25+09:00 Subject: Re: Programmer Ping-Pong (#150) On Dec 14, 2007, at 12:20 PM, Paul Irofti wrote: > On 2007-12-14, Eric I. wrote: >> On Dec 14, 10:58 am, Ken Bloom 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 Paul, I assume you've seen the (many!) other message, but I wanted to point out that I agree with you and the current tests support that a tree with two items has height 2. I was initially confused about where the items would be stored. I hope you're going to jump back in. -Rob Rob Biedenharn http://agileconsultingllc.com Rob@AgileConsultingLLC.com