1

私はこれを本で見つけました：

Design a data structure for maintaining dynamic sequence x_1, x_2,... , x_n 
which provides operations:
Insert(a,i) - inserts a as x_i, indexes from i+1 to n go up by 1
Delete(i) - deletes x_i, indexes from i+1 to n go down by 1
Find(i) - returns element x_i
Sum_even() - returns sum of the elements with even indexes

シーケンスは動的なので、AVLツリーを使用して保持したいと思います。したがって、検索、削除、挿入に標準的なトリックを使用できると思います。このノードをルートとするサブツリーの各ノードサイズを維持するだけです。次に、ツリーを簡単にナビゲートして、O（log n）時間でi番目の要素を見つけることができます。Inorderは私に次のように与えます：x_1、x_2、...、x_n。

しかし、Sum_even（）の場合、各ノードに偶数と奇数のインデックスを持つ要素の合計も必要です。挿入または削除中に更新するのは難しいですが。それはどのように機能する必要がありますか、誰かが助けることができますか？

4

1 に答える 1

2

サブツリーのサイズをノードに保存する必要はありません。AVLツリーは、左右のサブツリーの高さの違い（-1、0、または+1）のみを格納します。

簡単に保守するには、ノードごとにsum_evenを保存する必要があります。これは、サブツリーの偶数/奇数インデックスの値の合計になります。sum_evensum_odd

したがって、各ノードには変数があります。

  • difference左右のサブツリーの高さの違い
  • value
  • parityサブツリーサイズのパリティ（0または1）
  • sum_even
  • sum_odd

挿入と削除には、標準のアルゴリズムhttp://en.wikipedia.org/wiki/AVL_treeを使用します。ただし、影響を受けるノード（ルートノードおよびローテーションされたノードに到達する途中のノード）ごとに、値を更新します。

parity := (left.parity + right.parity + 1) % 2
if left.parity == 0
    sum_even := left.sum_even + right.sum_odd
    sum_odd := left.sum_odd + right.sum_even + value
else
    sum_even := left.sum_even + right.sum_even + value
    sum_odd := left.sum_odd + right.sum_odd
于 2012-12-14T20:47:17.720 に答える