【Ruby】【アルゴリズム】二分木の実装 追加／削除／検索

二分木とは

二分木は「木構造 (tree structer) 」または「木 (tree) 」と呼ばれるデータ構造の一つです。

http://www.geocities.jp/m_hiroi/light/abcruby13.html

学んだこと

再帰コードを書くときに、状態が変わるものをレシーバーにするのは良くない。

例えば今回の二分木実装では、
最初、Treeクラスを作らずにやって手詰まった。

具体的には、最初はこういうコードを書いていた↓

root = Node.new(nil,nil,10)
root.kesu(10)

この方法だと、
レシーバをnilにする必要があるけれども、
kesuメソッドの中ではrootオブジェクトがselfとして参照され、
selfへの代入は出来ないから、だめ。

 Can't change the value of self

　
とりあえず、再帰を書くときはレシーバを意識する。

あと、Rubyの「最後に評価した式が返り値となる仕様」に時たま嵌ってしまう。

例えばこのコード↓、最後のnodeを忘れると再帰がずれてしまう。

  def _delete_max(node)
    return node = node.left if node.right.nil?
    node.right = _delete_max(node.right)
    node
  end

作成したコード

class Node
  attr_accessor :left, :right, :val
  def initialize (left, right, val)
    @left = left
    @right = right
    @val = val
  end
end

class BinaryTree
  attr_accessor :root
  def initialize ()
    @root = nil
  end
  def add(int)
    obj = Node.new(nil,nil,int)
    @root = _add(@root, obj)
    self
  end
  def _add(root, obj)
    return root = obj if root.nil?
    if obj.val < root.val
      if !root.left
        root.left = obj
      else
        _add(root.left, obj)
      end
    else
      if !root.right
        root.right = obj
      else
        _add(root.right, obj)
      end
    end
    root
  end
  def _exist(root, int)
    return root if int == root.val
    if int < root.val
      return nil if root.left.nil?
      _exist(root.left, int)
    else
      return nil if root.right.nil?
      _exist(root.right, int)
    end
  end
  def exist(int)
    _exist(@root, int)
  end
  def kesu(int)
    return nil if !exist(int)
    _kesu(@root, int)
  end
  def _kesu(node, int)
    if int == node.val
      return node.right if node.left.nil?
      return node.left if node.right.nil?

      node.val = _biggest(node.left).val
      node.left = _delete_max(node.left)
      p node.left
    elsif int < node.val
      node.left = _kesu(node.left, int)
    else
      node.right = _kesu(node.right, int)
    end
    node
  end
  def _biggest(node)
    return node if node.right.nil?
    _biggest(node.right)
  end
  def _delete_max(node)
    return node = node.left if node.right.nil?
    node.right = _delete_max(node.right)
    node
  end
end

root = BinaryTree.new()
root.add(50)
root.add(10)
root.add(20)
root.add(8)
root.add(60)
p root.kesu(50)

　
■実行結果

#<Node:0x2c21280 @left=#<Node:0x2c21268 @left=#<Node:0x2c21238 @left=nil, @right
=nil, @val=8>, @right=nil, @val=10>, @right=#<Node:0x2c21220 @left=nil, @right=n
il, @val=60>, @val=20>