Uma Árvore Binária de Pesquisa (em inglês, BST - Binary Search Tree) é um tipo especial de árvore binária que segue duas propriedades:
Todos os nós-filho à esquerda têm um valor menor do que o nó-pai.
Todos os nós-filho à direita têm um valor maior do que o nó-pai.
Assim, para cada nó, ou lhe falta um nó-filho, ou então possui um nó menor à esquerda e um maior à direita.
Uma árvore binária de pesquisa com 8 nós
Esta propriedade é especialmente útil para pesquisar elementos numa árvore binária. Se estivermos à procura de um valor x, desta forma, sabemos sempre para que lado avançar. No exemplo apresentado acima, para encontrar o nó com valor 3, começamos por observar o nó raiz, com valor 5. Como 5 é maior do que 3, avançamos para a esquerda. De seguida, vemos o nó com valor 2 e, como 2 é menor do que 3, avançamos para a direita. Depois examinamos o nó com valor 4 e, como 4 é maior do que 3, avançamos para a esquerda. Por fim, encontramos o nó com valor 3 e, sendo 3 igual a 3, significa que localizámos o nó desejado.
# Assuma que nós inexistentes são None em vez de terem um valor de 0
def search(node: Node | None, x: int):
""" Retorna True se x estiver presente na árvore e False caso contrário """
if node is None: # Se chegámos ao fim da árvore
return False # Não encontrámos o valor x
if x == node.value: # Se x é igual a node.value
return True # => encontrámos o valor x na árvore
if x < node.value: # Se x é menor => precisamos de ir para a esquerda
return search(node.left) # Tentar encontrar x na subárvore esquerda
return search(node.right) # Caso contrário, tentar encontrar x na subárvore direita
Esta forma de pesquisa pode ser muito eficiente se a altura da árvore não for demasiado grande. Em cada iteração, avançamos para a subárvore à esquerda ou à direita, pelo que o número de operações ao pesquisar nesta árvore binária de pesquisa será equivalente à altura da árvore, no pior dos cenários.
Desafio: Verificar se a árvore fornecida é uma BST
Dada uma árvore binária, deve verificar se ela é uma árvore binária de pesquisa.
Entrada
A entrada contém inteiros separados por espaço, representando os valores dos nós da árvore binária. A ordem dos valores é dada percorrendo sempre a subárvore da esquerda para a direita. Um valor de 0 significa que o nó não existe. É garantido que a árvore binária de entrada é válida e que os valores são exclusivos.
Saída
O programa deve imprimir Yes se a árvore binária for uma árvore binária de pesquisa, ou No caso contrário.
Exemplos
Entrada
Saída
1 2 3 8 5 0 0 0 0 5 8 0 0 0 0
No
5 2 7 1 4 0 0 3 0 0 0 6 8 0 0 0 0
Yes
Explicação
Exemplo 1: Apesar de todos os nós-filho à direita serem maiores do que os nós-pai, nem todos os nós-filho à esquerda são menores do que o nó-pai.
Exemplo 2: É uma árvore binária de pesquisa, pois todos os nós-filho à esquerda têm valores menores do que o nó-pai, enquanto todos os nós-filho à direita têm um valor maior do que o nó-pai.
.png?table=block&id=18a2c681-664d-81db-a7aa-f4125f052d8b&cache=v2)
