Rubyでアルゴリズムやらデータ構造やらのお勉強（Binary Tree）

binary_tree.rb

# -*- coding: utf-8 -*-

# Cで書かれたアルゴリズムやらデータ構造なりを、自分なりにRubyで表現してみるお勉強PJ。
# 参考書籍（プログラミングの宝箱 アルゴリズムとデータ構造）
# Ruby1.9.3で動作確認済み

# 説明書きだけみてコーディングにトライしているので、意図を汲み取れているか微妙
# 多分木化時に再調整するなりしてまとめ直したい

$VERBOSE = true

class BinaryTree

  class Node
    include Comparable
    
    attr_reader :value, :parent
    
    def initialize(value, parent=nil)
      raise TypeError unless value.respond_to? :<=>
      
      @value, @parent = value, parent
      @less, @greater = nil, nil
    end
    
    def <=>(other)
      @value <=> other.value
    end
    
    def insert(value)
      case @value <=> value
      when 0
        raise 'Dupulicated the value'
      when ->n{n < 0}
        if @greater
          @greater.__send__ __callee__, value
        else
          @greater = self.class.new value, self
        end
      when Integer
        if @less
          @less.__send__ __callee__, value
        else
          @less = self.class.new value, self
        end

      else
        raise TypeError
      end
    end
    
    def find(value)
      case @value <=> value
      when 0
        self
      when ->n{n < 0}
        if @greater
          @greater.find value
        else
          nil
        end
      when Integer
        if @less
          @less.find value
        else
          nil
        end
      else
        raise TypeError
      end
    end
    
    alias_method :detect, :find
    
    def delete(value)
      if @value == value
        if leaf?
          parent.delete_node self
        else
          case
          when @less && @greater
            max = children.max
            @value = max.value
            max.parent.delete_node max
          when @less
            parent.replace_node self, @less
          when @greater
            parent.replace_node self, @greater
          else
            raise 'must not happen'
          end
        end
      else
        children.each{|node|node.delete value}
      end
    end
    
    def root?
      @parent.nil?
    end
    
    def child?
      ! root?
    end
    
    def branch
      children.empty? ? [self] : [self, *children]
    end
    
    def children
      [].tap {|ret|
        (ret << @less.branch)    if @less
        (ret << @greater.branch) if @greater
        ret.flatten!
      }
    end
      
    def node?
      !!(@less || @greater)
    end
    
    alias_method :parent?, :node?
    
    def leaf?
      ! node?
    end
    
    protected
    
    def delete_node(node)
      replace_node node, nil
    end

    def replace_node(older, newer)
      (@less = newer)    if @less.equal? older
      (@greater = newer) if @greater.equal? older
    end

  end
  
  def initialize
    @root = nil
  end
  
  def length
    @root ? @root.branch.length : 0
  end
  
  alias_method :size, :length
    
  def push(value)
    if @root
      @root.insert value
    else
      @root = Node.new value
    end
    
    self
  end
  
  alias_method :<<, :push
  
  def find(value)
    @root && @root.find(value)
  end
 
  alias_method :detect, :find
  
  def delete(value)
    @root && @root.delete(value)
  end

end


# Overview

require 'pp'
tree = BinaryTree.new
pp tree
pp tree.size

tree << 8
#~ pp tree
pp tree.size

tree << 80
tree << 1
#~ pp tree
pp tree.size

tree << 20
#~ pp tree
pp tree.size

pp tree.find 30
pp tree.find 20
pp tree.find 80

tree.delete 30
#~ pp tree
pp tree.size

tree.delete 80
#~ pp tree
pp tree.size