150118

Ruby


「アルゴリズムとデータ構造」のRuby版。

２分木を使ったマップ

# -*- coding: cp932 -*-

# Node Class

class Node

  attr_accessor :key, :value, :left, :right

  def initialize(num, val)

    @key = num      # ノードのキー

    @value = val    # ノードが保持する値

    @left = nil     # 左側のノード

    @right = nil    # 右側のノード

  end

end

# ノードを生成する

def create_new_node(num, val)

  newNode = Node.new(num, val)

  return newNode

end

# ノードの追加

def insert_tree(num, val, node)

  # 1つも挿入されていない場合

  if node == nil

    @tree_root = create_new_node(num, val)

    return

  end

  if node.key > num

    if node.left != nil

      insert_tree(num, val, node.left)

    else

      node.left = create_new_node(num, val)

    end

  else

    if node.right != nil

      insert_tree(num, val, node.right)

    else

      node.right = create_new_node(num, val)

    end

  end

end

# ノードの検索

def find_value(node, num)

  if node.key > num

    if node.left == nil

      return nil

    end

    return find_value(node.left, num)

  end

  if node.key < num

    if node.right == nil

      return nil

    end

    return find_value(node.right, num)

  end

  return node

end

# ノードの削除

def delete_tree(num)

  node = @tree_root

  parent_node = nil

  direction = 0

  # while文で削除すべき対象を見つける

  while (node != nil && node.key != num)

    if node.key > num

      parent_node = node

      node = node.left

      direction = -1

    else

      parent_node = node

      node = node.right

      direction = 1

    end

  end

  if node == nil

    return false

  end

  if node.left == nil || node.right == nil

    if node.left == nil

      if direction == -1

        parent_node.left = node.right

      elsif direction == 1

        parent_node.right = node.right

      elsif direction == 0

        @tree_root = node.right

      end

   else

      if direction == -1

        parent_node.left = node.left

      elsif direction == 1

        parent_node.right = node.left

      elsif direction == 0

        @tree_root = node.left

      end

    end

  else

    left_biggest = node.left

    parent_node = node

    direction = -1

    while left_biggest.right != nil

      parent_node = left_biggest

      left_biggest = left_biggest.right

      direction = 1

    end

    node.key = left_biggest.key

    node.value = left_biggest.value

    if direction == -1

      parent_node.left = left_biggest.left

    else

      parent_node.right = left_biggest.left

    end

  end

  return true

end

def print_tree(depth, node = nil)

  if node == nil

    return

  end

  print_tree(depth + 1, node.left)

  i = 0

  while i < depth

    printf ""

    i += 1

  end

  printf("%s ：%s \n", node.key, node.value)

  print_tree(depth + 1, node.right)

end

def main

  action = nil

  while action != 0

    print_tree(0, @tree_root)

    printf("0:終了1:挿入2:探索3:削除>")

    action = gets.chomp.to_i

    case action

      when 1

        printf("挿入する文字列（キー）:>")

        key = gets.chomp.to_i

        printf("キーに対応させる値:>")

        value = gets.chomp

        insert_tree(key, value, @tree_root)

      when 2

        printf("探索する文字列:>")

        i = gets.chomp.to_i

        node_found = find_value(@tree_root, i)

        if node_found != nil

          printf("対応する値は%sです\n", node_found.value)

        else

          printf("見つかりませんでした\n")

        end

      when 3

        printf("削除する文字列:>")

        i = gets.chomp.to_i

        if delete_tree(i)

          printf("削除しました\n")

        else

          printf("見つかりませんでした\n")

        end

    end

  end

end

main