algorithm - 增强AVL树，序列

我在书中找到这个：

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（），我可能还应该在每个节点中包含具有偶数和奇数索引的元素之和尽管在插入或删除时很难更新。怎么办，有人能帮忙吗？

最佳答案

不必在节点中存储子树的大小。AVL tree只存储左右子树的高度差：-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

关于algorithm - 增强AVL树，序列，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13884167/