ツリー構造

• 2分木（binary tree）

2分木の操作を行う

基本的な考え方

　ツリーはリスト構造の延長線上として考えればいい。

　データの追加、削除、検索が効率よく行える。バイナリサーチであった「予めデータをソートしなければならない」「配列を使うので、データの頻繁な追加と削除を行うのに向かない」という欠点をクリアしている。

# Node Class
class Node
  attr_reader :value, :left, :right
  def initialize( val )
    @value = val   # このノードが保持する値
    @left = nil    # 左側のノード
    @right = nil   # 右側のノード
  end
  
  # ノードの値を設定
  def setValue( val )
    @value = val
  end

  # 左側のノードの設定
  def setLeft( node )
    @left = node
  end
  
  # 右側のノードの設定
  def setRight( node )
    @right = node
  end
end


# Tree Class
class TreeNode
  attr_reader :treeRoot
  
  def initialize()
    @treeRoot = nil    # ツリーのルート
  end
  
  # ----- ノードの追加
  def insertNode( num, node = nil )
    # 1つも挿入されていない場合
    if node == nil
      @treeRoot = createNewNode( num )
      return
    end
    
    # num が現在の node の値よりも小さい場合は左側に追加する
    if node.value > num
      if node.left != nil
        insertNode(num, node.left)
      else
        node.setLeft( createNewNode( num ) )
      end
    # num が現在の node の値以上の場合は右側に追加する
    else
      if node.right != nil
        insertNode(num, node.right)
      else
        node.setRight( createNewNode( num ) )
      end
    end
  end
  
  # ----- ノードの検索
  def findValue( val, node = nil )
    # 自node よりも小さい値なら左側を検索
    if node.value > val
      if node.left == nil
        return nil
      end
      return findValue( node.left, val )
    end
    # 自node よりも大きい値なら右側を検索
    if node.value < val
      if node.right == nil
        return nil
      end
      return findValue( node.right, val )
    end
    return node
  end
  
  # ----- ノードの削除
  def deleteNode( val )
    node = @treeRoot
    parentNode = nil
    direction = 0
    
    # 削除すべき対象を発見する
    while (node != nil && node.value != val)
      if node.value > val
        parentNode = node
        node = node.left
        direction = -1
      else
        parentNode = 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
          # 親のポインタを変更する
          parentNode.setLeft( node.right )
        elsif direction == 1
          parentNode.setRight( node.right )
        elsif direciton == 0
          @treeRoot = node.right
        end
      else
        if direction == -1
          # 親のポインタを変更する
          parentNode.setLeft( node.left )
        elsif direction == 1
          parentNode.setRight( node.left )
        elsif direction == 0
          @treeRoot = node.left
        end
      end
    else
      # node の左側の最も大きい値を取得する
      leftBiggest = node.left
      parentNode = node
      direction = -1
      while leftBiggest.right != nil
        parentNode = leftBiggest
        leftBiggest = leftBiggest.right
        direction = -1
      end
      
      # node の入れ替え
      node.setValue( leftBiggest.value )
      
      if direction == -1
        parentNode.setLeft( leftBiggest.left )
      else
        parentNode.setRight( leftBiggest.left )
      end
    end
    return true
  end
  
  def printNode( depth, node = nil )
    if node == nil
      return
    end
    printNode( depth + 1, node.left )
    i = 0
    while i < depth
      printf "   "
      i += 1
    end
    printf "#{node.value}¥n"
    printNode( depth + 1, node.right )
  end
  
  def main
    action = nil
    while action != 0
      printNode( 0, @treeRoot )
      puts "実行する操作のタイプを入力して下さい"
      puts "1:追加  2:検索  3:削除  0:終了 >"
      action = gets.chomp.to_i
      
      case action
        when 1
          puts "1〜100までの範囲で追加する数値を入力して下さい"
          i = gets.chomp.to_i
          if (i < 1 || i > 100)
            continue
          end
          insertNode( i, @treeRoot )
        when 2
          puts "検索する数字を入力して下さい"
          i = gets.chomp.to_i
          if findValue( i, @treeRoot ) != nil
            puts "#{i}を発見しました"
          else
            puts "#{i}は見つかりませんでした"
          end
        when 3
          puts "削除する数字を入力して下さい"
          i = gets.chomp.to_i
          if deleteNode(i)
            puts "#{i}を削除しました"
          else
            puts "#{i}は見つかりませんでした"
          end
      end
    end
  end
  
  private
  # ノードを生成する
  def createNewNode( val )
    newNode = Node.new( val )
    newNode.setLeft( nil )
    newNode.setRight( nil )
    return newNode
  end
