質問: 木構造やグラフ理論に対する基礎以上の深い知見がないため、場当たりでいくつか試しました。(AVL木やB木など、一通り学んでみたのですが、この問題にマッチするか分かりませんでした。) まず探索に対してはハッシュテーブルに[Hash:Node]という形式でデータを保存し、キーを渡されると定数時間で取り出せるように試みました。ノードは ``` class Node { var item: Item var children: [Node] var prent: Node? var index: Int } ``` 上記のような構造を作り、追加・挿入・削除のたびに木をトラバースしてインデックスの振りなおしを試みました。変更のあったノードからルートへのパスにマークを付け、マークのついたノードより左の部分木には探索を行わない(枝刈り?)探索も試みました。 一次元の配列はハッシュテーブルの中身をインデックスでソートして、中身のアイテムだけ取り出すことで実現を試みました。 一応これらでも振る舞いとして意図通りに動いたものの、どうも効率が良いとは思えず、質問に至りました。 もしご存知であれば、何か該当するデータ構造やアルゴリズムについて「このキーワードでググれば分かるよ」程度でも教えていただると助かります。よろしくお願いします。
回答: おそらくNativeTreeと言われるものかと思います。 インデックスで別次元にデータを保持していますが、インデックスをやめて直接データをNodeに保持すれば最もシンプルなツリー構造と言えるでしょう。 それがNativeTreeともいわれている形になります。 今回の場合はデータを別の次元に保持しているだけで、実際はNativetreeから離れていないように思えます。 以下、蛇足ですが、 > > 探索に対してはハッシュテーブルに[Hash:Node]という形式でデータを保存し、キーを渡されると定数時間で取り出せるように試みました > > > 探索とは経路探索(Aにたどり着くためにはどの経路がいいのか?)や深さ探索(Bの子どもたちの最大の深さは?)がメインになります。どのノードにアクセスすればいいかわかっている状況でノードのデータを探しに行くことはどのツリー構造でも定数でアクセスができるでしょう。 経路探索をしてみるとなかなか大変なことに気づくと思います。