On Dec 17, 2007 7:29 PM, Rob Biedenharn <Rob / agileconsultingllc.com> wrote:
>
> An easy lob, Enumerable is a simple volley since AVLTree#each already
> exists.
>
> Adam opened my eyes to the symmetry that I was missing in the first
> part of the double rotations.  I extracted the rotate_left and
> rotate_right into their own methods and removed the now unnecessary
> argument to rebalance.
>
> My new test is for sequential access -- something that an AVLTree
> should be able to do in O(log N) time.  I'd love for someone to show
> how to write a good test forcing the access to be better than O(N) for
> a suitably large N.
>
> -Rob

I don't know how to test timing with the unit tests either.
I'm sending a response that passes the tests, but probably won't meet
the timing requirement until each node tracks its own height instead
of recalculates it on demand.
And I'm cheating on the return - Instead of writing a new test, I'm
re-enabling the test_remove_node.
If It weren't midnight I'd do a better job...

-Adam

==> 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 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 [](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
   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 [](idx)
   #     to_a[idx]
   #   end

   def [](idx)
     @root[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__

==> extract.rb <==
# -*- 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__

==> package.rb <==
#!/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__

==> 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_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


   ##################################################
   # Things that aren't tested anymore...


   # 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, http://en.wikipedia.org/wiki/AVL_tree
=end
__END__