🎯 はじめに
みなさんこんにちは！
今回は、二分探索木などのツリーデータ構造を学習するための可視化アプリケーションをReact + TypeScriptで作成しました。アルゴリズムの動作を一歩ずつ追いながら、視覚的に理解できるツールです。
この記事では、ツリーデータ構造の可視化アプリケーションの設計と実装について解説します。
🎮 デモプレイ
💻 ソースコード
🌲 ツリーデータ構造とは
ツリーデータ構造は、データ要素を階層的に整理するための非線形なデータ構造です。要素はノードとして表され、ノード間はエッジで結ばれます。この構造は、ルートノードと呼ばれる最上位のノードを頂点として始まり、各ノードは子ノードを持つことができますが、親ノードはただ一つです。この階層的な関係により、ファイルシステム、組織図、WebページのDOM構造など、親子の関係や階層的な分類を持つ情報を効率的に表現・処理するのに非常に適しています。
本アプリで扱う4つのデータ構造
1. 二分探索木（Binary Search Tree - BST）
最も基本的なツリー構造です。各ノードについて、左の子は親より小さく、右の子は親より大きいという性質を持ちます。
2. AVL木
自己平衡二分探索木の一種で、常にツリーの高さバランスを保ちます。各ノードについて、左右の部分木の高さの差が1以内になるよう、回転操作によって調整します。
3. 赤黒木
各ノードに色（赤または黒）を持たせ、色に関する規則を守ることでバランスを保つ平衡木です。AVL木よりも挿入・削除時の回転回数が少なく、実用的な実装が多いのが特徴です。
4. ヒープ（Min-Heap / Max-Heap）
完全二分木の構造を持ち、優先度付きキューの実装に使われます。Min-Heapでは親が子より小さく、Max-Heapでは親が子より大きいという性質を持ちます。
アルゴリズムの比較
各アルゴリズムの計算量を比較すると以下のようになります。
| アルゴリズム | 挿入 | 削除 | 探索 | 特徴 |
|---|---|---|---|---|
| 二分探索木（BST） | O(h) | O(h) | O(h) | シンプルだが、最悪ケースでO(n)になる可能性がある |
| AVL木 | O(log n) | O(log n) | O(log n) | 厳密にバランスを保つため、探索が高速 |
| 赤黒木 | O(log n) | O(log n) | O(log n) | AVL木より挿入・削除が高速 |
| Min/Max-Heap | O(log n) | O(log n) | O(n) | 最小値/最大値の取得がO(1) |
※ hはツリーの高さ、nはノード数
BSTは最もシンプルですが、データの挿入順序によってはツリーが一方向に偏り、計算量が線形になってしまう問題があります。平衡木（AVL木、赤黒木）は回転操作によってバランスを保つため、常に対数時間の性能を保証します。
🖥️ アプリケーションの画面構成と操作方法
アプリケーションは3つの主要なエリアで構成されています。
画面構成
- 左サイドバー（コントロールパネル）: アルゴリズムの選択や操作を行う
- 中央エリア（可視化キャンバス）: ツリー構造をグラフィカルに表示
- 右サイドバー（統計パネル）: 実行状況と計算量を表示
操作手順
1. 初期設定
アプリケーション起動時、以下の設定が可能です。
- アルゴリズム選択: ドロップダウンから使用するアルゴリズムを選択します（現在はBSTのみ対応）
- ノード数設定: スライダーで初期ツリーのノード数を1〜20の範囲で設定します
設定後、ランダムな値で初期ツリーが自動的に生成され、挿入過程がアニメーション表示されます。
2. 挿入操作
任意の値をツリーに追加できます。
- 入力フィールドに挿入したい数値を入力します
- 「挿入」ボタンをクリックします
- アニメーションが開始され、探索から挿入までの過程が可視化されます
ノードの色が以下のように変化します。
- 黄色: 現在探索中のノード
- 水色: 挿入候補の位置
- 緑色: 挿入が確定したノード
3. 削除操作
ツリーから特定の値を削除できます。
- 入力フィールドに削除したい数値を入力します
- 「削除」ボタンをクリックします
- アニメーションが開始され、削除対象の探索と削除処理が可視化されます
削除には3つのケースがあります。
- 葉ノードの削除: 単純にノードを除去します
- 子が1つのノードの削除: 子ノードを親に繋ぎ替えます
- 子が2つのノードの削除: 右部分木の最小値（後継ノード）で置き換えます
4. 速度調整
スライダーでアニメーションの再生速度を調整できます。ゆっくり動かすことで、各ステップの詳細を確認できます。
5. リセット
「リセット」ボタンをクリックすると、現在の設定（アルゴリズム、ノード数）で新しいツリーが再生成されます。
🛠️ 実装の工夫点
不変性を保つツリー操作
Reactの再レンダリングを正しく動作させるため、ツリーノードの変更時には必ず新しいオブジェクトを生成しています。元のツリーをディープコピーしてから操作を行い、各ステップで完全に独立したツリー状態を持つことで、意図しない副作用を防いでいます。
状態の色分け表現
ノードの状態を視覚的に区別するため、状態ごとに異なる色を適用しています。さらに、探索中や比較中のノードには太いボーダーを適用し、色だけでなく形状でも状態を判別できるようにしました。これにより、アクセシビリティが向上し、色覚多様性のあるユーザーにも配慮した設計となっています。
階層的レイアウトの自動計算
ツリーの可視化には、vis-networkライブラリを活用しました。階層的レイアウトを自動計算し、ノードの重なりや見づらさを防ぎます。レベル情報を付与することで、同じ深さのノードが横一列に並ぶよう制御しています。
📚 可視化による学習効果
直感的な理解の促進
アニメーションによって、アルゴリズムの動作が時系列で理解できます。教科書の静的な図では分かりにくかった処理の順序や、なぜその操作が必要なのかが、視覚的に腑に落ちるようになります。
📝 まとめ
ツリーデータ構造の可視化アプリケーションを通じて、アルゴリズムの動作を直感的に理解できるツールを実現しました。