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 个元素。然后按顺序给我：x_1，x_2，...，x_n。

但是对于 Sum_even() 我可能还应该在每个节点中包含具有偶数和奇数索引的元素的总和。虽然在插入或删除时很难更新。它应该如何工作，有人可以帮忙吗？

4

1 回答 1

2

您不必在节点中存储子树的大小。AVL 树只存储左右子树的高度差：-1、0 或 +1。

为了便于维护sum_even，您需要为每个节点存储sum_even和sum_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 回答