rubyの２分探索木実装

理屈は知っていても、なかなか自分で実装することはないであろう２分探索木を実装する。

class BinaryTree
  attr_accessor :root

  def initialize
    self.root  = nil
  end

  class Node
    attr_accessor :parent, :left, :right, :value

    def initialize(value)
      self.value  = value
      self.parent = nil
      self.left   = nil
      self.right  = nil
    end
  end

  def insert(value)
    node = Node.new(value)

    parent = root
    point = nil
    while parent != nil
      point = parent
      parent = if point.value > node.value
        point.left
      else
        point.right
      end
    end

    if point != nil
      node.parent = point
      if point.value > node.value
        point.left = node
      else
        point.right = node
      end
    else
      self.root = node
    end
  end

  def min(node = root)
    node = node.left while node != nil && node.left != nil

    return node
  end

  def max(node = root)
    node = node.right while node != nil && node.right != nil

    return node
  end

  def successor(node)
    return min(node.right) if node.right != nil

    parent = node.parent
    while parent != nil && parent.right.value == node.value
      node   = parent
      parent = parent.parent
    end

    parent
  end

  def search(value)
    node = root
    while node != nil && node.value != value
      node = if node.value > value
        node.left
      else
        node.right
      end
    end

    node
  end

  def transplant(out_node, node)
    if out_node == root
      out_node.right.parent = node if out_node.right != nil
      out_node.left.parent = node if out_node.left != nil
    else
      if out_node.parent.left == out_node
        out_node.parent.left = node
      else
        out_node.parent.right = node
      end
    end

    node.parent = out_node.parent if node != nil
  end

  def delete(node)
    if node.left == nil
      transplant(node, node.right)

      self.root = node.right if node.parent == nil
    elsif node.right == nil
      transplant(node, node.left)

      self.root = node.left if node.parent == nil
    else
      suc = successor(node)

      if suc.parent != node
        transplant(suc, suc.right)
        suc.right = node.right
        suc.right.parent = suc
      end

      transplant(node, suc)
      suc.left = node.left
      suc.left.parent = suc

      self.root = suc if node.parent == nil
    end
  end
end

挿入

何はともあれ、２分探索木に値を挿入できるようにする。
上の実装ではinsertメソッドが該当する。

２分探索木の性質として、親の左側に親以下の値、親の右側に親以上の値を入れる必要がある。
なので、根から値を比較しながらまだ値の入っていない場所を探して格納すれば良い。

最小値

minメソッドでやっていること。
木の中で１番小さい値を探す。
これは、根から一番深い左の節を見れば良いだけ。

最大値

一番深い右の（ry

次節点

successorメソッドは、節を渡すと次節点を返してくれる。
次節点というのは例えば次のような木があるとする。

この時、
3の次節点は4
4の次節点は5
5の次節点は6

つまりその節の次に大きい値を探すということ。
２分探索木の性質から、ある節における次節点は、右の節がある場合には右の節のminであり、そうでない場合は親をたどればOK.
この実装だと次節点が無い場合は引数として渡した値がそのまま帰ってくる。

探索

searchメソッド。値を渡すと同じ値を持っている節を返す。
根から値を比較しながら同じ値を探せばいい。

節の削除

ちょっと複雑なのがコレ。
下記３つの場合分けがある。

1. 節が右の子を持っていない
• 左の子を親と繋げる
2. 節が左の子を持っていない
• 右の子を親と繋げる
3. 節が右左両方の子を持っている
• 次節点が右の子でなければ、次節点の右の子を次節点の親と繋げる
• 次節点と節の親を繋げる

この「繋げる」の操作をしているのがtransplantメソッド。
ここでも場合分けがあり

1. 元の節が根
• 右の子を持っていれば、右の子の親を付け替え
• さらに、左の子を持っていれば、左の子の親を付け替え
2. 元の節が根ではない
• 元の節が親の左の節だったら左の節を付け替える
• 元の節が親の右の節だったら右の節を付け替える

これで削除が行える。。
削除が面倒なので実装に躊躇するわあ。