#/***********************************************************
#    tree.rb -- 2分探索木
#***********************************************************/

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

$nil_node = Tree.new("", nil, nil)
$root = $nil_node

def insert(key)  # 挿入 (登録) 
    $nil_node.key = key  # 番人 
    p = $root; link = "$root"
    while ( (cmp = (key <=> p.key)) != 0)
        if (cmp < 0); prev = p; link = "prev.left"; p = p.left
        else;         prev = p; link = "prev.right"; p = p.right
        end
    end
    if ( eval "#{link} != $nil_node")
         return nil     # すでに登録されている 
    end
    t = eval(link)
    q = Tree.new(key, $nil_node, t); eval "#{link} = q"
    return q;  # 登録した 
end

def delete(key)  # 削除できれば 0, 失敗なら 1 を返す 
    $nil_node.key = key  # 番人 
    p = $root; prev = $root; link = "$root"
    while ((cmp = (key <=> p.key)) != 0)
        if (cmp < 0); prev = p; link = "prev.left"; p = p.left
        else;         prev = p; link = "prev.right"; p = p.right; end
    end
    if (eval "#{link} == $nil_node"); return nil; end  # 見つからず 
    r = eval(link)
    if (r.right == $nil_node); eval "#{link} = r.left"
    elsif (r.left == $nil_node); eval "#{link} = r.right"
    else
       q = "r.left"
       while  (eval(q).right != $nil_node); q = q+".right"; end
       s = eval(q); eval(q + " = s.left")
       s.left = r.left; s.right = r.right
       eval(link + " = s")
    end
    return true;  # 削除成功 
end

def search(key)  # 検索 (未登録なら nil を返す) 
    $nil_node.key = key  # 番人 
    p = $root
    while ((cmp = (key <=> p.key)) != 0)
        if (cmp < 0); p = p.left
        else;         p = p.right; end
    end
    if (p != $nil_node); return p       # 見つかった 
    else;                return nil     # 見つからない 
    end
end

$depth = 0
def printtree(p)
    if (p.left != $nil_node) 
        $depth += 1;  printtree(p.left);  $depth -= 1
    end
    print('     ' * $depth + p.key + "\n")
    if (p.right != $nil_node) 
        $depth += 1;  printtree(p.right);  $depth -= 1
    end
end

printf("命令 Iabc:  abcを挿入\n"\
   "     Dabc:  abcを削除\n"\
   "     Sabc:  abcを検索\n")
while (true) 
    printf("命令? ")
    if ((buf = gets) == nil); break; end
    buf.chomp!
    key = buf[1..25]
    case (buf) 
    when /^[Ii]/
        if (insert(key) != nil); printf("登録しました.\n")
        else;                 printf("登録ずみです.\n")
        end
    when /^[Dd]/
        if (delete(key) == nil); printf("登録されていません.\n")
        else;                 printf("削除しました.\n")
        end
    when /^[Ss]/
        if (search(key) != nil); printf("登録されています.\n")
        else;                 printf("登録されていません\n")
        end
    else
        printf("使えるのは I, D, S です.\n")
    end
    if ($root != $nil_node) 
        printf("\n");  printtree($root);  printf("\n")
    end
end

exit 0