Was ist ein Suchbaum?
Ein Suchbaum ist eine Datenstruktur, die in der Computerprogrammierung verwendet wird, um eine Liste von Daten zu enthalten und zu organisieren. Jeder Suchbaum besteht aus einem geordneten Satz von Knoten. Diese Knoten können mit null oder mehreren anderen verbunden werden Die einzelnen Knoten enthalten einige Daten sowie Verknüpfungen zu anderen Knoten. Die in den Knoten des Baums enthaltenen Daten sind sehr häufig in einer bestimmten Reihenfolge angeordnet, damit effiziente Algorithmen suchen können. Einfügen und Entfernen von Knoten mit Leichtigkeit.
Die Knoten eines Suchbaums werden mit vier wichtigen Begriffen beschrieben: Der Anfang eines Baums, an dem sich der erste Knoten befindet, wird als Root bezeichnet. Wenn ein Knoten Links zu sub enthält -nodes, dieser Knoten wird als übergeordneter Knoten bezeichnet. Knoten, die sich unter dem übergeordneten Knoten befinden, werden als untergeordnete Knoten bezeichnet, und jeder Knoten, der keine untergeordneten Knoten hat, wird als Blatt bezeichnet. Ein Stammknoten wird identifiziert, weil er keinen übergeordneten Knoten und Blattknoten keine untergeordneten Knoten hat.
Ein Programm kann in einem Baum nach Daten suchen, indem es an einem bestimmten Knoten beginnt, eine bedingte Prüfung durchführt und dann zum nächsten logischen Knoten wechselt, wenn die erforderlichen Daten nicht vorhanden sind Diese Suche kann unterschiedlich lange dauern. Wenn der Suchbaum während des Hinzufügens und Entfernens von Knoten organisiert ist, kann die Suche sehr schnell erfolgen. Wenn ein Baum zusammengestellt wird Ist zufällig, unsortiert oder erlaubt mehrere Eltern, kann die Suche sehr lange dauern.
Ein Faktor, der sich auf die Verwendung von Suchbäumen auswirkt, ist das Problem des Gleichgewichts: Ein ausgeglichener Baum ist einer, bei dem sowohl das rechte als auch das linke untergeordnete Element des Stammknotens dieselbe Tiefe von untergeordneten Knoten enthalten oder innerhalb einer Anzahl von einem Knoten liegen Die Tiefe eines Baums ist die Anzahl der Knoten vom untersten Blatt eines Baums bis zur Wurzel. Ein unausgeglichener Baum kann alle Knoten auf nur einer Seite oder alle Knoten haben Die Knoten sind linear ohne Verzweigungen angeordnet. Wenn die Tiefe eines Baums zunimmt, kann sich die Geschwindigkeit der Suchalgorithmen drastisch verringern.
Es gibt bestimmte Arten von Suchbäumen, die als selbstausgleichend bezeichnet werden. Diese Bäume verwenden Vorgänge wie die Baumrotation, um das Gleichgewicht aufrechtzuerhalten und gleichzeitig die Reihenfolge der Daten in den Blättern beizubehalten Baumrotationen können ein Programm beim Hinzufügen und Entfernen von Knoten verlangsamen. Dem steht die Geschwindigkeit gegenüber, mit der Daten abgerufen werden können.
Obwohl es viele Arten von Suchbäumen gibt, stellt die häufigste Baumdatenstruktur einen binären Suchbaum dar. Dieser Datentyp besteht aus Knoten mit jeweils null bis zwei untergeordneten Knoten. Es gibt nur einen Stammknoten. und alle Blätter im Baum sind in aufsteigender Reihenfolge von links nach rechts nach den Daten geordnet, die sie enthalten.Viele Algorithmen existieren für binäre Suchbäume, die dies können Bestelldaten sehr einfach machen.
Es gibt keine einheitliche Standardimplementierung für Suchbaumknoten. Die Knoten können durch eine Vielzahl von Datenstrukturen dargestellt werden. Arrays von Arrays können verwendet werden, ebenso wie verknüpfte Listen multipliziert werden können Der Suchbaum verwendet eine benutzerdefinierte Datenstruktur, die die Ausführung der vom Programm geforderten Vorgänge erleichtert. Einige Standard-Programmierbibliotheken enthalten sogar eigene interne Implementierungen von Suchbäumen.