2分探索木 配置＆探索ゲーム

2分探索木とは？

2分探索木は、コンピューターでデータを効率的に管理するための「データ構造」の一種です。名前の通り「木」のような形でデータを保持し、以下のシンプルなルールに従っています。

基本ルール

• 各ノード（円）は1つの値を持ちます。
• あるノードから見て、その左側の子や孫はすべて親ノードより小さい値を持ちます。
• あるノードから見て、その右側の子や孫はすべて親ノードより大きい値を持ちます。
• 左右それぞれの部分木も、同じルールに従った2分探索木になっています。
• （一般的に）同じ値を持つノードは存在しません。

このゲームでは、まずノードをルールに従って配置します。ゲームクリア後は、完成した木を使って値を探索する「探索モード」に切り替わります。

何が便利なの？

• 高速なデータ操作: このルールのおかげで、データの検索、追加、削除が非常に高速になります。毎回、値を比較して「左に行くか、右に行くか」を決めるだけで、探しているデータに素早くたどり着けます。データがN個ある場合、平均的にたったのlog N回の比較で済みます。
• データが常にソート済み: 木を特定の順序（通りがけ順: In-order traversal）でたどると、データを小さい順にきれいに取り出すことができます。

注意点

2分探索木は非常に強力ですが、弱点もあります。例えば、「10, 20, 30, 40, 50」のようにソートされたデータを順番に追加すると、木が左右にバランスよく広がらず、一本の棒のようになってしまいます。この状態では性能が著しく低下し、データの検索にN回の比較が必要になってしまいます。
この問題を解決するために、AVL木や赤黒木といった、自動でバランスを調整する改良版の木構造も存在します。