end


# Main 
tree = TreeNode.new
tree.main

# Node Class
class Node
  attr_reader :value, :left, :right
  
  def initialize( val )
    @value = val    # このノードが保持する値
    @left = nil     # 左側のノード
    @right = nil    # 右側のノード
  end
  
  # ノードの値を設定
  def setValue( val )
    @value = val
  end

  # 左側のノードの設定
  def setLeft( node )
    @left = node
  end
  
  # 右側のノードの設定
  def setRight( node )
    @right = node
  end
end


# Tree Class
class TreeNode
  attr_reader :treeRoot
  
  def initialize()
    @treeRoot = nil    # ツリーのルート
  end
  
  # ----- ノードの追加
  def insertNode( val, node = @treeRoot )
    # 1つも挿入されていない場合
    if node == nil
      @treeRoot = createNewNode( num )
      return
    end
    
    # num が現在の node の値よりも小さい場合は左側に追加する
    if node.value > val
      if node.left != nil
        insertNode(val, node.left)
      else
        node.setLeft( createNewNode( val ) )
      end
    # num が現在の node の値以上の場合は右側に追加する
    else
      if node.right != nil
        insertNode(val, node.right)
      else
        node.setRight( createNewNode( val ) )
      end
    end
  end
  
  # ----- ノードの検索
  def findValue( val, node = @treeRoot )
    # 自node よりも小さい値なら左側を検索
    if node.value > val
      if node.left == nil
        return nil
      end
      return findValue( val, node.left )
    end
    # 自node よりも大きい値なら右側を検索
    if node.value < val
      if node.right == nil
        return nil
      end
      return findValue( val, node.right )
    end
    return node
  end
  
  # ----- ノードの削除
  def deleteNode( val )
    node = @treeRoot
    parentNode = nil
    direction = 0
    
    # 削除すべき対象を発見する
    while (node != nil && node.value != val)
      if node.value > val
        parentNode = node
        node = node.left
        direction = -1
      else
        parentNode = 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
          # 親のポインタを変更する
          parentNode.setLeft( node.right )
        elsif direction == 1
          parentNode.setRight( node.right )
        elsif direciton == 0
          @treeRoot = node.right
        end
      else
        if direction == -1
          # 親のポインタを変更する
          parentNode.setLeft( node.left )
        elsif direction == 1
          parentNode.setRight( node.left )
        elsif direction == 0
          @treeRoot = node.left
        end
      end
    else
      # node の左側の最も大きい値を取得する
      leftBiggest = node.left
      parentNode = node
      direction = -1
      while leftBiggest.right != nil
        parentNode = leftBiggest
        leftBiggest = leftBiggest.right
        direction = -1
      end
      
      # node の入れ替え
      node.setValue( leftBiggest.value )
      
      if direction == -1
        parentNode.setLeft( leftBiggest.left )
      else
        parentNode.setRight( leftBiggest.left )
      end
    end
    return true
  end
  
  def printNode( depth, node = @treeRoot )
    if node == nil
      return
    end
    printNode( depth + 1, node.left )
    i = 0
    while i < depth
      printf "   "
      i += 1
    end
    printf "#{node.value}¥n"
    printNode( depth + 1, node.right )
  end
  
  private
  # ノードを生成する
  def createNewNode( val )
    newNode = Node.new( val )
    newNode.setLeft( nil )
    newNode.setRight( nil )
    return newNode
  end
end


# Main 
tree = TreeNode.new
action = nil

while action != 0
  tree.printNode( 0 )
  
  puts "実行する操作のタイプを入力して下さい"
  puts "1:追加  2:検索  3:削除  0:終了 >"
  action = gets.chomp.to_i
  
  case action
    when 1
      puts "1〜100までの範囲で追加する数値を入力して下さい"
      i = gets.chomp.to_i
      if (i < 1 || i > 100)
        continue
      end
      tree.insertNode( i )
    when 2
      puts "検索する数字を入力して下さい"
      i = gets.chomp.to_i
      if tree.findValue( i ) != nil
        puts "#{i}を発見しました"
      else
        puts "#{i}は見つかりませんでした"
      end
    when 3
      puts "削除する数字を入力して下さい"
      i = gets.chomp.to_i
      if tree.deleteNode(i)
        puts "#{i}を削除しました"
      else
        puts "#{i}は見つかりませんでした"
      end
  end
