理屈は知っていても、なかなか自分で実装することはないであろう2分探索木を実装する。
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
挿入
何はともあれ、2分探索木に値を挿入できるようにする。
上の実装ではinsertメソッドが該当する。
2分探索木の性質として、親の左側に親以下の値、親の右側に親以上の値を入れる必要がある。
なので、根から値を比較しながらまだ値の入っていない場所を探して格納すれば良い。
最小値
minメソッドでやっていること。
木の中で1番小さい値を探す。
これは、根から一番深い左の節を見れば良いだけ。
最大値
一番深い右の(ry
次節点
successorメソッドは、節を渡すと次節点を返してくれる。
次節点というのは例えば次のような木があるとする。
この時、
3の次節点は4
4の次節点は5
5の次節点は6
つまりその節の次に大きい値を探すということ。
2分探索木の性質から、ある節における次節点は、右の節がある場合には右の節のminであり、そうでない場合は親をたどればOK.
この実装だと次節点が無い場合は引数として渡した値がそのまま帰ってくる。
探索
searchメソッド。値を渡すと同じ値を持っている節を返す。
根から値を比較しながら同じ値を探せばいい。
節の削除
ちょっと複雑なのがコレ。
下記3つの場合分けがある。
- 節が右の子を持っていない
- 左の子を親と繋げる
- 節が左の子を持っていない
- 右の子を親と繋げる
- 節が右左両方の子を持っている
- 次節点が右の子でなければ、次節点の右の子を次節点の親と繋げる
- 次節点と節の親を繋げる
この「繋げる」の操作をしているのがtransplantメソッド。
ここでも場合分けがあり
- 元の節が根
- 右の子を持っていれば、右の子の親を付け替え
- さらに、左の子を持っていれば、左の子の親を付け替え
- 元の節が根ではない
- 元の節が親の左の節だったら左の節を付け替える
- 元の節が親の右の節だったら右の節を付け替える
これで削除が行える。。
削除が面倒なので実装に躊躇するわあ。