Range Sum of BST

Q: Qual é a complexidade de tempo de Range Sum of BST?

A travessia podada visita os k nós dentro do intervalo, além dos nós em no máximo dois caminhos a partir da raiz: tempo O(h + k) para uma árvore de profundidade h , e O(n) quando todos os valores estão dentro do intervalo. A pilha ou a recursão ocupa O(h) de espaço.

Q: É possível resolver a soma do intervalo em uma BST com uma travessia em ordem?

Sim. Uma travessia em ordem lista os valores em ordem crescente, então você adiciona os valores assim que eles atingem low e para no primeiro que ultrapassa high . A parada antecipada economiza trabalho no lado direito da árvore; a poda economiza trabalho em ambos os lados.

Q: Você deve usar recursão ou uma pilha para a soma de intervalo de uma BST?

Ambas funcionam. Aqui, a profundidade é de no máximo 14, então a recursão permanece rasa. Uma pilha explícita evita o limite de recursão em uma árvore alta com milhares de níveis.

FácilÁrvore binária de busca Percurso em árvores

+10

Uma árvore de busca binária é armazenada no array tree em ordem por níveis: a raiz está no índice 0, os filhos do nó no índice i estão em 2*i+1 (à esquerda) e 2*i+2 (à direita), e -1 indica uma posição vazia. Em uma árvore de busca binária, todo valor na subárvore esquerda de um nó é menor que o valor do nó, e todo valor na subárvore direita é maior.

Retorne a soma dos valores de todos os nós v para os quais low ≤ v ≤ high, ou 0 quando não houver nenhum.

Função

rangeSumBST(tree: integer-array, low: integer, high: integer) → integer

treeinteger-array: a árvore binária de busca em ordem por nível, com -1 para um espaço vazio
lowinteger: o menor valor a contar
highinteger: o maior valor a ser contado
Retornainteger: a soma dos valores dos nós entre low e high, incluindo ambos

Restrições

1 ≤ tree.length ≤ 32767
Cada tree[i] é -1 ou um valor com 0 ≤ tree[i] ≤ 10⁵.
tree[0] nunca é -1, então a árvore tem pelo menos um nó.
O array pode terminar com entradas -1 extras após o último nó.
Ambos os filhos de um espaço vazio também estão vazios, e a profundidade é no máximo 14.
A árvore é uma árvore binária de busca válida, portanto todos os seus valores são distintos.
0 ≤ low ≤ high ≤ 10⁵
A resposta cabe em um inteiro com sinal de 32 bits.

Exemplos

Entrada: tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]low = 9high = 31
Saída: 88
Explicação: Os valores de 9 a 31 são 10, 12, 15, 20 e 31, que somam 88. 3, 8 e 40 ficam fora do intervalo.

Entrada: tree = [50, 25, 75, -1, -1, -1, -1]low = 60high = 70
Saída: 0
Explicação: A árvore contém 25, 50 e 75, e nenhum deles está entre 60 e 70, então a soma é 0. As quatro entradas -1 são os espaços vazios dos filhos de 25 e 75.

Entrada: tree = [6, 2, 9, 1, 4, 7]low = 4high = 4
Saída: 4
Explicação: Com low e high ambos iguais a 4, apenas um nó com valor 4 é contabilizado. O 4 no índice 4 é o filho direito de 2, então a resposta é 4.

Para ir além

Se você tivesse que responder a milhares de consultas diferentes (low, high) na mesma árvore, como poderia responder a cada uma em tempo O(log n)?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Visitar cada nó e somar os valores dentro do intervalo está correto. A ordem da árvore de busca permite fazer menos: o valor de um nó indica em qual lado estão os valores menores e os maiores, então uma subárvore que não pode conter valores do intervalo nunca é explorada.

Visite cada nó

Intuição

Um filho é válido apenas se seu índice estiver dentro do array e o valor nessa posição não for -1. No primeiro exemplo, o 12 no índice 4 tem 10 e 15 nos índices 9 e 10, e o 31 no índice 2 tem um espaço à esquerda vazio no índice 5.

Todo valor no intervalo está em algum nó, então uma travessia com pilha que alcança todos os nós e soma os valores com low ≤ v ≤ high obtém a soma correta. Ela ignora a ordem da árvore de busca, então visita todos os n nós mesmo quando o intervalo contém apenas alguns valores.

