Escreva uma função que retorna verdadeiro se uma árvore é binária de busca e falso caso contrário
Passo 1
O enunciado pede uma função que receba a raiz de uma árvore binária e devolva verdadeiro se ela obedecer às propriedades de uma árvore binária de busca (BST) e falso caso contrário. Para resolver isso, vamos usar conceitos de recursão e intervalos de valores (limites mínimo e máximo) que cada nó pode assumir.
Passo 2
Em uma BST, para todo nó com valor
:
- Todos os valores na subárvore esquerda devem ser menores que
. - Todos os valores na subárvore direita devem ser maiores que
.
Isso vale recursivamente para cada nó, ou seja, cada subárvore também deve satisfazer a condição de BST.
Passo 3
A ideia do algoritmo é passar, em cada chamada recursiva, dois limites
e
. Inicialmente, definimos esses limites como
e
. Ao visitar um nó de valor
:
- Se
não estiver no intervalo , retornamos falso. - Chamamos recursivamente o filho esquerdo com limites
e o filho direito com limites . - A árvore é BST somente se ambas as chamadas retornarem verdadeiro.
Passo 4
Segue o pseudocódigo da função em estilo Python. A função principal é
eh_bst(raiz)
, que invoca um helper recursivo com os limites iniciais.Passo 5
No pior caso, cada nó é visitado exatamente uma vez, e em cada visita fazemos apenas comparações e duas chamadas recursivas. A complexidade de tempo é
, onde
é o número de nós da árvore. A complexidade de espaço (além da árvore) é a profundidade da recursão, no pior caso
em árvores degeneradas e
em árvores balanceadas, sendo
a altura da árvore.
Resposta
def eh_bst(raiz):
def helper(no, minimo, maximo):
if no is None:
return True
# Se o valor do nó não está dentro dos limites válidos, não é BST
if no.valor <= minimo or no.valor >= maximo:
return False
# Verifica recursivamente as subárvores com novos limites
return (helper(no.esquerda, minimo, no.valor)
and helper(no.direita, no.valor, maximo))
# Limites iniciais são -infinito e +infinito
return helper(raiz, float(’-inf’), float(‘inf’))
def helper(no, minimo, maximo):
if no is None:
return True
# Se o valor do nó não está dentro dos limites válidos, não é BST
if no.valor <= minimo or no.valor >= maximo:
return False
# Verifica recursivamente as subárvores com novos limites
return (helper(no.esquerda, minimo, no.valor)
and helper(no.direita, no.valor, maximo))
# Limites iniciais são -infinito e +infinito
return helper(raiz, float(’-inf’), float(‘inf’))