ディジタル探索

digi.rb

# アルゴリズム辞典
# 島内剛一 野下浩平 伏見正則 有沢誠 浜田穂積
#
# ディジタル探索 pp. 522-523

require 'pp'

class Node
  attr_accessor :key, :left, :right
  
  def initialize(key, left, right)
    @key = key
    @left = left
    @right = right
  end
end

class DigitalSearch
  def initialize()
    @head = Node.new(0, nil, nil)
    @mask = [0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80]
  end
  
  # 探索
  def search(key)
    idx = 0
    np = @head.left
    
    while np != nil && key != np.key
      # キーの idx 桁が 1(0) ならば右(左)へ
      idx += 1
      np = (key[0] & @mask[idx] != 0) ? np.right : np.left
    end
    
    return np
  
  end

  # 挿入
  def insert(key)
    father = @head
    idx = 0

    # ステップ1 キーの探索
    np = father.left
    while np != nil && key != np.key
      father = np
      idx += 1
      np = (key[0] & @mask[idx] != 0) ? np.right : np.left
    end

    # ステップ2 キー挿入
    if np != nil
      puts "#{key} はすでにある"
    else
      # 新しい節を作り
      np = Node.new(key, nil, nil)
      # キーを置き親とつなぐ
      if key[0] & @mask[idx] != 0
        father.right = np
      else
        father.left = np
      end
    end

  end

  # 削除
  def delete(key)

    # ステップ1 キーの探索
    idx = 0
    np = @head.left
    while np != nil && key != np.key
      father = np
      idx += 1
      np = (key[0] & @mask[idx] != 0) ? np.right : np.left
    end


    # ステップ2 キー削除
    if np == nil
      puts "#{key} はない"
      return
    end
    
    # np の子孫中の葉を探す
    x = np
    while x.left != nil || x.right != nil
      father = x
      idx += 1
      x = x.left == nil ? x.right : x.left
    end
    
    # 葉のキーを np に置き、葉を切り離す
    np.key = x.key
    if x.key[0] & @mask[idx] != 0
      father.right = nil
    else
      father.left = nil
    end
  end
end


def main()
  digi = DigitalSearch.new()
  digi.insert('a')
  digi.insert('b')
  digi.insert('c')
  digi.insert('d')
  
  np = digi.search('a')
  if np != nil
    puts "key hit: #{np.key}"
  end

  np = digi.search('a')
  if np != nil
    puts "key hit: #{np.key}"
  end

  np = digi.search('b')
  if np != nil
    puts "key hit: #{np.key}"
  end

  np = digi.search('c')
  if np != nil
    puts "key hit: #{np.key}"
  end

  np = digi.search('d')
  if np != nil
    puts "key hit: #{np.key}"
  end

  digi.delete('b')
  puts "delete key: b"
  
  np = digi.search('a')
  if np != nil
    puts "key hit: #{np.key}"
  end

  np = digi.search('b')
  if np != nil
    puts "key hit: #{np.key}"
  end

  digi.delete('a');
  puts "delete key: a"

  np = digi.search('a')
  if np != nil
    puts "key hit: #{np.key}"
  end

end


main()