70189


# 概要

タイトル通り、実現したい構造があるのですが、いまいち具体的に言語化もできず、どのようにアプローチしたら良いのか分からず困っているので、以下の要件を実現できる構造をご存知であれば教えていただけると非常に助かります。

  * テーブルに木構造を表示するために、データを一次元配列で提供できる
  * その際、Orderを保持できる(画像のイメージ)
  * 定数時間での検索が可能O(1)
  * AppendToParent, InsertBefore, InsertAfter, DeleteItemsがAPIとして利用可能

[![イメージ](https://i.stack.imgur.com/KQxnZ.png)](https://i.stack.imgur.com/KQxnZ.png)

# 近いもの

[NSOutlineView](https://developer.apple.com/documentation/appkit/nsoutlineview),[OutlineGroup](https://developer.apple.com/documentation/swiftui/outlinegroup)のような仕組みを自作したいです。

# これまで試したこと

木構造やグラフ理論に対する基礎以上の深い知見がないため、場当たりでいくつか試しました。(AVL木やB木など、一通り学んでみたのですが、この問題にマッチするか分かりませんでした。)

まず探索に対してはハッシュテーブルに[Hash:Node]という形式でデータを保存し、キーを渡されると定数時間で取り出せるように試みました。ノードは

[code]

    class Node {
        var item: Item
        var children: [Node]
        var prent: Node?
        var index: Int
    }
    
[/code]

上記のような構造を作り、追加・挿入・削除のたびに木をトラバースしてインデックスの振りなおしを試みました。変更のあったノードからルートへのパスにマークを付け、マークのついたノードより左の部分木には探索を行わない(枝刈り？)探索も試みました。

一次元の配列はハッシュテーブルの中身をインデックスでソートして、中身のアイテムだけ取り出すことで実現を試みました。

一応これらでも振る舞いとして意図通りに動いたものの、どうも効率が良いとは思えず、質問に至りました。

もしご存知であれば、何か該当するデータ構造やアルゴリズムについて「このキーワードでググれば分かるよ」程度でも教えていただると助かります。よろしくお願いします。


CC BY-SA 4.0
2020-09-06T12:15:36.723
70187
2020-09-07T00:58:13.977
2020-09-06T15:38:25.637
3060
8320
question
アルゴリズム データ構造
Outlineビューを実現したいが、木構造を一次元のリストで表現できるような構造の名前を知りたい


おそらくNativeTreeと言われるものかと思います。

インデックスで別次元にデータを保持していますが、インデックスをやめて直接データをNodeに保持すれば最もシンプルなツリー構造と言えるでしょう。  
それがNativeTreeともいわれている形になります。  
今回の場合はデータを別の次元に保持しているだけで、実際はNativetreeから離れていないように思えます。

以下、蛇足ですが、

> 探索に対してはハッシュテーブルに[Hash:Node]という形式でデータを保存し、キーを渡されると定数時間で取り出せるように試みました

探索とは経路探索（Aにたどり着くためにはどの経路がいいのか？）や深さ探索（Bの子どもたちの最大の深さは？）がメインになります。どのノードにアクセスすればいいかわかっている状況でノードのデータを探しに行くことはどのツリー構造でも定数でアクセスができるでしょう。

経路探索をしてみるとなかなか大変なことに気づくと思います。


CC BY-SA 4.0
2020-09-07T00:58:13.977
70189
2020-09-07T00:58:13.977
22665
70187
answer