0

基本的な二分探索木の次の Ruby 実装を作成しました。

rt = Node.new(data)基になるオブジェクトを実際に変更しているのではなく、実際には破棄される一時変数にすぎないと思います。

#!/usr/bin/env ruby

class Node
  attr_accessor :left, :right, :data
  def initialize(d)
    @left = nil
    @right = nil
    @data = d
  end
end

class BST
  attr_accessor :root
  def initialize
    @root = nil
  end

  def add_helper(rt, d)
    if rt != nil
      add_helper(rt.left, d) if d < rt.data
      add_helper(rt.right, d) if d > rt.data
    end
    rt = Node.new(d)
  end

  def add(data)
    add_helper(root, data)
  end

  def print_helper(rt)
    return if rt == nil
    pr(rt.left) if rt.left != nil
    puts rt.data
    pr(rt.right) if rt.right != nil
  end

  def print_tree
    print_helper(root)
  end
end

###########################
b = BST.new
b.add(5)
b.add(-10)
b.print_tree

実装の何が問題になっていますか? 私はデバッグする必要があることを知っており、実際にデバッグしています。私は print ステートメントを入れましたが、最終的に Node オブジェクト自体でさえ、すべてがまだ nil であることに気付きました。

4

1 に答える 1

1

あなたの本能は正しいです。rt = Node.new(d)新しいNodeオブジェクトを作成していますが、すぐに破棄されています。

これを解決する 1 つの方法は、別の再帰呼び出しを行う前に、親呼び出しで代入を実行することです。

def add_helper rt, d
  if rt != nil
    case
    when d < rt.data
      # If rt doesn't have a left child yet, assign it here. Otherwise,
      # recursively descend to the left.
      if rt.left.nil?
        rt.left = Node.new(d)
      else
        add_helper(rt.left, d)
      end
    when d > rt.data
      # Likewise for the right child.
      if rt.right.nil?
        rt.right = Node.new(d)
      else
        add_helper(rt.right, d)
      end
    else
      # Handle duplicate additions however you'd like here.
      raise "Attempt to add duplicate data #{d}!"
    end
  else
    # Now, this can only happen when the root of the entire tree is missing!
    @root = Node.new(d)
  end
end

もう少し優雅な別のアプローチはadd_helper、ノードが欠落している場合にノードを追加する方法を知っているブロックを渡すことです。

def add_helper rt, d
  if rt.nil?
    # This node isn't assigned yet, so tell our caller to add it.
    yield Node.new(d)
  else
    # Otherwise, perform the appropriate recursive call, passing a block that
    # adds the new node to the correct side of the parent.
    case
    when d < rt.data ; add_helper(rt.left, d) { |n| rt.left = n }
    when d > rt.data ; add_helper(rt.right, d) { |n| rt.right = n }
    else ; raise "Duplicate insertion!"
    end
  end
end

def add data
  # Call add_helper with a block that knows how to assign the root of the whole
  # tree if it's not there:
  add_helper(root, data) { |n| @root = n }
end
于 2013-10-28T19:11:53.773 に答える