問題タブ [multiway-tree]

私は現在、さまざまなデータ構造について独学していますが、さまざまな種類のツリーに少し不満を感じています。何かを二分探索木に編成する目的は理解できますが、多元探索木の実用的なアプリケーションは見当たりません。多元探索木を使用して実装した問題の例を誰か教えてください。

多面木の高さはどうやって求めるのですか? 二分木の高さを知りたい場合は、次のようにすることができます。

しかし、同様の再帰的方法を多元木に適用できるかどうかはわかりません。

C# 用のファイル ベースのマルチウェイ B ツリー クラスを実装する必要があります。C++ と C で利用できる同様の機能がありますが、C# で使用したいと考えています。また、MonoTouch などのいくつかの代替 .NET 実装で使用したいので、ソース コードとしても利用できる必要があります。

非ファイル ベースのMultiway B-Treeを知っている人がいる場合、これをファイル ベースに簡単に適応させることができません。各 Multiway ページ/ノードの配列をファイル内のレコード/セクターにします。そして、変更したら保存します。

誰？

検索機能とランク機能を備えた ADT が必要です。つまり、STL マップのインターフェイスに加えて、関数「int get_rank(key)」が必要です。

このような関数の標準的な実装では、自己均衡検索ツリー (STL マップ/セットで使用される黒赤ツリーなど) のすべてのノードで追加の整数フィールドをサポートおよび更新する必要があります。しかし、STLマップ/セットはこれを行わないようです。

可能な限り最高の時間複雑度を持つ標準コンテナー (STL、Boost) に基づくソリューションを探しています。 key も O(log n) かかります。

要素のランクとは、マップ/セットのすべての要素のソートされたシーケンスにおける要素の位置を意味します。

例。セット = {0, 4, 6, 7, 8} ランク (0) = 1、ランク (4) = 2、ランク (6) = 3、ランク (7) = 4、ランク (8) = 5。

私たちの意見では、上記の時間の複雑さの制約の下では、1 つはキーで並べ替え、もう 1 つはランクで並べ替えた 2 つのマップの組み合わせでは問題を解決できません。

ありがとう。

これは難しい質問ではないはずですが、続行する前に誰かにバウンスしてもらいたいと思います。これらの予想されるアクティビティに基づいて、使用するデータ構造を決定する必要があります。

1. ソートされた順序で頻繁に繰り返す必要があります（先頭から開始）。
2. ソートされたビューから任意の要素を削除/復元する必要があります。
3. 後で、データを頻繁に再利用して、複数の並べ替えられたビューを操作します。
4. また、後で、ソートされたビュー内の要素の位置を頻繁に変更します。

ちなみに、これはJavaです。

私の最善の推測は、カスタムのリンクされたハッシュセット（リンクを並べ替えられた順序で配置するため）をロールするか、ツリーセットを使用することです。しかし、私はまだ完全にはわかりません。推奨事項？

編集：任意の削除/復元のため、おそらくツリーセットに固執する必要がありますよね？

実際、必ずしもそうとは限りません。うーん...

私は非常に大きい階層的に編成されたデータツリーを表すC++クラスを持っています（〜Gb、基本的にはメモリ内で逃げることができるのと同じ大きさです）。STLリストを使用して、各ノードの情報と他のノードへのイテレータを格納します。各ノードには親が1つだけありますが、0から10の子があります。抽象化すると、次のようになります。

load（）とsave（）をディスクに実装したいのですが、かなり高速であるはずですが、明らかな問題は次のとおりです。

1. サイズは事前にわかりません。

2. データには、揮発性のイテレータが含まれています。

3. 私のC++に対する無知は驚異的です。

誰かが純粋なC++ソリューションを提案できますか？

99プロローグ問題と呼ばれる素晴らしい問題セットがあります。問題P70はタイトルで言及されているものです。そしてここに、たった5行しかかからないこの問題の素晴らしいPrologソリューションがあります。ただし、Prologについての私の理解は限られています。

このソリューションは、Cのような形式（itertoolsは利用できません）ではどのように見えますか？

リクエストにより編集。私は著作権を侵害しないことを望みます。

問題：

BNFの構文：

差分リストを使用した優れたソリューション：

更新:
私がやろうとしていることの例をさらに見つけました: Managing Hierarchical Data in MySQL。私はそれをやりたいのですが、JavaScript で、より具体的には reddit.com である階層構造のコメントを取り込むアプリを構築しているためです。Chrome Web ブラウザーに Pretty JSON 拡張機能がある場合は、reddit に移動してスレッドのコメントをクリックし、URL に .json を追加して、解析しているものを確認します。
コメントを解析し、適切な HTML を追加してネストされていることを示すだけで、JSON データを問題なく取得できます。
解決策のアイデアはありますか?

古い質問:
私はプログラムに取り組んでいて、コードを書く前にロジックを理解する必要がある部分に来ました。ツリー形式のデータを取り込んでいますが、親ノードごとに複数の子が存在する可能性があり、データを見つけることができる唯一のツリーは、重みのあるツリーまたは各ノードが最大で 2 つの子ノードを持つツリーです。だから私は、次のようにツリーの各ノードを評価するアルゴリズムを理解しようとしています:

今、アルゴリズムがどのように機能するかを書き出そうとすると、ネストされた for/while ループを書くことになりますが、ツリーの高さのレベルごとにループを書くことになります。ノードごとの子これは機能しません。ある時点で、このような木をトラバースする方法を学んだことは知っていますが、今は完全に逃げています。ループに関してこれがどのように行われるか知っている人はいますか?

データ構造の研究を再開しました。私はこれの実用的な使用法をほとんど見つけませんでした。それらの1つは、ディスク上のファイルシステムに関するものでした。誰かがm-wayツリーの実際の使用例をもっと教えてもらえますか？

次の木を想像してみてください。

たとえば、FがAの子孫であるかどうかを照会する方法を探しています（注：FはAの直接の子孫である必要はありません）。これは、この特定の場合に当てはまります。より大きな潜在的な子孫ノードプールに対してテストする必要があるのは、限られた量の潜在的な親ノードのみです。

ノードが潜在的な親プール内のノードの子孫であるかどうかをテストする場合、すべての潜在的な親ノードに対してテストする必要があります。

これが思いついたものです：

• マルチウェイツリーをトライに変換します。つまり、上記のツリーのすべてのノードに次のプレフィックスを割り当てます。

  /li>

• 次に、可能なすべてのプレフィックスサイズのビット配列を予約し、テスト対象の親ノードを追加します。つまり、Cが潜在的な親ノードプールに追加されている場合は、次のようにします。

  /li>

• ノードが潜在的な親ノードの子孫であるかどうかをテストするときは、そのtrieプレフィックスを取得し、最初の「プレフィックス配列」（上記を参照）の最初の文字を検索し、存在する場合は、2番目の「プレフィックス」の2番目のプレフィックス文字を検索します配列」など、つまりFをテストすると次のようになります。

  そうです、FはCの子孫です。

このテストは最悪の場合のO（n）のようです。ここで、n =最大プレフィックス長=最大ツリーの深さです。したがって、最悪のケースは、ツリーを上ってノードを比較するという明白な方法とまったく同じです。ただし、テスト対象のノードがツリーの最下部近くにあり、潜在的な親ノードが最上部にある場合、これははるかに優れたパフォーマンスを発揮します。両方のアルゴリズムを組み合わせると、両方の最悪のシナリオが緩和されます。ただし、メモリのオーバーヘッドが問題になります。

それを行う別の方法はありますか？どんなポインタでも大歓迎です！