Tree 構造を利用した二分探索木(Ruby)

アルゴリズムを学ぼう

アルゴリズムを学ぼう



ここで実装した Tree 構造を使いました。

require './tree'

class BinaryTree < Tree
  def change(node, oldchild, newchild)
    replace(@root, newchild) unless node
    if left(node) == oldchild
      replace(left(node), newchild)
    elsif right(node) == oldchild
      replace(right(node), newchild)
    else
      raise "No child."
    end
  end
   
  def left(node)    #左の子供
    get_children(node)[0]
  end
   
  def right(node)    #右の子供
    get_children(node)[1]
  end
  
  def insert(node)
    raise "Already newchild exists." if @node.include?(node)
    @node << node
    nd = @root
    loop do
      if node < nd
        if left(nd)
	  nd = left(nd)
        else
	  @lh[nd].children[0] = node
	  @lh[node] = Branch.new(nd)
	  return
	end
      else
        if right(nd)
	  nd = right(nd)
	else
	  @lh[nd].children[1] = node
	  @lh[node] = Branch.new(nd)
	  return
	end
      end
    end
  end
  
  def search(start, goal)
    return false unless start
    return true  if start == goal
    return search(left(start)) if goal < start
    search(right(start))
  end
  
  def self.build(ar)
    ar1 = ar.dup
    t = BinaryTree.new(ar1.shift)
    ar1.each {|node| t.insert(node)}
    t
  end
end

if __FILE__ == $0
  ar = [3, 10, 1, 8, 5, 2, 6, 7, 4, 11, 9]
  p t = BinaryTree.build(ar)
end