From: Justin Ethier <justin.ethier@...>
Date: 2007-12-16T05:05:13+09:00
Subject: Re: [QUIZ] Programmer Ping-Pong (#150)

------=_Part_3377_881405.1197749117421
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

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

------=_Part_3377_881405.1197749117421--