サブツリーサイズで注釈が付けられたバイナリ検索ツリーの実装はありますか
-
27-10-2019 - |
質問
このリンク(下部近く)で説明されているツリーデータ構造を調査しています。
http://sigpipe.macromates.com/2009/08/13/maintaining-a-layout/
このデータ構造は指の木である可能性があると言及されています。しかし、指の木に関するより多くの研究の後、これには指の木が指の木を作る「指」がないことがわかりました。代わりに、これは単なる注釈付きのバイナリツリー(サブツリーサイズが注釈されている)のようです。
このデータ構造の既存の実装(任意の言語)を知っていますか? いいえ 機能的なプログラミング言語での実装)?
または、既存のツリーデータ構造にサブツリーサイズの注釈を改造する最も最適な方法は何ですか?
ありがとう!
解決
サイモン・タタムのカウントされたBツリー 似ています。ノードカウントがのようなバッファーの幅に置き換えられた場合 調整, 、これらは次のような操作を提供します ロープ.
実際には、あなたが参照するページを読んでから、編集者のピーステーブルまたはラインテーブルのように使用されていることがわかります
論文では、 Read-Optimizedデータストレージで更新を調整するための位置デルタツリー, 、著者は、ツリーのノードの間に保持する不変性に関して動作する木を提示します。 ザナドゥのエンフィラード カウントされたBツリーも似ています。
他のヒント
Githubに電話がかかっているプロジェクトがあります Boost.Intrusive Annotated Trees これは、boost.intrusiveのサブツリーカウントなどの注釈に一般的なサポートを提供することを目的としています。サブツリーカウントは、私の元のユースケースでした。
現在、C ++ 11バリアン酸テンプレートが必要であり、RBTreeのみをサポートしていますが、機能し、これらの制限の両方を時間内に削除したいと考えています。
アップデート: :現在、C ++ 03でビルドします。それでもRbtreeのみをサポートしています。
サブツリーカウントアノテーションで使用する場合、それはジョーダンが上記の答えで説明しているものに似ています - 各ノードで計算(左+右+1)です。実装はまったく異なります - 任意のノードおよび/または値の特性で動作します。注釈の更新は、代わりにRBTreeアルゴリズムに統合され、再計算の数を最小限に抑えます。
先日尋ねた質問に基づいて、同様の何かを実装しました。ブーストに注釈を追加しました::侵入:: rbtree/avltreeノードは、各サブツリーのサイズを計算します(foreach node count = node-> left-> count + node-> count-> count + 1)。 set_parent、set_left、およびset_rightのboost value_traitsフックを使用して、ツリーの挿入/削除/リバランスに関するこの更新を実行します。参照したサイトで述べられているように、各ノードを更新した後、現在のノードのサイズを更新し、ルートを押すまでツリーを通過し、各ノードのサイズを更新します。
問題は、特定の位置で木に挿入したいときに発生します。これを行う瞬間、ツリー構造のキー注文不変を無効にすることになります。これは、キーごとに効率的なO(log n)ルックアップを実行できないことを意味します。しかし、もしあなたがそれを望むなら、とにかくサイズの注釈は必要ないでしょう。