Clave más cercana en un BST
La misión
Problema
Un árbol binario de búsqueda (BST) guarda claves enteras distintas. Dada su raíz y un objetivo que puede tener parte decimal, devuelve la clave más cercana al objetivo. Si dos claves están igual de cerca, devuelve la menor. El árbol siempre tiene al menos un nodo.
Ejemplos
Input: tree = 8, left 3 with children 1 and 6 (6 has children 4 and 7),
right 10 with a right child 14; target = 5
Output: 4
Por qué: 4 y 6 están a uno de distancia, y 4 es el menor
Input: same tree; target = 12.2
Output: 14
Por qué: 14 está a 1.8 de distancia, mientras que 10 está a 2.2
Input: tree = a single node 7; target = -100
Output: 7
Por qué: caso límite: la única clave es la más cercana
Pistas
0 / 3
Visitar todos los nodos y quedarte con el mejor funciona, pero ignora el orden que hace de esto un árbol de búsqueda.
Las dos claves que rodean al objetivo, la mayor por debajo de él y la menor por encima, están ambas en el camino que tomaría una búsqueda normal del objetivo.
Baja desde la raíz como si buscaras el objetivo. En cada nodo, compara su distancia con la mejor encontrada hasta ahora, prefiriendo la clave menor en caso de empate, y luego ve a la izquierda si el objetivo es menor que el nodo y a la derecha en caso contrario.
- Tiempo objetivo
- O(h)
- Espacio objetivo
- O(1)
Restricciones
- keys are distinct integers
- the tree has at least one node
- the target may have a fractional part
Solución
Una búsqueda del objetivo sigue un único camino de la raíz a una hoja, y las claves justo por debajo y justo por encima del objetivo están ambas en él, porque la búsqueda tiene que girar en cada una de ellas. La clave más cercana es una de esas dos, así que basta con revisar solo los nodos del camino. La regla de desempate se resuelve comparando el par formado por la distancia y la clave, que prefiere la clave menor cuando las distancias coinciden. El tiempo es O(h) para un árbol de altura h y el espacio es O(1).
class T:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def closest_key(node, target):
best = node.val
while node:
# closer wins, and on a tie the smaller key wins
if (abs(node.val - target), node.val) < (abs(best - target), best):
best = node.val
node = node.left if target < node.val else node.right
return best
tree = T(8, T(3, T(1), T(6, T(4), T(7))), T(10, None, T(14)))
print(closest_key(tree, 5)) # -> 4
print(closest_key(tree, 12.2)) # -> 14
print(closest_key(T(7), -100)) # -> 7¿Lo que te frena es la idea y no el código? Inserción y búsqueda en un BST lo explica.