Escreva uma função que retorne o elemento menor ou igual (floor) que um de referência
em uma ABB.
Passo 1
O enunciado pede uma função que, dada uma ABB e um valor de referência
, retorne o maior elemento na árvore que seja menor ou igual a
(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
. Se forem iguais, já encontramos o piso exato e podemos retornar esse valor.
Se o valor do nó atual for maior que , então todo elemento na subárvore direita também será maior que
. Logo, o piso só pode estar na subárvore esquerda; repetimos a busca lá.
Se o valor do nó atual for menor que , então esse nó é um candidato ao piso. Porém, pode existir um valor maior, mas ainda ≤
, na subárvore direita. Então buscamos recursivamente lá e, se encontrarmos um candidato melhor, o retornamos. Caso contrário, mantemos o candidato atual.
Se o valor do nó atual for maior que
Se o valor do nó atual for menor que
Passo 3
Quando chegamos em um ponteiro nulo, significa que não há piso naquele caminho, então retornamos
ou outro indicador de “não encontrado”.
Passo 4
A complexidade dessa abordagem é
, onde
é 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.
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
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