Algoritmo

Coloque o índice da raiz 0 em uma pilha e defina total = 0.
Retire um índice i da pilha. Se low ≤ tree[i] ≤ high, adicione tree[i] a total.
Coloque 2*i+1 e 2*i+2 na pilha quando estiverem dentro do array e não forem -1.
Quando a pilha estiver vazia, retorne total.

def rangeSumBST(tree, low, high):
    n = len(tree)
    total = 0
    stack = [0]  # node indexes still to visit; the root is never empty
    while stack:
        i = stack.pop()
        value = tree[i]
        if low <= value <= high:
            total += value
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and tree[left] != -1:
            stack.append(left)
        if right < n and tree[right] != -1:
            stack.append(right)
    return total

Podar seguindo a ordem da árvore de busca

Intuição

A subárvore esquerda de um nó que contém v tem apenas valores menores que v. Se v ≤ low, nenhum deles está no intervalo, então ignore essa subárvore. Se v ≥ high, a subárvore direita tem apenas valores maiores que high, então ignore-a. No primeiro exemplo, 31 é igual a high, então seu filho direito 40 nunca é empilhado. 8 está abaixo de low, então seu filho esquerdo 3 é ignorado, mas seu filho direito 12 é visitado, porque valores entre 8 e 20 podem estar no intervalo.

Você visita os k valores no intervalo, além dos nós em no máximo dois caminhos a partir da raiz: tempo O(h + k) para profundidade h. Quando o intervalo abrange a árvore inteira, isso ainda é O(n).

Algoritmo

Empilhe o índice da raiz 0 em uma pilha e defina total = 0.
Retire um índice i da pilha e leia v = tree[i]. Se low ≤ v ≤ high, some v a total.
Se v > low, empilhe o filho esquerdo 2*i+1 quando ele existir.
Se v < high, empilhe o filho direito 2*i+2 quando ele existir.
Quando a pilha estiver vazia, retorne total.

def rangeSumBST(tree, low, high):
    n = len(tree)
    total = 0
    stack = [0]  # node indexes still to visit; the root is never empty
    while stack:
        i = stack.pop()
        value = tree[i]
        if low <= value <= high:
            total += value
        left, right = 2 * i + 1, 2 * i + 2
        # Smaller values sit on the left, larger on the right: skip a side the range cannot reach.
        if value > low and left < n and tree[left] != -1:
            stack.append(left)
        if value < high and right < n and tree[right] != -1:
            stack.append(right)
    return total

Armadilhas e casos extremos

Usar comparações estritas. As duas extremidades são incluídas, então o terceiro exemplo, com low = high = 4, deve incluir o 4.
Podar um nível cedo demais. Em v = low, a subárvore esquerda pode ser descartada, mas em v = low + 1 ela pode conter o próprio low.
Descartar os dois lados de um nó fora do intervalo. O 8 no primeiro exemplo é menor que low, mas sua subárvore direita contém 10, 12 e 15.
Ler um filho além do fim do array. Verifique 2*i+1 < tree.length antes de ler e trate -1 como ausência de filho.
Em Lua e R, os arrays começam em 1: mantenha os índices dos nós baseados em 0 para a aritmética 2*i+1 e leia tree[i + 1].

Perguntas frequentes3

Qual é a complexidade de tempo de Range Sum of BST?

A travessia podada visita os k nós dentro do intervalo, além dos nós em no máximo dois caminhos a partir da raiz: tempo O(h + k) para uma árvore de profundidade h, e O(n) quando todos os valores estão dentro do intervalo. A pilha ou a recursão ocupa O(h) de espaço.

É possível resolver a soma do intervalo em uma BST com uma travessia em ordem?

Sim. Uma travessia em ordem lista os valores em ordem crescente, então você adiciona os valores assim que eles atingem low e para no primeiro que ultrapassa high. A parada antecipada economiza trabalho no lado direito da árvore; a poda economiza trabalho em ambos os lados.

Você deve usar recursão ou uma pilha para a soma de intervalo de uma BST?

Ambas funcionam. Aqui, a profundidade é de no máximo 14, então a recursão permanece rasa. Uma pilha explícita evita o limite de recursão em uma árvore alta com milhares de níveis.

def rangeSumBST(tree, low, high):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]
low = 9
high = 31

Saída Esperada