Wie ein binärer Suchbaum aus einem Array erstellen
Am Dienstag mag ich Wege diskutieren, die Sie für eine Kodierung Interview vorbereiten können, und heute werde mich diskutieren, wie ein binären Suchbaum aus einem Array zu erstellen. Wenn es um die Entwickler Job-Interviews kommt, in Bezug auf Fragen Datenstrukturen sind sehr beliebt und sind deshalb wichtige for.Binary Suchbäume herzustellen, ist eine meiner Lieblings-Datenstrukturen, mit zu arbeiten, weil sie unglaublich effizient, wenn sie ordnungsgemäß verwaltet, und sie sind auch einfach zu verstehen.
Lassen Sie uns beginnen, indem zunächst einige Regeln für Binary Search Trees Gründung:
- Ein Elternknoten hat, höchstens 2 Kind-Knoten.
- Der linke Kindknoten ist immer kleiner als die übergeordneten Knoten.
- Der rechte Kindknoten ist immer größer als oder gleich dem übergeordneten Knoten.
Vor ein paar Wochen bedeckt ich, wie binäre Suche funktioniert. so wenden Sie sich bitte, dass die Post für den Such Teil des Algorithmus zu verweisen. In diesem Leitfaden werde ich erörtern, wie Sie einen binären Suchbaum aus einem Datenfeld erstellen können.
Hier ist die Anordnung, die wir für dieses Tutorial verwenden werden:
Dies ist ein grundlegender Integer-Array, bestehend aus sieben Werten, die in unsortierten Reihenfolge sind.
Erstellen Sie einen binären Suchbaum
Der erste Wert in dem Array 10 ist, so ist der erste Schritt in die Baum Konstruktion wird 10, um den Wurzelknoten, wie hier gezeigt:
Mit dem Wurzelknoten-Set, alle übrigen Werte werden Kinder dieses Knotens sein. Referenzierung unsere Regeln von Anfang an dieses Postens wir die untergeordneten Knoten wissen, wie die rechte oder linke Kindknoten abhängig von deren Wert bezeichnet werden. Daher ist der erste Schritt, den wir für das Hinzufügen der 7 zu dem Baum nehmen würden wird es an den Root-Knoten zu vergleichen:
Wenn die 7 weniger als die 10, wird es der linke Kindknoten werden. Wenn die 7 größer oder gleich 10 ist, wird es nach rechts zu bewegen. Da wir wissen, dass die 7 weniger als 10 bezeichnen wir sie als linken Kindknoten, wie hier gezeigt.
Recursively Führen Vergleiche für jedes Element
Nach dem gleichen Muster, führen wir den gleichen Vergleich mit dem Wert 14 in dem Array. Vergleicht man den Wert von 14 auf den Wurzelknoten von 10 wissen wir, dass 14 das richtige Kind ist.
Wir machen die Art und Weise durch das Array wir zum 20. kommen wir mit den Vergleich der Array 10 beginnen werde, die es ist größer als. Also haben wir nach rechts zu bewegen und vergleichen Sie es mit 14, dann ist es mehr als 14 und 14 hat keine Kinder nach rechts, so machen wir 20 das richtige Kind von 14.
Unser Baum kommt gut voran. Jetzt haben wir den Wert 1. Nach dem gleichen Muster wie die anderen Werte werden wir 1 bis 10 vergleichen, nach links bewegen und vergleichen Sie es mit 7 und schließlich 1 das linke Kind des 7 Knoten machen.
Mit dem 5-Wert vergleichen wir es zum 10. Seit 5 weniger als 10 wir nach links überqueren und vergleichen Sie es mit 7. Da wir wissen, dass 5 weniger als 7 wir den Baum weiter nach unten und vergleichen 5 mit dem Wert 1. Mit 1, aber keine untergeordneten Knoten und 5 größer als 1 ist wissen wir 5 das richtige Kind des 1 Knoten zu machen.
Schließlich werden wir den Wert 8 in den Baum eingefügt werden. Mit 8 weniger als 10 bewegen wir uns nach links und vergleichen Sie es mit 7. 8 ist größer als 7, so bewegen wir uns nach rechts und füllen Sie den Baum zu machen 8 das rechte Kind von 7.
Ich hoffe, dass Sie die einfache Eleganz von binären Suchbäumen zu schätzen wissen. Wie so viele Themen in der Programmierung und im Leben, die Stärke der binären Suchbäume kommt von ihrer Fähigkeit, Daten zu ermöglichen, in kleine, verbundenen Komponenten, gebrochen werden. Von diesem Punkt können wir mit den vollständigen Daten in einer organisierten Art und Weise eingestellt arbeiten. In Bezugnahme auf die binäre Tutorial Suchbaum habe ich zuvor, konnten wir den Baum nehmen, die wir in diesem Handbuch aufgebaut und effizient durch suchen jedes Element zu finden, die in dem Array zuvor gewesen waren.
Mögliche Probleme mit Binary Search Trees
So groß wie binäre Suchbäume sind, gibt es ein paar Einschränkungen im Auge zu behalten.
Wenn wir versuchen, den binären Suchbaum-Algorithmus auf diesem Baum, um es auszuführen genau das gleiche durchführen würde, als ob wir einfach über das Array iteriert, bis wir den Wert fanden wir suchten. Die Stärke der binären Suche kommt von der Möglichkeit, schnell die unnötige Werte herauszufiltern. Wenn ein Baum unausgeglichen ist, vor allem, wie die Art des Baumes, die von einem sortierten Feld führen würden, wird es nicht die gleichen Vorteile wie ein ausgewogenen Baum ergeben. Sie können es auf die endgültige Ausgabe, die unsere unsortierten Array hier erzeugt vergleichen zurück.
All dies bedeutet, ist, dass es wichtig ist, die Daten zu verstehen, die Sie gerade arbeiten, wenn Sie erstellen einen binären Suchbaum. Sie können Subroutinen, wie Randomisierung ein Array integrieren, bevor Sie einen binären Suchbaum erstellen es zu balancieren. In Zukunft werde ich auch Themen im Zusammenhang zu AVL und Rot Schwarz Bäume. Diese Arten von Algorithmen sorgen dafür, dass ein Baum ist Behält die richtige Balance Eigenschaften.
Ich hoffe, dass dies einen hilfreichen Begleiter war zu verstehen, wie man praktisch einen binären Suchbaum aus einer Array-Datenstruktur erstellen. Viel Glück mit dem Interview!