Range Sum of BST

Q: ¿Cuál es la complejidad temporal de la suma de un rango en un BST?

Un recorrido que poda según el orden del árbol de búsqueda visita los k nodos del rango, además de los nodos de como máximo dos caminos desde la raíz; el tiempo es O(h + k) para un árbol de profundidad h . En el peor de los casos, cuando todos los valores están dentro del rango, es decir, O(n) . El espacio adicional es O(h) para la pila o la recursión.

Q: ¿Por qué puedes omitir subárboles en la suma de rangos de un BST?

En un árbol de búsqueda binario, todo valor a la izquierda de un nodo es menor que él y todo valor a la derecha es mayor. Si el valor del nodo es como máximo low , nada de su lado izquierdo puede estar dentro del rango, y si es como mínimo high , nada de su lado derecho puede estarlo. Omitir esos lados nunca deja pasar un valor dentro del rango.

Q: ¿Se puede resolver la suma del rango del BST con un recorrido en orden?

Sí. Un recorrido en orden de un árbol de búsqueda binaria enumera los valores en orden creciente, así que puedes sumar los valores una vez que alcancen low y detenerte en cuanto uno supere high . Da la misma respuesta, y la parada temprana ahorra trabajo en el lado derecho del árbol, mientras que la búsqueda podada también ahorra trabajo en el izquierdo.

Q: ¿Deberías usar recursión o una pila para Range Sum of BST?

Ambos funcionan. La recursión es más corta y, en este caso, la profundidad es de como máximo 14, así que la pila de llamadas se mantiene pequeña. Una pila explícita evita por completo el límite de recursión, lo cual importa en un árbol alto con miles de niveles, y es lo que usan las soluciones de esta página.

FácilÁrbol binario de búsqueda Recorrido de árboles

+10

Recibes un árbol binario de búsqueda almacenado en el arreglo tree por niveles, y dos números low y high. La raíz está en el índice 0, los hijos del nodo en el índice i están en 2*i+1 (izquierda) y 2*i+2 (derecha), -1 marca un espacio vacío y el arreglo puede terminar con entradas -1 adicionales. En un árbol binario de búsqueda, cada valor del subárbol izquierdo de un nodo es menor que el valor del nodo, y cada valor de su subárbol derecho es mayor.

Escribe una función llamada rangeSumBST que devuelva la suma de todos los valores de los nodos v que cumplan low ≤ v ≤ high, o 0 cuando ningún valor esté dentro de ese rango.

Función

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

treeinteger-array: el árbol binario de búsqueda en orden por niveles, con -1 para una posición vacía
lowinteger: el valor más pequeño que se debe contar
highinteger: el valor más grande que se debe contar
Devuelveinteger: la suma de los valores de los nodos entre low y high, ambos incluidos

Restricciones

1 ≤ tree.length ≤ 32767
Cada tree[i] es -1 o un valor con 0 ≤ tree[i] ≤ 10⁵.
tree[0] nunca es -1, así que el árbol tiene al menos un nodo.
El arreglo puede terminar con entradas -1 adicionales después del último nodo.
Ambos hijos de un espacio vacío también están vacíos, y la profundidad es como máximo 14.
El árbol es un árbol binario de búsqueda válido, por lo que todos sus valores son distintos.
0 ≤ low ≤ high ≤ 10⁵
La respuesta cabe en un entero con signo de 32 bits.

Ejemplos

Entrada: tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]low = 9high = 31
Salida: 88
Explicación: Los valores de 9 a 31 son 10, 12, 15, 20 y 31, que suman 88. 3, 8 y 40 quedan fuera del rango.

Entrada: tree = [50, 25, 75, -1, -1, -1, -1]low = 60high = 70
Salida: 0
Explicación: El árbol contiene 25, 50 y 75, y ninguno de ellos está entre 60 y 70, así que la suma es 0. Las cuatro entradas -1 son los espacios vacíos de los hijos de 25 y 75.

Entrada: tree = [6, 2, 9, 1, 4, 7]low = 4high = 4
Salida: 4
Explicación: Con low y high ambos iguales a 4, solo cuenta un nodo con valor 4. El 4 en el índice 4 es el hijo derecho de 2, así que la respuesta es 4.

+14 pruebas ocultas al enviar

Para ir más allá

Si tuvieras que responder miles de consultas distintas (low, high) sobre el mismo árbol, ¿cómo podrías responder cada una en O(log n) de tiempo?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Sumar todos los valores del intervalo es un recorrido sencillo: visita cada nodo y conserva los que encajan. El orden del árbol de búsqueda te permite hacerlo mejor. El valor de un nodo te indica en qué lado se encuentran los valores menores y mayores, así que puedes omitir subárboles enteros sin mirar ni un solo nodo en su interior.

Visita cada nodo

Intuición

Primero, cómo recorrer el arreglo. El nodo del índice i tiene su hijo izquierdo en 2*i+1 y su hijo derecho en 2*i+2. Un hijo es real solo si su índice está dentro del arreglo y el valor que hay allí no es -1. En [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15], la raíz 20 tiene 8 y 31 en los índices 1 y 2, el 12 del índice 4 tiene 10 y 15 en los índices 9 y 10, y el 31 tiene un espacio izquierdo vacío en el índice 5.