end

# Node Class
class Node
  attr_reader :value, :key, :left, :right
  
  def initialize( num, val )
    @value = val    # このノードが保持する値
    @key = num      # このノードのキー
    @left = nil     # 左側のノード
    @right = nil    # 右側のノード
  end
  
  # ノードのキーを設定
  def setKey( num )
    @key = key
  end
  
  # ノードの値を設定
  def setValue( val )
    @value = val
  end

  # 左側のノードの設定
  def setLeft( node )
    @left = node
  end
  
  # 右側のノードの設定
  def setRight( node )
    @right = node
  end
end


# Tree Class
class TreeNode
  attr_reader :treeRoot
  
  def initialize()
    @treeRoot = nil    # ツリーのルート
  end
  
  # ----- ノードの追加
  def insertNode( key, val, node = @treeRoot )
    if node == nil
      @treeRoot = createNewNode( key, val )
      return
    end
    
    if node.key > key
      if node.left != nil
        insertNode( key, val, node.left )
      else
        node.setLeft( createNewNode( key, val ) )
      end
    else
      if node.right != nil
        insertNode( key, val, node.right )
      else
        node.setRight( createNewNode( key, val ) )
      end
    end
  end
  
  # ----- ノードの検索
  def findValue( key, node = @treeRoot )
    # 自node よりも小さい値なら左側を検索
    if node.key > key
      if node.left == nil
        return nil
      end
      return findValue( key, node.left )
    end
    # 自node よりも大きい値なら右側を検索
    if node.key < key
      if node.right == nil
        return nil
      end
      return findValue( key, node.right )
    end
    return node
  end
  
  # ----- ノードの削除
  def deleteNode( key )
    node = @treeRoot
    parentNode = nil
    direction = 0
    
    # 削除すべき対象を発見する
    while (node != nil && node.key != key)
      if node.key > key
        parentNode = node
        node = node.left
        direction = -1
      else
        parentNode = 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
          # 親のポインタを変更する
          parentNode.setLeft( node.right )
        elsif direction == 1
          parentNode.setRight( node.right )
        elsif direction == 0
          @treeRoot = node.right
        end
      else
        if direction == -1
          # 親のポインタを変更する
          parentNode.setLeft( node.left )
        elsif direction == 1
          parentNode.setRight( node.left )
        elsif direction == 0
          @treeRoot = node.left
        end
      end
    else
      # node の左側の最も大きい値を取得する
      leftBiggest = node.left
      parentNode = node
      direction = -1
      while leftBiggest.right != nil
        parentNode = leftBiggest
        leftBiggest = leftBiggest.right
        direction = -1
      end
      
      # node の入れ替え
      node.setValue( leftBiggest.value )
      
      if direction == -1
        parentNode.setLeft( leftBiggest.left )
      else
        parentNode.setRight( leftBiggest.left )
      end
    end
    return true
  end
  
  def printNode( depth, node = @treeRoot )
    if node == nil
      return
    end
    printNode( depth + 1, node.left )
    i = 0
    while i < depth
      printf "   "
      i += 1
    end
    printf "#{node.key} : #{node.value}¥n"
    printNode( depth + 1, node.right )
  end
  
  private
  # ノードを生成する
  def createNewNode( key, val )
    newNode = Node.new( key, val )
    newNode.setLeft( nil )
    newNode.setRight( nil )
    return newNode
  end
end


# Main 
tree = TreeNode.new
action = nil

while action != 0
  tree.printNode( 0 )
  
  puts "実行する操作のタイプを入力して下さい"
  puts "1:追加  2:検索  3:削除  0:終了 >"
  action = gets.chomp.to_i
  
  case action
    when 1
      puts "追加するキー（数値）を入力して下さい"
      key = gets.chomp.to_i
      puts "対応する文字列を入力してください"
      value = gets.chomp
      tree.insertNode( key, value )
    when 2
      puts "検索するキー（数字）を入力して下さい"
      i = gets.chomp.to_i
      found = tree.findValue( i )
      if found != nil
        puts "#{found.value}を発見しました"
      else
        puts "#{i}は見つかりませんでした"
      end
    when 3
      puts "削除するキー（数字）を入力して下さい"
      i = gets.chomp.to_i
      if tree.deleteNode(i)
        puts "#{i}を削除しました"
      else
        puts "#{i}は見つかりませんでした"
      end
  end
end