data-structures - 展开树中范围总和的伪代码？

Question

所以我试图实现一个函数： func rsum(root, left, right) 这个函数接受一个范围的值，然后在一个展开树中返回该树中所有键的总和。我希望它在 O(log n) 中工作。

我试过这个：

 s = 0
    if self.root is None:
        return 0

    node = self.root
    if left <= node.value <= right:
        s += node.value
    if  node.value >left  and node.left is not None :
        self.root = node.left
        s += self.range_sum(left, right)
    if node.value < right and node.right is not None:
        self.root = node.right
        s += self.range_sum(left, right)
    return s

虽然它在 O(log n) 中不起作用，但有更好的方法吗？

标签： data-structuresrecursive-datastructuressplay-tree