# Re: Programmer Ping-Pong (#150)

**URL:** <https://www.ruby-forum.com/t/re-programmer-ping-pong-150/229151>\
**Category:** Ruby\
**Created:** [December 19, 2007, 4:36am UTC](https://www.ruby-forum.com/t/re-programmer-ping-pong-150/229151 "2007-12-19T04:36:01Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![jameskelly](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ab097/32.png) [@jameskelly](https://www.ruby-forum.com/u/jameskelly)\
**Post date:** [December 19, 2007, 4:36am UTC](https://www.ruby-forum.com/t/re-programmer-ping-pong-150/229151/1 "2007-12-19T04:36:01Z")

</div>

I just realized that it might be a good idea to change my test to make  
each accept an options hash rather than ordered arguments, since my  
change and my new test will cause each to accept two keyword arguments.  
That is, rather than having calls like

@tree.each(:postorder,:node){…}

having something along the lines of

@ree.each(:traversal=\>:postorder,:val=\>:node)

----- Original Message ----  
From: James K. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
To: ruby-talk ML [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
Sent: Tuesday, December 18, 2007 8:23:35 PM  
Subject: Re: [QUIZ] Programmer Ping-Pong (#150)

On 12/18/07, Adam S. wrote:

> I added test\_remove\_multiple\_nodes - there are definitely a few  
> mistakes in the current remove 🙂

Seems the only mistake was that remove was expecting AVLTree#each to  
return the node traversed, but it was instead returning the node’s  
data.  
I modified each to accept the name of a function to be passed to  
itself, which defaults to data. I made an “identity” method called  
node, and  
the passed it in when each is called within remove.

For my test, each and to\_a must now accept symbols denoting the type of  
traversal to be performed, including inorder (the current traversal),  
preorder, postorder, and level-by-level.

==\>avl\_tree.rb\<==  
class AVLTree

include Enumerable

# 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 each(\*args,&iter) 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, sortblock
  @parent = nil
  @data = obj
  @left = ExternalNode.new(self)
  @right = ExternalNode.new(self)
  @height = 1
  @compare = sortblock
end

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

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

def each(returns=:data,&iter)
  @left.each(&iter)
  iter[self.send(returns)]
  @right.each(&iter)
end

def node
  self
end

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

def << node
  case @compare[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
  @height = nil
end

def remove obj
  @height = nil
  case @compare[obj,@data]
  when -1
    if Node === @left
      @left.remove(obj)
    else
      nil
    end
  when 0
    if Node === @left
      largest = nil
      AVLTree.new(@left).each(:node) do |n|
        largest = n if largest.nil? or n.data > largest.data
        largest = n if largest.nil? or n.data > largest.data
      end
      self.data = largest.data
      self.left = largest.left
    elsif Node === @right
      smallest = nil
      AVLTree.new(@right).each(:node) do |n|
        smallest = n if smallest.nil? or n.data < smallest.data
        smallest = n if smallest.nil? or n.data < smallest.data
      end
      self.data = smallest.data
      self.right = smallest.right
    else
      parent.send :replace_child, self, ExternalNode.new(parent)
    end
    path = self
    while Node === (path = path.parent)
      path.rebalance if path.balance_factor.abs > 1
    end
    self
  when +1
    if Node === @right
      @right.remove(obj)
    else
      nil
    end
  end
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 [](idx)
    if idx < (leftheight = @left.height)
      @left[idx]
    elsif (idx== leftheight)
      @data
    elsif (idx-=(leftheight+1)) < @right.height
      @right[idx]
    end
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 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
end

def 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
end

def rebalance
  if (bf = balance_factor) > 1 # right is too high
    if @right.balance_factor < 0
      # double rotate right-left
      # - first the right subtree
      @right.rotate_right
    end
    rotate_left # single rotate left
  elsif bf < -1 # left must be too high
    if @left.balance_factor > 0
      # double rotate left-right
      # - first force left subtree
      @left.rotate_left
    end
    rotate_right # single rotate right
  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, &block)  
@root = root  
if block  
raise(ArgumentError,  
“Block argument for #{self.class.name} must” +  
" take 2 arguments and act as sort function"  
) unless block.arity == 2  
else  
block = proc{|a,b| a\<=\>b}  
end  
@compare = block  
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, @compare)
  @root.parent = self
else
  @root << Node.new(obj, @compare)
end
self

```

end

def remove(obj)  
@root.remove(obj) unless empty?  
end

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

def   
@root[idx]  
end

def to\_a  
empty? ? [] : @root.to\_a  
end

def each(\*args,&iter)  
@root.each(\*args,&iter) unless empty?  
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\<==

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

def test\_non\_sequential\_insertion\_\_part\_2  
items = [3, 1, 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

def test\_alternate\_traversals  
items = [3,2,4,1,5]  
items.each {|el| @tree \<\< el}

```
preorder_result = [3,2,1,4,5]
assert_equal(@tree.to_a(:preorder),preorder_result)
@tree.each(:preorder) {|el| assert_equal(preorder_result.shift,el)}

inorder_result = [1,2,3,4,5]
assert_equal(@tree.to_a(:inorder),inorder_result)
@tree.each(:inorder) {|el| assert_equal(inorder_result.shift,el)}

postorder_result = [1,2,5,4,3]
assert_equal(@tree.to_a(:postorder),postorder_result)
@tree.each(:postorder) {|el|

```

assert\_equal(postorder\_result.shift,el)}

```
bylevel_result = [3,2,4,1,5]
assert_equal(@tree.to_a(:by_level),bylevel_result)
@tree.each(:by_level) {|el| assert_equal(bylevel_result.shift,el)}

```

end

def test\_tree\_find  
[1,2,3,4].each{|n| @tree\<\<n}  
assert\_equal(1, @tree.find{|v|v\>0} )  
assert\_equal(2, @tree.find{|v|v%2==0} )  
end

def test\_sequential\_access  
items = [50, 17, 72]  
items.each { |n| @tree \<\< n }  
items.sort.each\_with\_index do |e,i|  
assert\_equal(e, @tree[i],  
"@tree[#{i}] should be like " +  
“#{items.inspect}.sort[#{i}]”)  
end  
end

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

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

def test\_remove\_node  
@tree \<\< 314  
@tree.remove(314)  
assert\_equal(false, @tree.include?(314),  
‘314 still in the tree’)  
end

```
def test_remove_multiple_nodes
items = [50, 17, 72, 45, 43, 23]
items.each { |n| @tree << n }
puts @tree, @tree.height
@tree.remove(50)
assert_equal(false, @tree.include?(50),
              '50 still in the tree')
@tree.remove(72)
assert_equal(false, @tree.include?(72),
              '72 still in the tree')
@tree.remove(45)
assert_equal(false, @tree.include?(45),
              '45 still in the tree')
assert_equal(2, @tree.height) #tree should have 3 items, height =

```

2  
end

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

# Interface tests

def test\_custom\_comparison\_code  
rev\_tree = AVLTree.new { |a, b| b \<=\> a }  
values = [3, 2, 1]  
values.each { |v| rev\_tree \<\< v }  
rev\_tree.each { |v| assert\_equal(values.shift, v) }

```
len_tree = AVLTree.new { |a, b| a.length <=> b.length }
values = %w[3 22 111]
values.each { |v| len_tree << v }
len_tree.each { |v| assert_equal(values.shift, v) }

```

end

end  
_END_

* * *

Never miss a thing. Make Yahoo your home page.  
[http://www.yahoo.com/r/hs](http://www.yahoo.com/r/hs)

```
  ____________________________________________________________________________________

```

Be a better friend, newshound, and  
know-it-all with Yahoo! Mobile. Try it now.  
[http://mobile.yahoo.com/;\_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ](http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ)

---

<div class="post-metadata">

**Author:** ![jameskelly](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ab097/32.png) [@jameskelly](https://www.ruby-forum.com/u/jameskelly)\
**Post date:** [December 20, 2007, 2:37pm UTC](https://www.ruby-forum.com/t/re-programmer-ping-pong-150/229151/2 "2007-12-20T14:37:15Z")

</div>

On Dec 19, 2007, at 7:01 PM, Adam S. wrote:

> It was also bugging me that we were creating so many ExternalNodes  
> where we didn’t care about the data, only the methods, so I moved all  
> the methods to the class, and removed all the calls to new (I just  
> realized I should have made new private)

Maybe it should be a singleton. As it is, we could switch it to a  
module now too.

James Edward G. II

---

<div class="post-metadata">

**Author:** ![jameskelly](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ab097/32.png) [@jameskelly](https://www.ruby-forum.com/u/jameskelly)\
**Post date:** [December 20, 2007, 2:02am UTC](https://www.ruby-forum.com/t/re-programmer-ping-pong-150/229151/3 "2007-12-20T02:02:36Z")

</div>

On 12/18/07, James K. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> To: ruby-talk ML [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
> I modified each to accept the name of a function to be passed to  
> itself, which defaults to data. I made an “identity” method called node, and  
> the passed it in when each is called within remove.
> 
> For my test, each and to\_a must now accept symbols denoting the type of  
> traversal to be performed, including inorder (the current traversal),  
> preorder, postorder, and level-by-level.

Ok, I did the each and the to\_a. I did not add the hash as suggested

- I don’t think it’s a good idea to provide tree users with nodes  
directly. And I refactored remove so that it didn’t need each(:node)  
anyway. I expanded my previous test\_remove\_multiple\_nodes test to  
help ensure the refactoring was robust.  
It was also bugging me that we were creating so many ExternalNodes  
where we didn’t care about the data, only the methods, so I moved all  
the methods to the class, and removed all the calls to new (I just  
realized I should have made new private)

My new test lets you add and subtract trees.

-Adam

==\> avl\_tree.rb \<==  
class AVLTree

include Enumerable

# Need something smarter than nil for external nodes

# but we dont need all these separate instances - they are all

identical  
class ExternalNode  
def self::include?(_) false end  
def self::height; 0 end  
def self::each(\*args,&iter) end  
def self::each\_level(sequence,&iter)  
sequence.shift.each\_level(sequence,&iter) unless sequence.empty?  
end  
def self::each\_node(&iter) end  
def self::to\_a(_); [] end  
def self::pop; nil end  
def self::shift; nil end  
def self::parent=(p); nil end  
def self::to\_s; ‘’; end  
end

class Node  
attr\_accessor :data, :parent  
attr\_reader :left, :right

```
def initialize obj, sortblock
  @parent = nil
  @data = obj
  @left = ExternalNode
  @right = ExternalNode
  @height = 1
  @compare = sortblock
end

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

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

def each(traversal, &iter)
  case traversal
    when :inorder
      @left.each(traversal,&iter)
       iter[@data]
      @right.each(traversal,&iter)
    when :preorder
       iter[@data]
      @left.each(traversal,&iter)
      @right.each(traversal,&iter)
    when :postorder
      @left.each(traversal,&iter)
      @right.each(traversal,&iter)
       iter[@data]
  end
end

def each_level sequence,&iter
  iter[@data]
  sequence.push @left
  sequence.push @right
  sequence.shift.each_level(sequence,&iter) unless sequence.empty?
end

def each_node &iter
  @left.each_node(&iter)
  iter[self]
  @right.each_node(&iter)
end

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

def << node
  case @compare[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
  @height = nil
end

def remove obj
  case @compare[obj,@data]
  when -1
    @left.remove(obj)
  when 0
    path = @left.pop || @right.shift || drop_self
    self.data = path.data
    while Node === (path = path.parent)
      break if path.balance_factor.abs == 1
      path.rebalance
    end
    self
  when +1
    @right.remove(obj)
  end
end

def drop_self
  parent.send :replace_child, self, ExternalNode#.new(parent)
  self
end

def pop
  @right.pop || drop_self
end

def shift
  @left.shift || drop_self
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 traversal
  left,root,right = @left.to_a(traversal), [@data], 

```

@right.to\_a(traversal)  
case traversal  
when :inorder  
left+root+right  
when :preorder  
root+left+right  
when :postorder  
left+right+root  
when :by\_level  
# pad out the left array so zip gets all the right elements too  
while (left.size \< right.size) do left\<\<nil end  
[root]+left.zip(right).map{|set| set.flatten}  
end  
end

```
def [](idx)
    if idx < (leftheight = @left.height)
      @left[idx]
    elsif (idx== leftheight)
      @data
    elsif (idx-=(leftheight+1)) < @right.height
      @right[idx]
    end
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 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
end

def 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
end

def rebalance
  if (bf = balance_factor) > 1 # right is too high
    if @right.balance_factor < 0
      # double rotate right-left
      # - first the right subtree
      @right.rotate_right
    end
    rotate_left # single rotate left
  elsif bf < -1 # left must be too high
    if @left.balance_factor > 0
      # double rotate left-right
      # - first force left subtree
      @left.rotate_left
    end
    rotate_right # single rotate right
  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 = ExternalNode, &block)  
@root = root  
if block  
raise(ArgumentError,  
“Block argument for #{self.class.name} must” +  
" take 2 arguments and act as sort function"  
) unless block.arity == 2  
else  
block = proc{|a,b| a\<=\>b}  
end  
@compare = block  
end

def empty?  
@root == ExternalNode  
end

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

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

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

```

end

def remove(obj)  
@root.remove(obj).data  
end

def height  
@root.height  
end

def   
@root[idx]  
end

def to\_a( traversal=:inorder )  
@root.to\_a(traversal).flatten.compact  
end

def each(traversal=:inorder,&iter)  
if traversal==:by\_level  
@root.each\_level([],&iter)  
else  
@root.each(traversal,&iter)  
end  
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

def test\_non\_sequential\_insertion\_\_part\_2  
items = [3, 1, 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

def test\_alternate\_traversals  
items = [3,2,4,1,5]  
items.each {|el| @tree \<\< el}

```
preorder_result = [3,2,1,4,5]
assert_equal(preorder_result,@tree.to_a(:preorder))
@tree.each(:preorder) {|el| assert_equal(preorder_result.shift,el)}

inorder_result = [1,2,3,4,5]
assert_equal(inorder_result,@tree.to_a(:inorder))
@tree.each(:inorder) {|el| assert_equal(inorder_result.shift,el)}

postorder_result = [1,2,5,4,3]
assert_equal(postorder_result,@tree.to_a(:postorder))
@tree.each(:postorder) {|el|
assert_equal(postorder_result.shift,el)}

bylevel_result = [3,2,4,1,5]
assert_equal(bylevel_result,@tree.to_a(:by_level))
@tree.each(:by_level) {|el| assert_equal(bylevel_result.shift,el)}

```

end

def test\_tree\_find  
[1,2,3,4].each{|n| @tree\<\<n}  
assert\_equal(1, @tree.find{|v|v\>0} )  
assert\_equal(2, @tree.find{|v|v%2==0} )  
assert\_equal([2,4], @tree.find\_all{|v|v%2==0} )  
end

def test\_sequential\_access  
items = [50, 17, 72]  
items.each { |n| @tree \<\< n }  
items.sort.each\_with\_index do |e,i|  
assert\_equal(e, @tree[i],  
"@tree[#{i}] should be like " +  
“#{items.inspect}.sort[#{i}]”)  
end  
end

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

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

def test\_remove\_node  
@tree \<\< 314  
@tree.remove(314)  
assert\_equal(false, @tree.include?(314),  
‘314 still in the tree’)  
end

```
def test_remove_multiple_nodes
  #expanded to test rebalancing better
  items=[35, 79, 68, 49, 5, 50, 24, 71,
            66, 81, 41, 1, 37, 20, 95, 62]
  items.each { |n| @tree << n }
  items.size.times do
    togo = items.shift
    @tree.remove(togo)
    assert_equal(false, @tree.include?(togo),
              '#{togo} still in the tree')
    items.each{|i| assert_equal(true, @tree.include?(i),
              "tree should still include #{i}")
    }
  end
  assert_equal true, @tree.empty?
  @tree<<2
  assert_equal true, @tree.include?(2)
end

def test_tree_merge
  [1,2,3,4].each{|v| @tree << v}
  tree2 = AVLTree.new
  [2,4,6,8].each{|v| tree2<<v}
  mergedTree = @tree+tree2
  assert_equal([1,2,3,4,6,8], mergedTree.to_a)
  assert_equal([1,3], (mergedTree-tree2).to_a)
end

```

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

# Interface tests

def test\_custom\_comparison\_code  
rev\_tree = AVLTree.new { |a, b| b \<=\> a }  
values = [3, 2, 1]  
values.each { |v| rev\_tree \<\< v }  
rev\_tree.each { |v| assert\_equal(values.shift, v) }

```
len_tree = AVLTree.new { |a, b| a.length <=> b.length }
values = %w[3 22 111]
values.each { |v| len_tree << v }
len_tree.each { |v| assert_equal(values.shift, v) }

```

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](http://en.wikipedia.org/wiki/AVL_tree)  
=end  
**END**