Ahora, la idea. Cada valor del rango está en algún nodo, así que un recorrido que llegue a todos los nodos y sume los valores que cumplen low ≤ v ≤ high obtiene la suma correcta. Usa una pila de índices de nodos. Empieza por la raíz, extrae un índice, suma su valor si está dentro del rango y apila cada hijo real.

Esto ignora por completo la propiedad del árbol de búsqueda; funciona con cualquier árbol binario. Recorre los n nodos, tiempo O(n), y la pila contiene los hijos pendientes a lo largo de un camino, espacio O(h) para una profundidad h. Cuando el rango abarca unos pocos valores en un árbol de miles de nodos, se desperdicia la mayor parte de ese trabajo.

Algoritmo

Apila el índice de la raíz 0 en una pila y establece total = 0.
Extrae un índice i. Si low ≤ tree[i] ≤ high, suma tree[i] a total.
Apila 2*i+1 y 2*i+2 cuando estén dentro del arreglo y no sean -1.
Cuando la pila esté vacía, devuelve 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 según el orden del árbol de búsqueda

Intuición

Mantén el mismo recorrido con pila, pero aprovecha el orden. Supón que un nodo contiene v. Su subárbol izquierdo contiene solo valores menores que v. Si v ≤ low, todos ellos son menores que low, así que el subárbol izquierdo no puede aportar nada: omítelo. Del mismo modo, si v ≥ high, el subárbol derecho contiene solo valores mayores que high: omítelo. Así que apilas el hijo izquierdo solo cuando v > low, y el hijo derecho solo cuando v < high.

En el primer ejemplo, con el rango [9, 31], 31 es igual a high, por lo que su hijo derecho 40 nunca se apila. 8 es menor que low, así que se omite su hijo izquierdo 3, mientras que su hijo derecho 12 sigue visitándose, porque los valores entre 8 y 20 pueden estar dentro del rango.

Los nodos que visitas son los k valores dentro del rango más, como máximo, dos caminos desde la raíz hasta una hoja a lo largo de sus bordes, así que el tiempo es O(h + k). Cuando el rango cubre todo el árbol, esto sigue siendo O(n), pero un rango estrecho en un árbol grande solo toca unas pocas docenas de nodos. La pila requiere O(h) de espacio.

Algoritmo

Apila el índice de la raíz 0 en una pila y establece total = 0.
Extrae un índice i y lee v = tree[i]. Si low ≤ v ≤ high, suma v a total.
Si v > low, apila el hijo izquierdo 2*i+1 cuando exista.
Si v < high, apila el hijo derecho 2*i+2 cuando exista.
Cuando la pila esté vacía, devuelve 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

Errores comunes y casos límite

La mayoría de las respuestas incorrectas se deben a los límites del rango o del arreglo.

Usar comparaciones estrictas. Se incluyen ambos extremos, así que cuenta un nodo igual a low o high.
Podar un paso demasiado pronto. Cuando v es igual a low, se puede omitir el subárbol izquierdo, pero cuando v es low + 1, no se puede: podría contener el propio low.
Detenerse en un nodo fuera del rango. Un nodo menor que low todavía puede tener un subárbol derecho lleno de valores dentro del rango, así que omite solo el lado que descartan las reglas de orden.
Leer un índice secundario más allá del final del arreglo. Comprueba 2*i+1 < tree.length antes de leer el valor y trata -1 como si no hubiera un hijo.
Confundir el desplazamiento en Lua y R, donde los arreglos empiezan en 1. Mantén los índices de los nodos basados en 0 para el cálculo 2*i+1 y lee tree[i + 1].

Preguntas frecuentes4

¿Cuál es la complejidad temporal de la suma de un rango en un BST?

Un recorrido que poda según el orden del árbol de búsqueda visita los k nodos del rango, además de los nodos de como máximo dos caminos desde la raíz; el tiempo es O(h + k) para un árbol de profundidad h. En el peor de los casos, cuando todos los valores están dentro del rango, es decir, O(n). El espacio adicional es O(h) para la pila o la recursión.

¿Por qué puedes omitir subárboles en la suma de rangos de un BST?

En un árbol de búsqueda binario, todo valor a la izquierda de un nodo es menor que él y todo valor a la derecha es mayor. Si el valor del nodo es como máximo low, nada de su lado izquierdo puede estar dentro del rango, y si es como mínimo high, nada de su lado derecho puede estarlo. Omitir esos lados nunca deja pasar un valor dentro del rango.

¿Se puede resolver la suma del rango del BST con un recorrido en orden?

Sí. Un recorrido en orden de un árbol de búsqueda binaria enumera los valores en orden creciente, así que puedes sumar los valores una vez que alcancen low y detenerte en cuanto uno supere high. Da la misma respuesta, y la parada temprana ahorra trabajo en el lado derecho del árbol, mientras que la búsqueda podada también ahorra trabajo en el izquierdo.

¿Deberías usar recursión o una pila para Range Sum of BST?

Ambos funcionan. La recursión es más corta y, en este caso, la profundidad es de como máximo 14, así que la pila de llamadas se mantiene pequeña. Una pila explícita evita por completo el límite de recursión, lo cual importa en un árbol alto con miles de niveles, y es lo que usan las soluciones de esta página.

Python

def rangeSumBST(tree, low, high):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado