Programmer Ping-Pong (#150)

On Dec 14, 2007, at 1:24 PM, Adam S. wrote:

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.
    
  • / \
    
  • /| |\

  • o o o o

  •  6.
    
  • / \
    
  • /| |\

  • o o o o

  •  7.
    
  • / \
    
  • /| |\

  • 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 :wink:

-Adam

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

-Rob

Rob B. http://agileconsultingllc.com
[email protected]

On 2007-12-14, Adam S. [email protected] wrote:

On 12/14/07, Rick DeNatale [email protected] wrote:

On 12/14/07, Rob B. [email protected] wrote:

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

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(!@tree.include?(314))
end

end

On 14/12/2007, Eric I. [email protected] wrote:

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

Now I think this one is misleading. Here you choose to lie about the
tree height. There is no way one can detect this by a test, a list
passes for a binary tree at any time. It is just somewhat unbalanced -
the real height is @contents.length

def to_a
end
end
END

Thanks

Michal

On Dec 14, 2007, at 9:30 AM, John J. wrote:

How do you prevent or at least reign in the splintering/forking of
code and likely duplication of efforts here?

I spent a great deal of time considering this issue and discussed the
pros and cons with multiple Ruby Q. fans. In the end, I decided
forking was acceptable. This gives you more choices as a solver, find
a failing test you want to make pass and go for it!

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…

There couldn’t be a more perfect opportunity to learn a little about
binary trees. Remember, you only need to make one test pass. Watch
for your chance! :wink:

James Edward G. II

On Dec 14, 4:12 pm, Michal S. [email protected] wrote:

On 14/12/2007, Eric I. [email protected] wrote:

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

Now I think this one is misleading. Here you choose to lie about the
tree height. There is no way one can detect this by a test, a list
passes for a binary tree at any time. It is just somewhat unbalanced -
the real height is @contents.length

I think that’s a valid criticism. It was a failed attempt to make it
work using the simplest change. I feel like I need to let someone
else fix it, though.

Eric

On Dec 14, 2007, at 10:55 AM, Paul I. wrote:

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.

You are. Vote with your reply feature.

James Edward G. II

On Dec 14, 2007, at 9:14 AM, Paul I. wrote:

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.

The official response is that it is settled by anyone who responds.
Forking is OK. I vote we don’t stress about it too much.

Feel free to invoke the kindness clause of the rules and unify tests
as well.

James Edward G. II

On Dec 14, 2:12 pm, Michal S. [email protected] wrote:

end
@contents << obj
end

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

Now I think this one is misleading. Here you choose to lie about the
tree height. There is no way one can detect this by a test, a list
passes for a binary tree at any time. It is just somewhat unbalanced -
the real height is @contents.length

So…write a failing test case :slight_smile:

On Dec 14, 2007, at 11:47 AM, Robert D. wrote:

I agree but nobody followed the rules so far, we would need a zip
with both files, right?

The rules did not ask for a zip file, no.

James Edward G. II

Shoot, I’ll give it a whirl, it beats the meta discussion. I added a
check for branch contents, I think that qualified as an aspect per the
quiz rules.

  • donald

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
Math::log(@contents.length).ceil
end

def remove(obj)
@contents.delete(obj)
end

end

#!/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(!@tree.include?(314))
end

def test_has_branches
[50, 17, 72].each {|n| @tree << n}
assert(50 == @tree.value)
assert(17 == @tree.left.value)
assert(72 == @tree.right.value)
end

end

This one is really a tree for once.

#!/usr/bin/env ruby -wKU

class TreeNode

attr_accessor :left, :right, :data, :parent

def initialize obj
@left=nil
@right=nil
@data=obj
@parent=nil
end

def attach_left node
@left = node
node.parent = self
end

def attach_right node
@right = node
node.parent = self
end

def height
max( (left.height rescue 0) , (right.height rescue 0) )+1
end

def max *args
args.inject{|m,n| n>m ? n : m}
end

def << node
left ? (right ? (left << node) : (attach_right node)) : (attach_left
node)
end

def include? obj
(@data == obj) ||
(@left.include? obj rescue false) ||
(@right.include? obj rescue false)
end

def length
len = 1
len += @left.length if left
len += @right.length if right
end

end

class AVLTree

def initialize
@root = nil
end

def empty?
! @root
end

def include?(obj)
(! empty?) && (@root.include? obj)
end

def <<(obj)
if empty?
@root = TreeNode.new obj
else
@root << TreeNode.new(obj)
end
self
end

def height
empty? ? 0 : @root.height
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_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_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(! @tree.include?(i), "Tree should not include #{i} yet.")
    @tree << i
    0.upto(i) do |j|
      assert( @tree.include?(j), "Tree should include #{j} 

already.")
end
end
end

def test_tree_traverse
  ary = [3,5,17,30,42,54,1,2]
  ary.each{|n| @tree << n}
  traversal = []
  @tree.each{|n| traversal << n}
  ary.each{|n| assert traversal.include?(n), "#{n} was not visited

in tree."}
end

end
end

On Dec 14, 2007, at 11:37 AM, Rick DeNatale wrote:

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

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.

I also considered using Subversion over email. The decision here was
much closer than the forking issue, but in the end I selected email
for various reasons. I’m not sure if that was the best choice or not
though.

James Edward G. II

On 14/12/2007, John J. [email protected] wrote:

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…

There’s nothing difficult about trees. There is a root at the top, and
from there the branches grow. While binary trees can split only into
two branches in one place other trees grow thicker :wink:

And if you do not know about AVL trees somebody posted a link to
article explaining them already. Even if that looks too long, the quiz
is still far from the point when you would use it :slight_smile:

Thanks

Michal

On Dec 14, 2007, at 3:06 PM, Rob B. wrote:

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 :wink:

Yes, I think we should keep testing the concrete features. A height
should naturally emerge from that as needed.

James Edward G. II

On 12/14/07, Ball, Donald A Jr (Library) [email protected]
wrote:

Shoot, I’ll give it a whirl, it beats the meta discussion. I added a
check for branch contents, I think that qualified as an aspect per the
quiz rules.

  • donald

So I made it a simple tree.
I guess maybe it was premature of me to add the tree growthlimit test
earlier - I had to add some balancing right away in order to get the
tree to pass.
My new test makes the balancing requirement tighter.

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

class AVLTree
attr_accessor :left, :right
def initialize
@content = nil
@left = @right = nil
end

def empty?
!@content
end

def include?(obj)
(@content == obj) ||
(@left and @left.include?(obj)) ||
(@right and @right.include?(obj)) ||
false
end

def <<(obj)
if empty?
@content = obj
else
@left ||= AVLTree.new
@right ||= AVLTree.new
if obj < @content
@left << obj
else
@right <<obj
end
balance = @right.height - @left.height
if (balance > 1)
pivot = @right
@right = pivot.left
pivot.left = self
end
end
self
end

def height
lh = (@left && @left.height)||0
rh = (@right&&@right.height)||0
1 + [lh,rh].max
end

def remove(obj)
if @content == obj
@content = nil
else
@left.remove(obj)
@right.remove(obj)
end
end

def value
@content
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

#disabled this test case as it is order dependent and not valid
#re-enabled, I think it is 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(!@tree.include?(314))
end

def test_has_branches
[50, 17, 72].each {|n| @tree << n}
assert(50 == @tree.value)
assert(17 == @tree.left.value)
assert(72 == @tree.right.value)
end

def test_balances_left
4.downto(1){|i| @tree << i}
assert(@tree.height<4)
end

end

END

-Adam

(redirecting to Ruby T. so we can all discuss)

On Dec 14, 2007, at 9:46 AM, Eivind E. wrote:

This is getting branching problems - people are writing new code
during the mailing list delays. I’ve send out my reply when there
were no others at that level, and I’m seeing the same problem occuring
several times. I suggest that you change the rules to have people
mail you their pongs, and then you post them - then only one will be
posted as official at each level. It will slow things down, but it
will also avoid the total branching that the mailing list slowness
gives (I see up towards 20 minute delays in mailing list posting,

I’m not too concerned with branching issues and I have no idea how I
would pick who’s code to send in to the list. I will never be as fair
as you will be by picking a test you want to make pass and replying.

James Edward G. II

Here is a modification that joins both of the latest forks. It answers
both
of your challenges:

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

class TreeNode

attr_accessor :left, :right, :data #, :parent

def initialize(obj = nil)
@left=nil
@right=nil
@data=obj
end

def attach_left node
@left = node
end

def attach_right node
@right = node
end

def height
[(left.height rescue 0) , (right.height rescue 0)].max + 1
end

def include? obj
(@data == obj) ||
(@left.include? obj rescue false) ||
(@right.include? obj rescue false)
end

def length
len = 1
len += @left.length if left
len += @right.length if right
end

end

class AVLTree

def initialize
@root = nil
end

def empty?
! @root
end

def include?(obj)
(! empty?) && (@root.include? obj)
end

def <<(obj)
if empty?
@root = TreeNode.new obj
else
@root = insert(obj, @root)
end
self
end

def insert(obj, node)
if node == nil
node = TreeNode.new(obj)
elsif obj < node.data
node.left = insert(obj, node.left)
elsif obj > node.data
node.right = insert(obj, node.right)
end

balance = (node.left.height rescue 0) - (node.right.height rescue
0).abs
if balance > 1
if (obj < node.data)
if (obj < node.left.data)
node = rotate_with_left_child(node)
end
end
end
node
end

def rotate_with_left_child(node)
new_parent = node.left

node.left = new_parent.right
new_parent.right = node
new_parent
end

def height
empty? ? 0 : @root.height
end

def each
list = list_nodes(@root, [])
for data in list
yield data
end
end

def list_nodes(node, list)
list_nodes(node.left, list) if node.left != nil
list << node.data if node.data != nil
list_nodes(node.right, list) if node.right != nil
list
end
end

test_avl_tree.rb

require “test/unit”
require “avl_tree.rb”

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_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_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(! @tree.include?(i), “Tree should not include #{i} yet.”)
@tree << i
0.upto(i) do |j|
assert( @tree.include?(j), “Tree should include #{j} already.”)
end
end
end

def test_tree_traverse
ary = [3,5,17,30,42,54,1,2]
ary.each{|n| @tree << n}
traversal = []
@tree.each{|n| traversal << n}
assert_equal(ary.size, traversal.size)
ary.each{|n| assert traversal.include?(n), “#{n} was not visited in
tree.”}
end

def test_balances_left
4.downto(1){|i| @tree << i}
assert(@tree.height<4)
end

def test_balances_right
0.upto(4){|i| @tree << i}
assert(@tree.height<4)
end

end

On Dec 14, 2007 11:26 PM, James G. [email protected] wrote:

On Dec 14, 2007, at 11:47 AM, Robert D. wrote:

I agree but nobody followed the rules so far, we would need a zip
with both files, right?

The rules did not ask for a zip file, no.
Indeed you asked not to put the solutions into a zip file, my bad :frowning:
Robert

http://ruby-smalltalk.blogspot.com/


All truth passes through three stages. First, it is ridiculed. Second,
it is violently opposed. Third, it is accepted as being self-evident.
Schopenhauer (attr.)

On Dec 14, 2007, at 12:20 PM, Paul I. wrote:

@tree << 6

with two or three pieces of data should be larger (by one) than that
code
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 B. http://agileconsultingllc.com
[email protected]

On Dec 14, 2007, at 6:42 PM, Michal S. wrote:

This one is really a tree for once.

This was quite close to what I had at the time, so that’ why the reply
is to Michal’s message. I’ve also incorporated tests from Adam S.
and Justin E., but see the comments for how I’ve softened them and
why.

I moved Michal’s TreeNode into AVLTree::Node since I don’t believe it
should be at the top level. I also created an AVLTree::ExternalNode
to duck-type with AVLTree::Node as a special kind of nil alternative
to clean up a lot of code that would otherwise need to make a special
case of @left or @right being nil.

Also, I’ve included my package and extract scripts that can pull the
code into separate files. To bootstrap, go to the bottom and past the
code for extract into a file, then run that file and give it the whole
message as input (or just the part starting below here).

I’ve also been very strict about the indentation and width of the
lines so the mailer shouldn’t break any lines.

I’m using Knuth’s “The Art of Computer Programming” as a guide where
the benefits of an AVL Tree are defined as:

… and it never uses more than O(log N) operations
to search the tree or insert an item. In fact, we
shall see that thier approach also leads to a general
technique that is good for representing arbitrary
linear lists of length N, so that each of the
following operations can be done in only O(log N)
units of time:

   i) Find an item having a given key
  ii) Find the k-th item, given k
 iii) Insert an item at a specified place
  iv) Delete a specified item

I’m tending to ignore (iii) and assume that the “specified place” is
implicit in the value of the object being inserted. I’m also ignoring
(iv) because it’s hard (see the comment in the test file for more).

As a result of (i) and (iii), I ended up rejecting duplicates and
there’s an already passing test that shows this so I stretched the
“one new failing test” rule.

-Rob

Rob B. http://agileconsultingllc.com
[email protected]

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

class AVLTree

Need something smarter than nil for external nodes

class ExternalNode
attr_accessor :parent
def initialize(parent)
@parent = parent
end
def include?(); false; end
def <<(
); raise RuntimeError; end
def height; 0; end
def balance_factor; 0; end
def left; self; end
def right; self; end
def left=(node)
raise(NotImplementedError,
“external node of #{@parent}”)
end
def right=(node)
raise(NotImplementedError,
“external node of #{@parent}”)
end
def to_s; ‘’; end
def to_a; []; end
end

class Node
attr_accessor :data, :parent
attr_reader :left, :right

 def initialize obj
   @parent = nil
   @data   = obj
   @left   = ExternalNode.new(self)
   @right  = ExternalNode.new(self)
 end

 def left=(node)
   @left = node
   node.parent = self
 end

 def right=(node)
   @right = node
   node.parent = self
 end

 def height
   [ @left.height, @right.height ].max + 1
 end

 def << node
   case node.data <=> @data
   when -1
     if Node === @left
       @left << node
     else
       self.left = node
     end
   when 0
     return self             # no dups
   when +1
     if Node === @right
       @right << node
     else
       self.right = node
     end
   end
   rebalance if balance_factor.abs > 1
 end

 def include? obj
   case obj <=> @data
   when -1 : @left.include?(obj)
   when  0 : true
   when +1 : @right.include?(obj)
   end
 end

 def to_a
   result = @left.to_a
   result << @data
   result.concat @right.to_a
   result
 end

 def to_s
   bf = case balance_factor <=> 0
        when -1 : '-' * -balance_factor
        when  0 : '.'
        when  1 : '+' * balance_factor
        end
   "[#{left} "+
     "(#{@data}{#{height}#{bf}}^#{parent.data})"+
     " #{right}]"
 end

 protected

 def balance_factor
   @right.height - @left.height
 end

 def rebalance
   if (bf = balance_factor) > 1
     # right is too high
     if @right.balance_factor > 0
       # single rotate left
       my_parent, from, to = @parent, self, @right
       temp = @right.left
       @right.left = self
       self.right = temp
       my_parent.send :replace_child, from, to
       to.parent = my_parent
     else
       # double rotate right-left
       raise(NotImplementedError,
             "double rotate right-left for #{self}")
     end
   elsif bf < -1
     # left must be too high
     if @left.balance_factor < 0
       # single rotate right
       my_parent, from, to = @parent, self, @left
       temp = @left.right
       @left.right = self
       self.left = temp
       my_parent.send :replace_child, from, to
       to.parent = my_parent
     else
       raise(NotImplementedError,
             "double rotate left-right for #{self}")
     end
   end
 end

 def replace_child(from, to)
   if from.eql? @left
     @left = to
   elsif from.eql? @right
     @right = to
   else
     raise(ArgumentError,
           "#{from} is not a branch of #{self}")
   end
 end

end

def initialize
@root = nil
end

def empty?
@root.nil?
end

def include?(obj)
empty? ? false : @root.include?(obj)
end

def <<(obj)
raise(ArgumentError,
“Objects added to #{self.class.name} must” +
" respond to <=>"
) unless obj.respond_to?(:<=>)

 if empty?
   @root = Node.new(obj)
   @root.parent = self
 else
   @root << Node.new(obj)
 end
 self

end

def height
empty? ? 0 : @root.height
end

naive implementation [not O(lg N)]

def

to_a[idx]

end

def to_a
empty? ? [] : @root.to_a
end

naive implementation [not O(lg N)]

def each
to_a.each {|e| yield e}
end

def to_s
empty? ? “[]” : @root.to_s
end

Indicates that parent is root in to_s

def data; ‘*’; end

protected

def replace_child(from, to)
if @root.eql? from
@root = to
else
raise(ArgumentError,
“#{from} is not a branch of #{self}”)
end
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

##################################################

Membership tests

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), "4 not in #{@tree}")
 assert(@tree.include?(3), "3 not in #{@tree}")

end

def test_tree_include_many
0.upto(10) do |i|
assert_equal(false, @tree.include?(i),
“Tree should not include #{i} yet.”)
@tree << i
0.upto(i) do |j|
assert_equal(true, @tree.include?(j),
“Tree should have 0…#{i},”+
" where’s #{j}? ")
end
end
end

This sits at the intersection of membership

and height tests. We know one node has height 1,

and two nodes has height 2, so if we insert one

object twice and the height is 1, there must

only be one node in the tree.

def test_tree_does_not_keep_duplicates
@tree << ‘a’
@tree << ‘a’
assert_equal 1, @tree.height, “one node: #{@tree}”
end

##################################################

Height tests

def test_tree_height_of_one_or_two_nodes_is_N
@tree << 5
assert_equal 1, @tree.height, “one node: #{@tree}”
@tree << 6
assert_equal 2, @tree.height, “two nodes: #{@tree}”
end

def test_tree_height_of_three_nodes_is_two
@tree << 5
@tree << 6
@tree << 7
assert_equal 2, @tree.height, @tree.to_s
end

RobB: The more precise limit given in [Knuth] is

used rather than that from [Wikipedia]

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

def test_balances_left
4.downto(1) { |i| @tree << i }
assert(@tree.height < 4,
“expected tree height #{@tree.height} < 4”)
end

def test_balances_right
1.upto(4) { |i| @tree << i }
assert(@tree.height < 4,
“expected tree height #{@tree.height} < 4”)
end

def test_non_sequential_insertion__part_1
items = [ 1, 3, 2 ]
items.each do |i|
@tree << i
end
items.each do |i|
assert_equal(true, @tree.include?(i),
"where is #{i}? ")
end
end

##################################################

Access tests (getting data back out)

RobB: this tests too much at one time; I sorted ary.

def test_tree_traverse
ary = [ 3, 5, 17, 30, 42, 54, 1, 2 ].sort
ary.each { |n| @tree << n }
traversal = []
@tree.each { |n| traversal << n }
assert_equal(ary.size, traversal.size)
ary.each do |n|
assert_equal(true, traversal.include?(n),
“#{n} was not visited in tree.”)
end
end

##################################################

Things that aren’t tested anymore…

[Knuth] p.473: "The problem of deletion can be solved

in O(log N) steps if we approach it correctly."

RobB: I’m choosing to skip this capability since

the test was added before an actual tree structure

emerged.

def future__test_remove_node
@tree << 314
@tree.remove(314)
assert_equal(false, @tree.include?(314),
‘314 still in the tree’)
end

RobB: While I think the spirit of this test is good,

it attempts to expose the implementation too much.

I replaced this with test_sequential_access.

def never__test_has_branches
[50, 17, 72].each {|n| @tree << n}
assert_equal 50, @tree.data
assert_equal 17, @tree.left.data
assert_equal 72, @tree.right.data
end

end
=begin
[Knuth] Knuth, Donald Ervin,
The Art of Computer Programming, 2nd ed.
Volume 3, Sorting and Searching,
section 6.2.3 “Balanced Trees”, pp. 458-478
[Wikipedia]
AVL Tree, AVL tree - Wikipedia
=end
END

==> package <==
#!/usr/bin/env ruby -wKU

-- ruby --

Dir[ARGV[0] || ‘*.rb’].each do |f|
lines = IO.readlines(f)
lines.unshift “==> #{f} <==\n”
lines << “END\n” unless lines.last.chomp == ‘END
lines << “\n”
puts lines
end
END

==> extract <==
#!/usr/bin/env ruby -wKU

-- ruby --

file = nil
state = :init
ARGF.each do |line|
case state
when :init
next unless line =~ /^==> (.*) <==$/
if File.exist?($1)
backup = $1+‘~’
File.delete(backup) if File.exist?(backup)
File.rename($1, backup)
end
file = File.open($1, ‘w’)
state = :writing
when :writing
file.write line
if line.chomp == ‘END
file.close
state = :init
end
end
end
END