私はこのリンク（下部近く）で説明されているツリーデータ構造を調査してきました：
http://sigpipe.macromates.com/2009/08/13/maintaining-a-layout/
このデータ構造はフィンガーツリーである可能性があると述べられています。しかし、フィンガーツリーについてさらに調査した結果、フィンガーツリーをフィンガーツリーにする「フィンガー」が不足していることがわかりました。代わりに、これは単なる注釈付きの二分木（サブツリーサイズで注釈が付けられている）のようです。
私自身の実装の参照として使用できるこのデータ構造の既存の実装（任意の言語）を知っていますか（ただし、機能的なプログラミング言語での実装ではないことが望ましい）？
または、サブツリーサイズの注釈を既存のツリーデータ構造に後付けするための最適な方法は何でしょうか。
ありがとう！
サイモンタタムのカウントされたBツリーも同様です。ノード数が微調整のようにバッファの幅に置き換えられた場合、これらはロープのような操作を提供します。
実際、あなたが参照しているページを読むと、それが編集者のピーステーブルやラインテーブルのように使用されていたことがわかります
論文では、更新を読み取り最適化データストレージと調整するためのPositional Delta Treesで、ツリー内のノード間で保持する不変条件に関する動作が、カウントされたB-ツリーも同様です。
Boost.Intrusiveのサブツリーカウントなどのアノテーションの一般的なサポートを提供することを目的とした、Boost.IntrusiveAnnotatedTreesというプロジェクトがgithubにあります。サブツリーカウントは、私の最初のユースケースでした。
現在、C ++ 11の可変個引数テンプレートが必要であり、rbtreeのみをサポートしていますが、機能します。これらの制限の両方を時間内に削除したいと考えています。
更新：C++03でビルドするようになりました。それでもrbtreeのみをサポートします。
サブツリーカウントアノテーションと一緒に使用すると、ジョーダンが上記の回答で説明したものと似ています-各ノードで（左+右+ 1）を計算します。実装はまったく異なります。任意のノードや値の特性で機能します。代わりに、注釈の更新がrbtreeアルゴリズムに統合され、再計算の回数が最小限に抑えられます。
先日尋ねた質問に基づいて、似たようなものを実装しました。各サブツリーのサイズを計算するために、boost::intrusive::rbtree/avltree ノードに注釈を追加しました (foreach ノード数 = ノード->左->カウント + ノード->右->カウント + 1)。set_parent、set_left、および set_right の boost value_traits フックを使用して、ツリーの挿入/削除/再調整でこの更新を実行します。参照したサイトに記載されているように、各ノードの更新後、現在のノードのサイズを更新し、ルートに到達するまでツリーを上に移動し、各ノードのサイズを更新します。
問題は、ツリーの特定の位置に挿入したい場合に発生します。これを行うとすぐに、ツリー構造のキー順序不変条件が無効になります。これは、キーによる効率的な O(log n) ルックアップを実行できないことを意味します。ただし、それが必要な場合は、おそらくサイズの注釈は必要ないでしょう。