Angesichts des folgenden Problems:

"Speichern Sie die 5000 größten Zahlen aus einem Zahlenstrom"

Die Lösung, die in den Sinn kommt, ist ein binärer Suchbaum, der die Anzahl der Knoten im Baum und eine Referenz auf den kleinsten Knoten aufrechterhält, sobald die Anzahl 5000 erreicht. Wenn die Anzahl 5000 erreicht, kann mit jeder neuen hinzuzufügenden Zahl verglichen werden das kleinste Element im Baum. Wenn größer, kann die neue Zahl hinzugefügt, die kleinste entfernt und die neue kleinste berechnet werden (was sehr einfach sein sollte, wenn bereits die vorherige kleinste vorhanden ist).

Meine Sorge bei dieser Lösung ist, dass der Binärbaum natürlich verzerrt wird (da ich nur auf einer Seite lösche).

Gibt es eine Möglichkeit, dieses Problem zu lösen, ohne dass ein schrecklich verzerrter Baum entsteht?

Falls jemand es wünscht, habe ich Pseudocode für meine Lösung so weit unten aufgenommen:

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