Dado o seguinte problema:

"Armazene os maiores 5000 números de um fluxo de números"

A solução que vem à mente é uma árvore de pesquisa binária que mantém uma contagem do número de nós na árvore e uma referência ao menor nó quando a contagem atinge 5.000. Quando a contagem atinge 5000, cada novo número a ser adicionado pode ser comparado a o menor item da árvore. Se maior, o novo número pode ser adicionado então o menor removido e o novo menor calculado (o que deve ser muito simples já tendo o menor anterior).

Minha preocupação com essa solução é que a árvore binária é naturalmente desviada (como estou excluindo apenas de um lado).

Existe uma maneira de resolver este problema que não cria uma árvore terrivelmente distorcida?

Caso alguém queira, incluí pseudo-código para minha solução abaixo:

process(number)
{
  if (count == 5000 && number > smallest.Value)
  {
    addNode( root, number)
    smallest = deleteNodeAndGetNewSmallest ( root, smallest)
  }
}

deleteNodeAndGetNewSmallest( lastSmallest)
{
  if ( lastSmallest has parent)
  {
    if ( lastSmallest has right child)
    {
      smallest = getMin(lastSmallest.right)
      lastSmallest.parent.right = lastSmallest.right
    }
    else
    {
      smallest = lastSmallest.parent
    }
  }
  else 
  {
    smallest = getMin(lastSmallest.right)
    root = lastSmallest.right
  }
  count--
  return smallest
}

getMin( node)
{
  if (node has left)
    return getMin(node.left)
  else
    return node
}

add(number)
{
  //standard implementation of add for BST
  count++
}