Persistent林

永続BSTを path copying で成長させ、過去の版に戻ってクエリに答える。

永続データ構造(Driscoll, Sleator, Tarjan 1989)は、更新後も過去の版を保持し続けるデータ構造。path copying方式では更新時にルートから対象ノードまでのパス上のみコピーし、残りは旧版と共有する。
更新コスト/版間ジャンプ O(log n)、空間も同オーダー。可逆計算と血縁関係にある「履歴を破壊しない」設計思想。

挿入

挿入のたびに新しい版が生まれ、旧版は保存される。

版 (Versions: 1)

クリックで版を切替。緑=現在表示中。

クエリ・ミッション

挿入してから出題を生成します

正解0

不正解0

スコア—

目標 5問正解—

解説

version i のルートから新しい version i+1 のルートへ、変更したパス上のノードだけを新規作成。図中で太線=新規ノード、細線=共有ノード。

操作

整数を入力して挿入するたびに新しい版が右上にチップで追加される。チップをクリックで版を切替表示。クエリ・ミッションでは指定された版で「特定のキーが存在するか」「最小値/最大値」「ノード数」のいずれかを当てる。5問正解でクリア。