Range Sum of BST

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

El recorrido podado visita los k nodos dentro del rango, además de los nodos de como máximo dos rutas desde la raíz: tiempo O(h + k) para un árbol de profundidad h , y O(n) cuando todos los valores están dentro del rango. La pila o la recursión ocupa un espacio de O(h) .

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

Sí. Un recorrido en orden enumera los valores en orden creciente, así que agregas los valores cuando alcanzan low y te detienes en el primero que supera high . La detención anticipada ahorra trabajo en el lado derecho del árbol; la poda lo ahorra en ambos lados.

Q: ¿Deberías usar recursión o una pila para la suma de un rango en un BST?

Ambos funcionan. Aquí la profundidad es como máximo 14, así que la recursión se mantiene poco profunda. Una pila explícita evita el límite de recursión en un árbol alto con miles de niveles.

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

+10

Un árbol de búsqueda binaria se almacena en el arreglo tree en orden por niveles: 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), y -1 marca una posición vacía. En un árbol de búsqueda binaria, todos los valores del subárbol izquierdo de un nodo son menores que el valor del nodo, y todos los valores de su subárbol derecho son mayores.

Devuelve la suma de todos los valores de los nodos v que cumplan low ≤ v ≤ high, o 0 si no hay ninguno.

Función

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

treeinteger-array: el árbol de búsqueda binaria 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 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. El 3, el 8 y el 40 quedan fuera del intervalo.

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 para 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 en 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.

Para ir más allá

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

Pistas

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

0 de 3 abiertas

Solución

Recorrer cada nodo y sumar los valores que están dentro del rango es correcto. El orden del árbol de búsqueda te permite hacer menos: el valor de un nodo te indica en qué lado están los valores menores y los mayores, así que nunca se explora un subárbol que no pueda contener valores dentro del rango.

Visita cada nodo

Intuición

Un hijo existe solo si su índice está dentro del arreglo y el valor allí no es -1. En el primer ejemplo, el 12 del índice 4 tiene 10 y 15 en los índices 9 y 10, y el 31 del índice 2 tiene un espacio izquierdo vacío en el índice 5.

Cada valor del rango se encuentra en algún nodo, así que un recorrido con pila que alcanza todos los nodos y suma los valores que cumplen low ≤ v ≤ high obtiene la suma correcta. Ignora el orden del árbol de búsqueda, así que visita los n nodos, incluso cuando el rango contiene solo unos pocos valores.

Algoritmo

Coloca el índice raíz 0 en una pila y establece total = 0.
Extrae un índice i. Si low ≤ tree[i] ≤ high, suma tree[i] a total.
Coloca 2*i+1 y 2*i+2 en la pila 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

Poda según el orden del árbol de búsqueda

Intuición

El subárbol izquierdo de un nodo que contiene v solo tiene valores menores que v. Si v ≤ low, ninguno de ellos está dentro del rango, así que omite ese subárbol. Si v ≥ high, el subárbol derecho solo tiene valores mayores que high, así que omítelo. En el primer ejemplo, 31 es igual a high, por lo que su hijo derecho 40 nunca se apila. 8 está por debajo de low, así que se omite su hijo izquierdo 3, pero se visita su hijo derecho 12, porque los valores entre 8 y 20 pueden estar dentro del rango.

Visitas los k valores del rango, además de los nodos de como máximo dos caminos desde la raíz: tiempo O(h + k) para una profundidad h. Cuando el rango abarca todo el árbol, sigue siendo O(n).

Algoritmo

Apila el índice raíz 0 y establece total = 0.
Desapila 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

Usar comparaciones estrictas. Se cuentan ambos extremos, así que el tercer ejemplo, con low = high = 4, debe contar el 4.
Podar un paso demasiado pronto. En v = low se puede descartar el subárbol izquierdo, pero en v = low + 1 puede contener el propio low.
Descartar ambos lados de un nodo que está fuera del rango. El 8 del primer ejemplo es menor que low, pero su subárbol derecho contiene 10, 12 y 15.
Leer un hijo más allá del final del arreglo. Comprueba 2*i+1 < tree.length antes de leer y trata -1 como si no hubiera ningún hijo.
En Lua y R, los arreglos empiezan en 1: mantén los índices de los nodos en base 0 para la aritmética de 2*i+1 y lee tree[i + 1].

Preguntas frecuentes3

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

El recorrido podado visita los k nodos dentro del rango, además de los nodos de como máximo dos rutas desde la raíz: tiempo O(h + k) para un árbol de profundidad h, y O(n) cuando todos los valores están dentro del rango. La pila o la recursión ocupa un espacio de O(h).

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

Sí. Un recorrido en orden enumera los valores en orden creciente, así que agregas los valores cuando alcanzan low y te detienes en el primero que supera high. La detención anticipada ahorra trabajo en el lado derecho del árbol; la poda lo ahorra en ambos lados.

¿Deberías usar recursión o una pila para la suma de un rango en un BST?

Ambos funcionan. Aquí la profundidad es como máximo 14, así que la recursión se mantiene poco profunda. Una pila explícita evita el límite de recursión en un árbol alto con miles de niveles.

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

Prueba #1

Prueba #2

Prueba #3

Argumentos

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

Salida Esperada