Biorąc pod uwagę następujący problem:

„Przechowuj największe 5000 numerów ze strumienia liczb”

Rozwiązaniem, które przychodzi na myśl, jest binarne drzewo wyszukiwania, które utrzymuje liczbę węzłów w drzewie i odniesienie do najmniejszego węzła, gdy liczba osiągnie 5000. Gdy liczba osiągnie 5000, każdy nowy numer do dodania można porównać do najmniejszy element na drzewie. Jeśli większy, nowy numer może być dodany, a następnie najmniejszy usunięty i nowy najmniejszy obliczony (co powinno być bardzo proste, mając już poprzedni najmniejszy).

Moje zainteresowanie tym rozwiązaniem polega na tym, że drzewo binarne będzie naturalnie wypaczone (ponieważ usuwam tylko z jednej strony).

Czy istnieje sposób na rozwiązanie tego problemu, który nie stworzy strasznie przekrzywionego drzewa?

W przypadku, gdy ktoś tego chce, do tej pory dołączyłem pseudo-kod do mojego rozwiązania:

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++
}