| 操作 | 平均 | 最悪 |
|---|
* ならし:長い一連の操作で平均したもの
データ構造ビジュアライザー
データ構造とは、よく尋ねる質問にすばやく答えられるようにデータをしまう方法です。スタックから赤黒木まで、11種類の古典的な構造から1つを選び、値を入力して操作を押してください。どのノードが比較され、どのリンクが変わり、なぜ木が回転し値が浮かび上がるのかが、何が起きているかを述べる一文とともに画面上で1ステップずつ再生されます。タイルは各操作の仕事量を数え、表はその実行時間を示します。 構造を選び、値を入力して操作を押してください。どの操作も1ステップずつ再生されます。強調表示されたノードは、何が比較され、移動し、変わるのかを示し、図の下の行は何が起きているのか、なぜなのかを説明します。「戻る」「ステップ」「再生」「最後」でステップをもう一度たどれます。「ランダムに埋める」と「クリア」で最初からやり直し、「元に戻す」で操作を取り消せます。タイルにはサイズ、木の高さ、直前の操作の仕事量(比較、探査、たどった親リンクの数)、その構造にとって大事な数値が表示され、表には各操作の実行時間が載っています。
使い方
- 二分探索木、ハッシュテーブル、トライなどの構造を選びます。最初はランダムな内容が入っています。「ランダムに埋める」と「クリア」でやり直せます。
- 値を入力して操作を押します。プッシュ、エンキュー、挿入、削除、検索、巡回、Union、Findなどです。ステップは自動で再生され、「戻る」「ステップ」「再生」「最後」でもう一度たどれます。
- 図の下の行で各ステップの内容を読み、タイルでサイズ、高さ、直前の操作の仕事量を確かめ、表で実行時間を比べてください。
リスト、スタック、キュー
いちばん単純な構造は要素を一列に並べます。スタックは片方の端だけで操作するので、最後に入れた要素が最初に出てきます。積み重ねた皿のようなものです。キューは末尾に加えて先頭から取り出します。窓口に並ぶ列のようなものです。ここでのキューはリングバッファに入っています。先頭と末尾は固定された配列の中を回り、最後まで行くと最初に戻ります。満杯になると、要素は2倍の大きさのバッファにコピーされます。連結リストはノードをポインタでつなぐので、先頭への挿入はほとんど手間がかかりませんが、末尾やあるインデックスを見つけるにはリンクを1つずつたどらなければなりません。
木、ヒープ、ハッシュテーブル、集合
二分探索木は小さい値を左に、大きい値を右に置くので、木が茂っている限り、探索は1ステップごとに候補を半分に減らせます。AVL木と赤黒木は回転によってそれを保ちます。その回転は目で見ることができ、場合ごとに名前がついています。ヒープは最小または最大の値だけを一番上に置き、優先度付きキューに必要なのはそれだけです。ハッシュテーブルはキーから計算したバケットへ直接飛び、衝突に対処しなければなりません。トライは単語の接頭辞を共有し、Union-Findは2つの要素が同じ集合に属するかどうかをほぼ一定時間で答えます。
よくある質問
どのデータ構造を使えばよいですか?
いちばんよく尋ねる質問によります。要素を届いた順またはその逆順で処理するならスタックかキュー、キーを引くならハッシュテーブル、キーを順番どおりに取り出したり最も近いキーを探したりもするならAVL木や赤黒木のような平衡探索木、いつも最小か最大の要素だけが必要ならヒープ、単語や接頭辞ならトライ、合わさっていくグループを追跡するならUnion-Findです。
AVL木と赤黒木の違いは何ですか?
どちらも二分探索木を浅く保つので、探索、挿入、削除はいずれもlog nに比例する時間で済みます。AVL木はより厳密にバランスを取り、各ノードの左右の高さの差が1以内なので、探索が少し速くなります。赤黒木はもっと余裕を許し、変更時の回転が少なくて済むため、多くの標準ライブラリが順序付きのマップやセットに使っています。
なぜハッシュテーブルは最悪の場合に遅くなるのですか?
多くのキーが同じバケットに入ると、探索ではそれらを1つずつ調べることになり、リストと変わらなくなります。よいハッシュ関数はキーを均等に散らし、テーブルは混みすぎる前に大きくなるので、探索は平均して一定時間で済みます。テーブルサイズを10にして同じ数字で終わる数値を入れたり、互いにアナグラムの単語を入れたりして、衝突が積み重なる様子を見てください。
AVLのノードの横にある数字は何ですか?
バランス係数です。ノードの左部分木の高さから右部分木の高さを引いた値です。AVL木では、どのバランス係数も−1、0、+1のいずれかでなければなりません。挿入や削除でどれかが+2か−2になると、木はそのノードで回転します。場合(LL、RR、LR、RL)は余分な高さがどちらに傾いているかを示し、回転が1回か2回かを決めます。
何かがサーバーに送られますか?
いいえ。どの操作もお使いのブラウザー内で実行され、各構造の内容はこのブラウザーのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