探索アルゴリズム「二分探索木 シミュレーション編」公開
2019/03/30
こんばんは。えいたです。
情報系の大学に進学 → 教育系のゼミに配属 → 教育に関する研究
僕はゼミ室のテーマに沿って、卒業研究は二分探索木の教材を制作しました。
使用言語：シミュレーションはJava、アニメーション教材はFlash
まさかのFlash使用禁止令、アニメーション教材は冬休みに制作しました。
もしも、シミュレーションをFlashで制作した場合が気になる・・・。
「１０年越しのリベンジ、教授に届け！」
二分探索木とは
IT技術者の基本、基本情報技術者試験に出題あり。
コンピュータプログラムにおいて、「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」という制約を持つ二分木である。探索木のうちで最も基本的な木構造である。
平衡状態では木の高さはO(log2N)となる。ただし最悪の場合は、事実上の線形リストになり、木の高さはO(N)となる。
- ８５を検索：５０ → ７５ → ９０ → ８５(成功)
- ４７を検索：５０ → ２５ → ４０ → ４５(失敗)
線形リストより探索回数が減少、二分探索木のメリットです。
「二分探索木 シミュレーション編」で学ぶ
「二分探索木 シミュレーション編」について
ルール
各操作(検索・挿入・削除)について、シミュレーションをします。
検索
２５を検索：５０ → ２５(成功)
挿入
５５を挿入：５０ → ７５ → 左側に挿入(成功)
削除
７５を削除：５０ → ７５ → ノードを削除(成功)
画面構成
初期状態において、初期化ボタンで二分探索木を選択できます。
７種類から選択、「１」は探索木無し状態(不具合ではありません)
入力数値は２桁(１～９９)、手動／自動は選択可能！
- 手動：ユーザが次ステップの実行権を持つ
- 自動：自動的に次ステップに進む
最後に各操作を選択、各ステップをアニメーションで表現しました。
操作方法
二分探索木を選択 → 数値を入力 → 手動／自動を選択 → 操作を実行
二分探索木の決定は「初期化ボタン」で確定します。
入力数値はキーボード入力、空白の場合はランダムです。
手動はステップ毎に「手動ボタン」を押して下さい。
削除処理は複雑
子が存在するノードを削除する場合、置き換える必要あり！
子が２つの場合について、削除アルゴリズムを説明します。
子が１つ：削除対象と子を置き換えるだけ。
７５を削除
７５を探索成功 → ノードを削除
７５未満の最も大きい数値を探索
左側ノードを探索 → 右側ノードが存在するまで探索 → ６５を探索成功
６５に置き換える
７５を６５に置き換える → 二分探索木が成立
さいごに
卒業研究からの改善点は、各操作の処理をアニメーション表示！
静止画の弱点、アニメーションが伝わらない。
「YouTubeで実演する！」
ユーザからの需要次第ですが、取扱説明書の動画は検討に値する？
二分探索木はシミュレーション編で学習、ゲーム編で理解を深めて下さい。
他のゲームも遊んで下さいね。