Escreva uma função que retorne o elemento menor ou igual (floor) que um de referência x em uma ABB.

Passo 1

O enunciado pede uma função que, dada uma ABB e um valor de referência x, retorne o maior elemento na árvore que seja menor ou igual a x (chamado de floor). Vamos usar a propriedade de Busca Binária (árvore à esquerda valores menores, à direita valores maiores) para dirigir a busca de forma eficiente.

Passo 2

Em cada nó, comparamos o valor do nó atual com x. Se forem iguais, já encontramos o piso exato e podemos retornar esse valor.
Se o valor do nó atual for maior que x, então todo elemento na subárvore direita também será maior que x. Logo, o piso só pode estar na subárvore esquerda; repetimos a busca lá.
Se o valor do nó atual for menor que x, então esse nó é um candidato ao piso. Porém, pode existir um valor maior, mas ainda ≤ x, na subárvore direita. Então buscamos recursivamente lá e, se encontrarmos um candidato melhor, o retornamos. Caso contrário, mantemos o candidato atual.

Passo 3

Quando chegamos em um ponteiro nulo, significa que não há piso naquele caminho, então retornamos null ou outro indicador de “não encontrado”.

Passo 4

A complexidade dessa abordagem é O(h), onde h é a altura da árvore, porque em cada nível descemos apenas por um dos lados.
Agora, vamos colocar isso em pseudocódigo na forma de uma função recursiva.

Resposta

function floor(node, x):
if node == null:
return null
if node.key == x:
return node.key
if node.key > x:
return floor(node.left, x)
// aqui node.key < x, é candidato ao piso
floorRight = floor(node.right, x)
if floorRight != null:
return floorRight
else:
return node.key

Exercícios relacionados