binary_tree.rb

Heads up: This description was created by AI and might not be 100% accurate.

このRubyスクリプトは、二分探索木（Binary Search Tree）を操作するための機能を提供するものです。

プログラムの特徴:

二分探索木（BST）の表現: Node クラスを用いて二分探索木を表現します。ノードは、アイテム（値）と、左の子ノードと右の子ノードへの参照を持ちます。
ノード挿入: insert_node 関数は、二分探索木に新しいノードを挿入します。挿入時には、挿入する値が現在のノードの値より小さい場合は左の子ノードに挿入され、大きい場合は右の子ノードに挿入されます。値が等しい場合、挿入はスキップされます。
ノード削除: delete_node 関数は、二分探索木から指定された値を持つノードを削除します。ノードが根で、削除する値がその値と等しい場合は、単純に削除されます。ノードが葉の場合も同様に削除されます。もしノードが二つの子ノードを持つ場合、右子ノードの最小値を調べ、その最小値を持つノードを削除対象のノードの値と交換し、その後、右子ノードから最小値を持つノードを削除します。
ノード最小値検索: find_min 関数は、指定されたノードの左側の部分木の最小ノードを返します。
二分探索木の構築: make_binary_tree 関数は、配列から二分探索木を構築します。配列の要素を順番に insert_node 関数を用いて挿入することで、二分探索木を構築します。
インオーダー（Inorder）走査: print_with_inorder 関数は、二分探索木をインオーダーで走査し、ノードのアイテムを順に出力します。インオーダー走査は、左子ノードをまず走査し、次にルートノードを走査し、最後に右子ノードを走査する順序です。inorder_to_array関数は、インオーダー走査で得られたノードのアイテムを配列として返します。

アルゴリズム:

二分探索木（BST）の挿入:
- 与えられたノードがnilの場合、新しいノードを作成し、返します。
- 挿入する値が現在のノードのアイテムより小さい場合、左の子ノードを再帰的に挿入します。
- 挿入する値が現在のノードのアイテムより大きい場合、右の子ノードを再帰的に挿入します。
二分探索木（BST）の削除:
- 与えられたノードがnilの場合、nilを返します。
- 挿入する値が現在のノードのアイテムと等しい場合、現在のノードをnilで返します（ノードが削除されることを意味します）。
- ノードが葉ノードの場合、現在のノードをnilで返します。
- ノードが2つの子ノードを持つ場合、右子ノードの最小値を調べ、その最小値を持つノードを削除対象のノードの値と交換します。その後、右子ノードから最小値を持つノードを削除します。
ノード最小値検索:
- ノードの左子ノードがnilになるまで、左子ノードを辿ります。
- 最後にnilでなくなったノードが、その部分木の最小ノードです。
二分探索木の構築:
- 配列の各要素を順番にinsert_node関数を用いて二分探索木に挿入します。
インオーダー走査:
- 左の子ノードを再帰的に走査します。
- 現在のノードのアイテムを出力します。
- 右の子ノードを再帰的に走査します。
インオーダー走査による配列への変換:
- 左の子ノードを再帰的に走査し、その結果を配列に格納します。
- 現在のノードのアイテムを配列に追加します。
- 右の子ノードを再帰的に走査し、その結果を配列に格納します。
- 最終的に、配列を返します。

Ruby code snippet

# frozen_string_literal: true
#=> nil

class Node
  attr_accessor :item, :left, :right
  def initialize(item)
      @item = item
      @left = nil
      @right = nil
  end
end
#=> :initialize

def insert_node(node, ele)
  return Node.new(ele) if node.nil?

  if ele < node.item
      node.left = insert_node(node.left, ele)
    else
      node.right = insert_node(node.right, ele)
  end
  node
end
#=> :insert_node

def delete_node(node, val)
  return nil if node.nil?

  if val < node.item
      node.left = delete_node(node.left, val)
    elsif val > node.item
      node.right = delete_node(node.right, val)
    else
      return nil if node.left.nil? && node.right.nil?
  
      min_larger_right = find_min(node.right)
      node.item = min_larger_right.item
      node.right = delete_node(node.right, min_larger_right.item)
  end
  node
end
#=> :delete_node

def find_min(node)
  node = node.left while node.left
  node
end
#=> :find_min

def make_binary_tree(data)
  btree = nil
  data.each do |ele|
      btree = insert_node(btree, ele)
  end
  btree
end
#=> :make_binary_tree

def print_with_inorder(btree)
  return if btree.nil?

  print_with_inorder(btree.left)
  puts btree.item
  print_with_inorder(btree.right)
end
#=> :print_with_inorder

def inorder_to_array(btree)
  return [] if btree.nil?

  inorder_to_array(btree.left) + [btree.item] + inorder_to_array(btree.right)
end
#=> :inorder_to_array


data = 3.times.to_a.shuffle
#=> [1, 2, 0]

# make tree
#=> nil
btree = make_binary_tree(data)
#=> 
#<Node:0x00007f15c2d95218


# inorder
#=> nil
p inorder_to_array(btree)
[0, 1, 2]
#=> [0, 1, 2]

# insert
#=> nil
insert_node(btree, 123)
#=> 
#<Node:0x00007f15c2d95218
 @item=1,
 @left=#<Node:0x00007f15c2d950b0 @item=0, @left=nil, @right=nil>,
 @right=
  #<Node:0x00007f15c2d95128
   @item=2,
   @left=nil,
   @right=#<Node:0x00007f15c3234148 @item=123, @left=nil, @right=nil>>>
p inorder_to_array(btree)
[0, 1, 2, 123]
#=> [0, 1, 2, 123]

# delete
#=> nil
delete_node(btree, 0)
#=> 
#<Node:0x00007f15c2d95218
 @item=1,
 @left=nil,
 @right=
  #<Node:0x00007f15c2d95128
   @item=2,
   @left=nil,
   @right=#<Node:0x00007f15c3234148 @item=123, @left=nil, @right=nil>>>
p inorder_to_array(btree)
[1, 2, 123]
#=> [1, 2, 123]

Executed with Ruby 3.4.9.