Algorithmen lernen

Kapitel 6. Binäre Bäume: Die Unendlichkeit in deinerHandfläche

Diese Arbeit wurde mithilfe von KI übersetzt. Wir freuen uns über dein Feedback und deine Kommentare: [e-mail]

In diesem Kapitel lernst du:

• Wie du Binärbäume erstellst und manipulierst, indem du Werte einfügst, entfernst und nach ihnen suchst.

• Wie man einen binären Suchbaum verwaltet, der die globale Eigenschaft durchsetzt, dass:

  • Die Werte im linken Teilbaum eines Knotens sind alle kleiner oder gleich dem Wert dieses Knotens.

  • Die Werte im rechten Teilbaum eines Knotens sind alle größer oder gleich dem Wert dieses Knotens.

• Diese Such-, Einfüge- und Entfernungsoperationen können in ausgeglichenen Binärbäumen O(log N) sein, aber sie können zu einem inakzeptablen O(N) werden, wenn du nicht vorsichtig bist.

• Wie man einen binären Suchbaum nach Einfüge- und Entnahmeoperationen neu ausbalanciert, um O(log N) Leistung für Suche, Einfügen und Entfernen zu garantieren.

• Wie man einen binären Suchbaum durchläuft, um jeden Wert in aufsteigender Reihenfolge mit O(N) Leistung zu verarbeiten.

• Wie man eine binäre Baumstruktur verwendet, um einen Symboltabellen-Datentyp zu implementieren, mit dem zusätzlichen Vorteil, dass die Schlüssel in sortierter Reihenfolge abgerufen werden können.

• Wie man eine binäre Baumstruktur verwendet, um eine Prioritätswarteschlange zu implementieren, mit dem zusätzlichen Vorteil, dass man die (Schlüssel-, Wert-) Einträge in Prioritätsreihenfolge erzeugen kann, ...