サブツリーサイズで注釈が付けられたバイナリ検索ツリーの実装はありますか

Question

このリンク（下部近く）で説明されているツリーデータ構造を調査しています。

http://sigpipe.macromates.com/2009/08/13/maintaining-a-layout/

このデータ構造は指の木である可能性があると言及されています。しかし、指の木に関するより多くの研究の後、これには指の木が指の木を作る「指」がないことがわかりました。代わりに、これは単なる注釈付きのバイナリツリー（サブツリーサイズが注釈されている）のようです。

このデータ構造の既存の実装（任意の言語）を知っていますか？ いいえ 機能的なプログラミング言語での実装）？

または、既存のツリーデータ構造にサブツリーサイズの注釈を改造する最も最適な方法は何ですか？

ありがとう！

Answer 1

サイモン・タタムのカウントされたBツリー 似ています。ノードカウントがのようなバッファーの幅に置き換えられた場合 調整, 、これらは次のような操作を提供します ロープ.

実際には、あなたが参照するページを読んでから、編集者のピーステーブルまたはラインテーブルのように使用されていることがわかります

論文では、 Read-Optimizedデータストレージで更新を調整するための位置デルタツリー, 、著者は、ツリーのノードの間に保持する不変性に関して動作する木を提示します。 ザナドゥのエンフィラード カウントされたBツリーも似ています。

Answer 2

Githubに電話がかかっているプロジェクトがあります Boost.Intrusive Annotated Trees これは、boost.intrusiveのサブツリーカウントなどの注釈に一般的なサポートを提供することを目的としています。サブツリーカウントは、私の元のユースケースでした。

現在、C ++ 11バリアン酸テンプレートが必要であり、RBTreeのみをサポートしていますが、機能し、これらの制限の両方を時間内に削除したいと考えています。 アップデート: ：現在、C ++ 03でビルドします。それでもRbtreeのみをサポートしています。

サブツリーカウントアノテーションで使用する場合、それはジョーダンが上記の答えで説明しているものに似ています - 各ノードで計算（左+右+1）です。実装はまったく異なります - 任意のノードおよび/または値の特性で動作します。注釈の更新は、代わりにRBTreeアルゴリズムに統合され、再計算の数を最小限に抑えます。

Answer 3

先日尋ねた質問に基づいて、同様の何かを実装しました。ブーストに注釈を追加しました::侵入:: rbtree/avltreeノードは、各サブツリーのサイズを計算します（foreach node count = node-> left-> count + node-> count-> count + 1）。 set_parent、set_left、およびset_rightのboost value_traitsフックを使用して、ツリーの挿入/削除/リバランスに関するこの更新を実行します。参照したサイトで述べられているように、各ノードを更新した後、現在のノードのサイズを更新し、ルートを押すまでツリーを通過し、各ノードのサイズを更新します。

問題は、特定の位置で木に挿入したいときに発生します。これを行う瞬間、ツリー構造のキー注文不変を無効にすることになります。これは、キーごとに効率的なO（log n）ルックアップを実行できないことを意味します。しかし、もしあなたがそれを望むなら、とにかくサイズの注釈は必要ないでしょう。