Was ist das Besondere an einem Binärbaum?
Binärbäume sind in der Informatik die am häufigsten verwendete Unterart der Bäume. Im Gegensatz zu anderen Arten von Bäumen können die Knoten eines Binärbaumes nur höchstens zwei direkte Nachkommen haben. Meist wird verlangt, dass sich die Kindknoten eindeutig in linkes und rechtes Kind einteilen lassen.
Was versteht man unter Baumstruktur?
Unter einer Baumstruktur versteht man in der Informatik eine Struktur, die aus sogenannten Knoten und Kanten besteht, sowie aus inneren Knoten und Blättern. Optisch dargestellt ähnelt es einem Baum, was die Bezeichnung “Baumstruktur” erklärt.
Was bedeutet Baumstruktur?
Eine Baumstruktur ist eine Datenstruktur aus Kanten und Knoten, die wie ein Baum aufgebaut ist. Ein Baum besteht aus einer Wurzel und Blättern, sowohl in der realen Welt als auch in der Informatik. Bäume in der Informatik haben noch Kanten und innere Knoten. Rechts ist ein sehr kleiner, beschrifteter Baum zu sehen.
Was ist ein binärer Baum?
Ein binärer Baum ist ein Baum, dessen Kinder sind nie mehr als zwei. Ein binärer Suchbaum folgt aus der invariante, dass das linke Kind einen kleineren Wert als der root-Knoten s-Taste, während Sie das Rechte Kind sollte haben einen größeren Wert als der root-Knoten ist der Schlüssel.
Wie funktioniert der Suchbaum?
Der Name „Suchbaum“ lässt sich darauf zurückführen, dass das Auffinden von Daten sehr schnell funktioniert. Durch die Funktionsweise der kleiner-größer-Vergleiche, können binäre Suchbäume einen direkten Pfad ablaufen, anstatt den ganzen Baum durchsuchen zu müssen.
Ist der linke und der rechte Teilbaum ausgeglichen?
Noch effizienter gestaltet sich das Suchen, wenn der Baum ausgeglichen ist. Er ist ausgeglichen (AVL-Baum; benannt nach Adelson, Velskii and Landis [1962]) wenn für jeden Knoten gilt, dass sich der linke und der rechte Teilbaum in ihren Höhen um maximal 1 unterscheiden.