[QUIZ] Programmer Ping-Pong (#150)

[Ruby Quiz]

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

This is a non-traditional Ruby Quiz that changes the rules of the contest.
Please read the entire message before playing along. We will be back to normal
quizzes next time, for those that end up missing them.

The Game

Eric Hodel described Programmer Ping-Pong in his RubyConf 2007 presentation. I
wasn't familiar with the concept before that and it sounds like fun, so let's
all try it out together.

The rules are:

* This quiz does not have a no-spoiler period so you may
submit at anytime after reading this message
* I'll make the initial serve, starting the quiz off with
a single failing test
* Anyone can return the ball at anytime by doing exactly
two things, in order: make all tests pass including the
recently added failure and then add a new failing test
of your own

I want to see if we can build an entire library using just that process.

The Task

Let's build a pure Ruby binary AVL tree. An AVL tree is a self-balancing binary
tree data structure where insertion, deletion, and lookup all take O(log n) time
to execute. This is handy to have for many search problems that must run
quickly. It can also be used to build constructs like an OrderedHash.

You can read more about AVL trees on Wikipedia:

http://en.wikipedia.org/wiki/Avl_tree

There's also a handy document describing their rotations in detail:

http://fortheloot.com/public/AVLTreeTutorial.rtf

What features our AVL tree will support will be decided by you as you write
tests. Here are some suggestions of things we might try though, just to get you
thinking:

* Support for custom Ruby objects as nodes of the tree
* The ability to customize the comparison code, perhaps with a block
* A String output visualizer, possibly for the inspect() method
* Any other great features you can think of to add

The Details

We will have two files: avl_tree.rb and test_avl_tree.rb. Please pass both
files in each submission email you make for this quiz. Let's not complicate
this with directory structures or zip files.

Please don't add any external dependencies, unless it's a standard library. We
want everyone to be able to easily run this code and play along.

We are using Test::Unit instead of RSpec, or any other tool, for similar
reasons.

Please keep your tests short. Under 10 lines is preferred, but don't go over
24.

Also try to test just one aspect of the implementation with each test. I did
purposely say "aspect" and not "method." I do test more than one method in the
serve and I can imagine other scenarios where it could be useful, like checking
support for a handful of the standard Enumerator methods.

You can refactor any code as needed provided you do not change its function and
all tests still pass after you do so.

Adds comments if you need to, but writing code that needs no comment would be
even better.

Let's use some simple spacing conventions to keep all of us on the same page.
Indent two space and do not use tabs. Break up long lines so they do not exceed
80 characters.

Finally, this quiz has the potential to be very chaotic. Take pity on your
quizmaster who must track this process and on the rest of the community who may
be bothered by a highly active thread. I suggest good email manners:

* Use your client's "Reply" feature and make sure you are replying to
the message that contains the test you made pass
* Trim any unneeded context from the reply, including the previous
version of the code since you will be including the current copy
of the whole thing
* Kindness to your fellow programmers trumps any listed guidelines

The Serve

The initial contents of avl_tree.rb are:

#!/usr/bin/env ruby -wKU

class AVLTree

end

The test file, test_avl_tree.rb, begins as:

#!/usr/bin/env ruby -wKU

require "test/unit"

require "avl_tree"

class TestAVLTree < Test::Unit::TestCase
def setup
@tree = AVLTree.new
end

def test_tree_membership
assert_equal(true, @tree.empty?)
assert_equal(false, @tree.include?(3))

@tree << 3

assert_equal(false, @tree.empty?)
assert_equal(true, @tree.include?(3))
end
end

 

[Rick DeNatale]

The Game

Eric Hodel described Programmer Ping-Pong in his RubyConf 2007 presentation. I
wasn't familiar with the concept before that and it sounds like fun, so let's
all try it out together.

The rules are:

* This quiz does not have a no-spoiler period so you may
submit at anytime after reading this message
* I'll make the initial serve, starting the quiz off with
a single failing test
* Anyone can return the ball at anytime by doing exactly
two things, in order: make all tests pass including the
recently added failure and then add a new failing test
of your own

We're doing this in the true tdd spirit of making very small steps right.

Okay, first return.

avl_tree.rb
#!/usr/bin/env ruby -wKU

class AVLTree

def empty?
!@contents
end

def include?(obj)
return @contents == obj
end

def <<(obj)
@contents = obj
end

end

test_avl_tree.rb
#!/usr/bin/env ruby -wKU

require "test/unit"

require "avl_tree"

class TestAVLTree < Test::Unit::TestCase
def setup
@tree = AVLTree.new
end

def test_tree_membership
assert_equal(true, @tree.empty?)
assert_equal(false, @tree.include?(3))

@tree << 3

assert_equal(false, @tree.empty?)
assert_equal(true, @tree.include?(3))
end

def test_tree_should_allow_more_than_one_element
@tree << 3
@tree << 4

assert(@tree.include?(4))
assert(@tree.include?(3))
end

end

 

[Paul Irofti]

The Serve

The Pong

The initial contents of avl_tree.rb are:

The altered contents of avl_tree.rb are:

#!/usr/bin/env ruby -wKU

class AVLTree
attr_accessor :head
def initialize
@head = nil
end
def empty?
@head.nil?
end
def << (thing)
@head = thing if empty?
end
def include?(value)
@head == value
end
end

The test file, test_avl_tree.rb, begins as:

The test file was altered as:

#!/usr/bin/env ruby -wKU

require "test/unit"

require "avl_tree"

class TestAVLTree < Test::Unit::TestCase
def setup
@tree = AVLTree.new
end

def test_tree_membership
assert_equal(true, @tree.empty?)
assert_equal(false, @tree.include?(3))

@tree << 3

assert_equal(false, @tree.empty?)
assert_equal(true, @tree.include?(3))
end

def test_tree_insertion
assert_equal(true, @tree.empty?)
assert_equal(false, @tree.include?(3))
assert_equal(false, @tree.include?(5))

@tree << 3
@tree << 5

assert_equal(false, @tree.empty?)
assert_equal(true, @tree.include?(5))
assert_equal(true, @tree.include?(3))
end
end

Hope this follows the rules as the insertion is not actually implemented
nor is the include?. But I guess in less than 20 lines that's the best a
`Pong' can do (-:

 

[Paul Irofti]

We're doing this in the true tdd spirit of making very small steps right.

Okay, first return.

Hmm, when I posted no one answered, but I guess you got there first.
Does your version count as the next? Or how is this settled? We seem to
have written similar things anyways.

 

[Rob Biedenharn]

Hmm, when I posted no one answered, but I guess you got there first.
Does your version count as the next? Or how is this settled? We seem
to
have written similar things anyways.

I'll settle that. Since your tests were equivalent, I went with
Rick's since I saw it first:

avl_tree.rb

#!/usr/bin/env ruby -wKU

class AVLTree

def initialize
@contents = []
end

def empty?
@contents.empty?
end

def include?(obj)
@contents.include?(obj)
end

def <<(obj)
@contents << obj
end

def height
end

end
__END__


test_avl_tree.rb

#!/usr/bin/env ruby -wKU

require "test/unit"

require "avl_tree"

class TestAVLTree < Test::Unit::TestCase
def setup
@tree = AVLTree.new
end

def test_tree_membership
assert_equal(true, @tree.empty?)
assert_equal(false, @tree.include?(3))

@tree << 3

assert_equal(false, @tree.empty?)
assert_equal(true, @tree.include?(3))
end

def test_tree_should_allow_more_than_one_element
@tree << 3
@tree << 4

assert(@tree.include?(4))
assert(@tree.include?(3))
end

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

end
__END__

Rob Biedenharn http://agileconsultingllc.com
(e-mail address removed)

 

[John Joyce]

question about this quiz:
How do you prevent or at least reign in the splintering/forking of
code and likely duplication of efforts here?
As with so many quizzes, I'm going to sit and watch the ping pong
battle royale. I don't know much about binary trees or other such
data structures...

 

[Eivind Eklund]

I ended up responding to Paul because it looked like a later
submission (and response to the first pong).

The Pong

The altered contents of avl_tree.rb are:

#!/usr/bin/env ruby -wKU

class AVLTree
attr_accessor :head
def initialize
@head = nil
end
def empty?
@head.nil?
end
def << (thing)
@head = thing if empty?
end
def include?(value)
@head == value
end
end

The test file was altered as:

#!/usr/bin/env ruby -wKU

require "test/unit"

require "avl_tree"

class TestAVLTree < Test::Unit::TestCase
def setup
@tree = AVLTree.new
end

def test_tree_membership
assert_equal(true, @tree.empty?)
assert_equal(false, @tree.include?(3))

@tree << 3

assert_equal(false, @tree.empty?)
assert_equal(true, @tree.include?(3))
end

def test_tree_insertion
assert_equal(true, @tree.empty?)
assert_equal(false, @tree.include?(3))
assert_equal(false, @tree.include?(5))

@tree << 3
@tree << 5

assert_equal(false, @tree.empty?)
assert_equal(true, @tree.include?(5))
assert_equal(true, @tree.include?(3))
end
end

Hope this follows the rules as the insertion is not actually implemented
nor is the include?. But I guess in less than 20 lines that's the best a
`Pong' can do (-:

Here's a ping (or is that now a poing?)

Note that I've joined up the test and tree files using the customary
$0 == __FILE__ hack, to make participation as simple as cut/pasting to
a single file. You run the tests by "ruby avltree.rb" (or
/avltree.rb if you change modes), and use the library by "require
'avltree'". The require will NOT run the tests.


#!/usr/bin/env ruby -wKU

class AVLTree
attr_accessor :head, :left
def initialize
@head = nil
@left = nil
end
def empty?
@head.nil?
end
def << (thing)
if empty?
@head = thing
else
@left = AVLTree.new
@left << thing
end
end
def include?(value)
@head == value || (@left != nil && @left.include?(value))
end
end

if $0 == __FILE__
require "test/unit"

class TestAVLTree < Test::Unit::TestCase
def setup
@tree = AVLTree.new
end

def test_tree_membership
assert_equal(true, @tree.empty?)
assert_equal(false, @tree.include?(3))

@tree << 3

assert_equal(false, @tree.empty?)
assert_equal(true, @tree.include?(3))
end

def test_tree_insertion
assert_equal(true, @tree.empty?)
assert_equal(false, @tree.include?(3))
assert_equal(false, @tree.include?(5))

@tree << 3
@tree << 5

assert_equal(false, @tree.empty?)
assert_equal(true, @tree.include?(5))
assert_equal(true, @tree.include?(3))
end

def test_tree_include_many
0.upto(10) do |i|
assert(false, @tree.include?(i))
@tree << i
0.upto(i) do |j|
assert(true, @tree.include?(j))
end
end
end
end
end

 

[Phrogz]

question about this quiz:
How do you prevent or at least reign in the splintering/forking of
code and likely duplication of efforts here?
As with so many quizzes, I'm going to sit and watch the ping pong
battle royale. I don't know much about binary trees or other such
data structures...

Obviously we need to create a tree simply to track to the bifurcating
responses

 

[Paul Irofti]

#!/usr/bin/env ruby -wKU

class AVLTree

def initialize
@contents = []
end

def empty?
@contents.empty?
end

def include?(obj)
@contents.include?(obj)
end

def <<(obj)
@contents << obj
end

def height
1
end

I think that the second assert against 1 was a typo, instead of 2 he
typed 1, the idea being to implement height.

I see there was another answer to my pong instead this one. Who's the
arbiter here? Or referee? Or jury? (-: I think we'll need one.

 

[Eric I.]

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

 

[Eric I.]

I see there was another answer to my pong instead this one. Who's the
arbiter here? Or referee? Or jury? (-: I think we'll need one.

In an earlier discussion with James, I think forks are OK. People
will vote with their fingertips. We may end up with two or more
competing implementations. Or the wisdom of the crowds will prune
cruelly leaving one dominant branch.

Eric

 

[Paul Irofti]

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.

 

[Rick DeNatale]

I'll settle that. Since your tests were equivalent, I went with
Rick's since I saw it first:

avl_tree.rb

#!/usr/bin/env ruby -wKU

class AVLTree

def initialize
@contents = []
end

def empty?
@contents.empty?
end

def include?(obj)
@contents.include?(obj)
end

def <<(obj)
@contents << obj
end

def height
1
end

end
_END_

test_avl_tree.rb
#!/usr/bin/env ruby -wKU

require "test/unit"

require "avl_tree"

class TestAVLTree < Test::Unit::TestCase
def setup
@tree = AVLTree.new
end

def test_tree_membership
assert_equal(true, @tree.empty?)
assert_equal(false, @tree.include?(3))

@tree << 3

assert_equal(false, @tree.empty?)
assert_equal(true, @tree.include?(3))
end

def test_tree_should_allow_more_than_one_element
@tree << 3
@tree << 4

assert(@tree.include?(4))
assert(@tree.include?(3))
end

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_should_be_greater_than_1
@tree << 5
@tree << 6
@tree << 7
assert(@tree.height > 1, "Tree appears to have stunted growth.")
end
end
_END_

 

[Rick DeNatale]

Obviously we need to create a tree simply to track to the bifurcating
responses

I'm afraid that mail is going to be a terrible way to do this.

Something like subversion would work much better. Your commit would
either succeed or you'd know that you had to reset and respond to
someone who beat you to it instead.

And gmails hide quoted text is making it almost impossible for me to
follow this already.

 

[Adam Shelly]

I'm pinging Rick's last pong. But I am changing one of Ken's tests to
agree with Paul - A tree with one node has height 1, and a tree with
two or three has height 2.

(I think the zip file is a bad idea - I don't want to have to download
each submission. I'm sticking with cut and paste).

avl_tree.rb
#!/usr/bin/env ruby -wKU

class AVLTree

def initialize
@contents = []
end

def empty?
@contents.empty?
end

def include?(obj)
@contents.include?(obj)
end

def <<(obj)
@contents << obj
end

def height
@contents.length
end

end

_END_

test_avl_tree.rb

#!/usr/bin/env ruby -wKU

require "test/unit"

require "avl_tree"

class TestAVLTree < Test::Unit::TestCase
def setup
@tree = AVLTree.new
end

def test_tree_membership
assert_equal(true, @tree.empty?)
assert_equal(false, @tree.include?(3))

@tree << 3

assert_equal(false, @tree.empty?)
assert_equal(true, @tree.include?(3))
end

def test_tree_should_allow_more_than_one_element
@tree << 3
@tree << 4

assert(@tree.include?(4))
assert(@tree.include?(3))
end

def test_tree_height_of_one_or_two_nodes_is_N
@tree << 5
assert_equal 1, @tree.height
@tree << 6
assert_equal 2, @tree.height #changed from 1
end


def test_tree_height_of_three_nodes_should_be_greater_than_1
@tree << 5
@tree << 6
@tree << 7
assert(@tree.height > 1, "Tree appears to have stunted growth.")
end

def test_tree_growth_limit_is_1pt44_log_N
(1..10).each{|i|
@tree << i
limit = (1.44 * Math::log(i)).ceil+1
assert( @tree.height <= limit, "Tree of #{i} nodes is too tall
by #{@tree.height - limit}")
}
end

end

_END_

-Adam

 

[Eric I.]

avl_tree.rb
__BEGIN__
#!/usr/bin/env ruby -wKU
class AVLTree
def initialize
@contents = []
end

def empty?
@contents.empty?
end

def include?(obj)
@contents.include?(obj)
end

def <<(obj)
@contents << obj
end

def height
(Math.log(@contents.size + 1) / Math.log(2)).round
end

def to_a
end
end
__END__

test_avl_tree.rb
__BEGIN__
#!/usr/bin/env ruby -wKU
require "test/unit"
require "avl_tree"
class TestAVLTree < Test::Unit::TestCase
def setup
@tree = AVLTree.new
end

def test_tree_membership
assert_equal(true, @tree.empty?)
assert_equal(false, @tree.include?(3))
@tree << 3
assert_equal(false, @tree.empty?)
assert_equal(true, @tree.include?(3))
end

def test_tree_should_allow_more_than_one_element
@tree << 3
@tree << 4
assert(@tree.include?(4))
assert(@tree.include?(3))
end

def test_tree_height_of_one_node_is_one
@tree << 5
assert_equal 1, @tree.height
end

def test_tree_height_of_two_or_three_nodes_is_two
@tree << 5
@tree << 6
assert_equal 2, @tree.height
@tree << 3
assert_equal 2, @tree.height
end

def test_tree_height_of_two_or_three_nodes_is_two
@tree << 5
@tree << 6
assert_equal 2, @tree.height
@tree << 3
assert_equal 2, @tree.height
end

def test_to_a_returns_items_in_order
@tree << 5
@tree << 6
@tree << 3

assert_equal [3, 5, 6], @tree.to_a
end

# defunct tests no longer used

def defunct_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 defunct_test_tree_height_of_three_nodes_is_two
@tree << 5
@tree << 6
@tree << 7
assert_equal 2, @tree.height
end
end

 

[Eric I.]

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.

Well I think a lower bound would be log2(@content.length + 1). The
upper-bound would be, I assume, what is described in the Wikipedia
article.

Anyway, I tried to fix the height assumptions in Rob's and Ken's
submissions according to what you and I seem to be saying. I was
uncomfortable with negating others' tests, and perhaps I should have
made a parallel branch to Rob's submission. Anyway, perhaps you can
take the next step.

Eric

 

[Adam Shelly]

I agree with Eric's assumptions about the tree height, and his
solution passes my previous test case even though he didn't include
it.
I'm going to try to unify some of these branches by
-including my last test case,
-solving his new one,
- and adding a new one of my own.

avl_tree.rb
__BEGIN__

#!/usr/bin/env ruby -wKU

class AVLTree

def initialize
@contents = []
end

def empty?
@contents.empty?
end

def include?(obj)
@contents.include?(obj)
end

def <<(obj)
@contents << obj
end

def height
(Math.log(@contents.size + 1) / Math.log(2)).round
end

def to_a
@contents.sort
end

end

__END__

test_avl_tree.rb
__BEGIN__

#!/usr/bin/env ruby -wKU
require "test/unit"
require "avl_tree"
class TestAVLTree < Test::Unit::TestCase
def setup
@tree = AVLTree.new
end

def test_tree_membership
assert_equal(true, @tree.empty?)
assert_equal(false, @tree.include?(3))
@tree << 3
assert_equal(false, @tree.empty?)
assert_equal(true, @tree.include?(3))
end

def test_tree_should_allow_more_than_one_element
@tree << 3
@tree << 4
assert(@tree.include?(4))
assert(@tree.include?(3))
end


def test_tree_height_of_one_node_is_one

@tree << 5
assert_equal 1, @tree.height

end

def test_tree_height_of_two_or_three_nodes_is_two
@tree << 5
@tree << 6

assert_equal 2, @tree.height
@tree << 3
assert_equal 2, @tree.height
end

def test_to_a_returns_items_in_order
@tree << 5
@tree << 6
@tree << 3

assert_equal [3, 5, 6], @tree.to_a
end

def test_tree_growth_limit_is_1pt44_log_N
(1..10).each{|i|
@tree << i
limit = (1.44 * Math::log(i)).ceil+1
assert( @tree.height <= limit, "Tree of #{i} nodes is too tall
by #{@tree.height - limit}")
}
end

def test_tree_balance_factor
@tree << 4
assert(@tree.balance_factor == 0)
@tree << 5
assert(@tree.balance_factor == 1)
@tree << 6
assert(@tree.balance_factor == 2)
end

end

 

[Paul Irofti]

I'm pinging Rick's last pong. But I am changing one of Ken's tests to
agree with Paul - A tree with one node has height 1, and a tree with
two or three has height 2.

Then its settled.

(I think the zip file is a bad idea - I don't want to have to download
each submission. I'm sticking with cut and paste).

Me too.

Here's my pong mister:

The lib:

#!/usr/bin/env ruby -wKU

class AVLTree

def initialize
@contents = []
end

def empty?
@contents.empty?
end

def include?(obj)
@contents.include?(obj)
end

def <<(obj)
@contents << obj
end

def height
Math::log(@contents.length).ceil
end

def remove(node)
end

end

Test case:

#!/usr/bin/env ruby -wKU

require "test/unit"

require "avl_tree"

class TestAVLTree < Test::Unit::TestCase
def setup
@tree = AVLTree.new
end

def test_tree_membership
assert_equal(true, @tree.empty?)
assert_equal(false, @tree.include?(3))

@tree << 3

assert_equal(false, @tree.empty?)
assert_equal(true, @tree.include?(3))
end

def test_tree_should_allow_more_than_one_element
@tree << 3
@tree << 4

assert(@tree.include?(4))
assert(@tree.include?(3))
end

#disabled this test case as it is order dependent and not valid
# def test_tree_height_of_one_or_two_nodes_is_N
# @tree << 5
# assert_equal 1, @tree.height
# @tree << 6
# assert_equal 2, @tree.height #changed from 1
# end


def test_tree_height_of_three_nodes_should_be_greater_than_1
@tree << 5
@tree << 6
@tree << 7
assert(@tree.height > 1, "Tree appears to have stunted growth.")
end

def test_tree_growth_limit_is_1pt44_log_N
(1..10).each{|i|
@tree << i
limit = (1.44 * Math::log(i)).ceil+1
assert( @tree.height <= limit, "Tree of #{i} nodes is too tall
by #{@tree.height - limit}")
}
end

def test_remove_node

@tree << 314
@tree.remove(314)
assert([email protected]?(314))
end

end

 

[Rob Biedenharn]

I'm pinging Rick's last pong. But I am changing one of Ken's tests to
agree with Paul - A tree with one node has height 1, and a tree with
two or three has height 2.

(I think the zip file is a bad idea - I don't want to have to download
each submission. I'm sticking with cut and paste).

def test_tree_height_of_one_or_two_nodes_is_N
@tree << 5
assert_equal 1, @tree.height
@tree << 6
assert_equal 2, @tree.height #changed from 1
end

Well, I went to lunch and came back to a whole mess of new messages.
After a careful rereading of how internal and external nodes are
defined, I agree with this. Quoting Don Knuth's The Art of Computer
Programming, Volume 3, Sorting and Searching (2nd ed.), section 6.2.3.
Balanced Trees, p.459

The height of a tree is defined to be its maximum level,
the length of the longest path from the root to an
external node.

External nodes are effectively the empty left or right subtrees of an
internal node. I'll represent external nodes as a lowercase 'o' in
the rest of this message.

The first value added needs one internal node and has two external
nodes:
* 5
* / \
* o o
This has height == 1.

Adding a second value and keeping the (binary) tree balanced needs
only a new external node:
* 5
* / \
* o 6
* / \
* o o

If the values are added in the opposite order:
* 6
* / \
* 5 o
* / \
* o o

This still has height == 2 for any two values. So I have to disagree
with Paul's comment that the test is either order dependent or
otherwise not valid.

Again, quoting from p.459:

A binary tree is called balanced if the height of the
left subtree of every node never differs by more than
+/-1 from the height of its right subtree.

Adding a third value results in one of three possible trees:
* 5.
* / \
* 4. 7.
* /| |\
* o o o o

* 6.
* / \
* 5. 7.
* /| |\
* o o o o

* 7.
* / \
* 5. 8.
* /| |\
* o o o o

All of these trees have height 2. Any other configuration is an
unbalanced tree. For example, showing the balance factor
[height(right)-height(left)] of the node as '.' for zero, '+' for +1,
'-' for -1, and '++' for +2.
* 4++
* / \
* o 7-
* / \
* 5. o
* / \
* o o


def test_tree_growth_limit_is_1pt44_log_N
(1..10).each{|i|
@tree << i
limit = (1.44 * Math::log(i)).ceil+1
assert( @tree.height <= limit,
"Tree of #{i} nodes is too tall by #{@tree.height -
limit}")
}
end

The theorem you're trying to capture is on p.460:

The height of a balanced tree with N internal nodes
always lies between lg(N+1) and 1.4405*lg(N+2)-0.3277

Your upper limit should be:
limit=(1.4405*Math::log(i+2)/Math::log(2)-0.3277).ceil
In any case, I'd argue that this test is certainly not among the
aspects of a tree that I would expect to be added next.

Besides, the code to calculate the, so called, "height" is moot.
There's no "tree" in the data structure upon which a real height can
be said to exist. I see no need to put the Math library to the test ;-)

-Adam

I have to hit send on this before even more messages arrive! No pings
or pongs in this message, but soon!

-Rob

Rob Biedenharn http://agileconsultingllc.com
(e-mail address removed)