Chave mais próxima em uma BST
A missão
Problema
Uma árvore binária de busca (BST) guarda chaves inteiras distintas. Dada a raiz dela e um alvo que pode ter parte fracionária, retorne a chave mais próxima do alvo. Se duas chaves estiverem igualmente próximas, retorne a menor. A árvore sempre tem pelo menos um nó.
Exemplos
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 e 6 estão ambos a uma unidade de distância, e 4 é o menor
Input: same tree; target = 12.2
Output: 14
Por quê: 14 está a 1,8 de distância, enquanto 10 está a 2,2
Input: tree = a single node 7; target = -100
Output: 7
Por quê: edge case: a única chave é a mais próxima
Dicas
0 / 3
Visitar todos os nós e guardar o melhor funciona, mas ignora a ordenação que faz disso uma árvore de busca.
As duas chaves que cercam o alvo, a maior abaixo dele e a menor acima dele, ficam ambas no caminho que uma busca normal pelo alvo percorreria.
Desça a partir da raiz como se estivesse buscando o alvo. Em cada nó, compare a distância dele com a melhor encontrada até agora, preferindo a chave menor em caso de empate; depois vá para a esquerda se o alvo for menor que o nó e para a direita caso contrário.
- Tempo-alvo
- O(h)
- Espaço-alvo
- O(1)
Restrições
- keys are distinct integers
- the tree has at least one node
- the target may have a fractional part
Solução
Uma busca pelo alvo segue um único caminho da raiz até uma folha, e as chaves logo abaixo e logo acima do alvo estão ambas nele, porque a busca precisa virar em cada uma delas. A chave mais próxima é uma dessas duas, então basta verificar os nós do caminho. A regra de desempate é tratada comparando o par formado pela distância e pela chave, que prefere a chave menor quando as distâncias empatam. O tempo é O(h) para uma árvore de altura h, e o espaço é 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)) # -> 7Travou na ideia, e não no código? Inserção e busca em BST explica isso.