# Re: Programmer Ping-Pong (#150)

**URL:** <https://www.ruby-forum.com/t/re-programmer-ping-pong-150/229167>\
**Category:** Ruby\
**Created:** [December 19, 2007, 3:35am UTC](https://www.ruby-forum.com/t/re-programmer-ping-pong-150/229167 "2007-12-19T03:35:11Z")\
**Posts on this page:** 1\
**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, 3:35am UTC](https://www.ruby-forum.com/t/re-programmer-ping-pong-150/229167/1 "2007-12-19T03:35:11Z")

</div>

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)