Re: 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 :slight_smile:

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.

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs