Tiefensuche vs Breitensuche

Wenn Sie sich die Zeit genommen haben, Code in irgendeiner Form zu studieren, stoßen Sie wahrscheinlich auf Datenstrukturen. Datenstrukturen bestehen aus einer Vielzahl von Möglichkeiten zum Speichern, Organisieren und Bearbeiten von Daten. Einige der beliebtesten sind Arrays, verknüpfte Listen, Stapel, Warteschlangen und binäre Suchbäume. In diesem Artikel konzentrieren wir uns auf zwei verschiedene Methoden zur Annäherung an das Durchqueren von Bäumen: Tiefensuche und Breitensuche.

Was ist ein baum

Ein Baum ist eine Datenstruktur, die aus Knoten besteht, die Zeiger auf andere Knoten enthalten. Im Gegensatz zu Bäumen im wirklichen Leben (oder vielleicht existieren sie irgendwo) steht ein Datenbaum auf dem Kopf. Im Wesentlichen ist die Wurzel oben und die Blätter unten.

Lassen Sie uns das Diagramm aufschlüsseln.

Jeder Baum hat einen einzelnen Wurzelknoten, der sich auf der obersten Ebene befindet (in diesem Fall Ebene 0). Dann sehen wir, dass auf der nächsten Ebene der Wurzelknoten A Zeiger auf die Knoten B und C hat. Ebenso haben die Knoten B und C Zeiger auf den Knoten A. In dieser Situation ist der Knoten A der Elternknoten und die Knoten B und C sind seine Kinder. Weiterhin werden die Knoten B und C als Geschwister betrachtet.

Sie fragen sich möglicherweise, ob es möglich ist, dass ein Knoten mehr als zwei Kinder hat. Die Antwort ist ja! Diese spezielle Darstellung zeigt einen Binärbaum, der durch maximal zwei untergeordnete Knoten für jeden übergeordneten Knoten bestimmt werden kann.

Baum Code

Haftungsausschluss: Ich werde Javascript verwenden, um einen einfachen Baum zu erstellen!

Zunächst müssen wir eine Knotenklasse erstellen:

Wenn wir eine Knotenklasse erstellen, übergeben wir ihr einen Wert oder Daten, der zur Dateneigenschaft des Knotens wird. Wir haben auch übergeordnete und untergeordnete Eigenschaften, die vorerst null bzw. ein leeres Array sind. Schließlich verweist die übergeordnete Eigenschaft auf die übergeordneten Elemente des jeweiligen Knotens und die untergeordnete Eigenschaft auf die untergeordneten Elemente des Knotens.

Dann erstellen wir die Baumklasse:

Die Baumklasse enthält eine einzelne Eigenschaft (root), die anfänglich null ist. Bäume enthalten Prototypmethoden wie contain (), insert () und remove (), aber diese werden für einen regnerischen Tag gespeichert!

Suche!

Sowohl die Tiefensuche als auch die Breitensuche sind Prototypmethoden der Tree-Klasse, mit denen ermittelt wird, ob ein bestimmter Knoten, der bestimmte Daten enthält, in einem Baum vorhanden ist. Die folgende Abbildung zeigt die beiden verschiedenen Suchvorgänge.

Tiefe-Erste Annäherung

Die Methode "Tiefe zuerst" beginnt am Wurzelknoten und bewegt sich zum äußersten linken Knoten. Sobald es den am weitesten links liegenden Knoten erreicht, durchläuft es den Baum zurück zum Stamm und dann zum am weitesten rechts liegenden Knoten. Wenn es auf einen Knoten mit untergeordneten Elementen stößt, durchläuft es die untergeordneten Elemente dieses Knotens von links nach rechts und fährt dann nach rechts fort.

Suchreihenfolge: [10, 4, 1, 9, 17, 12, 18]

Code

Bei der Tiefensuche wird ein Wert als Argument verwendet. Dies ist der Wert, nach dem wir im Baum suchen. Da wir die Knoten von links nach rechts durchlaufen möchten, legen wir die Wurzel als Stapel fest, da wir einen Last-In-First-Out-Ansatz verwenden möchten. Dann führen wir eine while-Schleife durch, die so lange fortgesetzt wird, wie der Stapel Elemente enthält. In der while-Schleife entfernen wir das erste Element im Stapel oder rufen die shift () - Array-Methode auf und setzen sie auf einen Knoten. Wir vergleichen die Daten dieses Knotens mit dem Argumentwert. Wenn sie übereinstimmen, gibt die Funktion true zurück. Ist dies nicht der Fall, werden die untergeordneten Elemente des Knotens an der Vorderseite des Stapels hinzugefügt oder die unhift () -Array-Methode aufgerufen, und die Suche in den neuen Daten wird fortgesetzt. Wenn der bestimmte Wert im Baum nicht vorhanden ist, gibt die Funktion false zurück.

Breitensprung

Der Ansatz mit der ersten Breite beginnt am Wurzelknoten und durchläuft jede nachfolgende Ebene, um nach dem gewünschten Knoten zu suchen. Ähnlich wie bei der Tiefensuche werden die Knoten auf jeder Ebene von links nach rechts gelesen.

Suchauftrag: [10, 4, 17, 1, 9, 12, 18]

Code

Die Breitensuche ähnelt im Code der Tiefensuche. Es wird ein Wert als Argument verwendet. Der Unterschied besteht darin, dass wir anstelle eines Stapels eine Warteschlange verwenden möchten, um einen First-In-First-Out-Ansatz durchführen zu können. In der while-Schleife möchten wir ähnlich wie bei der Tiefensuche die Array-Methode shift () verwenden, um das erste Element der Warteschlange als Knoten zu entfernen. Wenn jedoch die Knotendaten nicht mit dem gewünschten Wert übereinstimmen, werden die untergeordneten Elemente des Knotens nicht verschoben, sondern mit der push () - Array-Methode am Ende der Warteschlange hinzugefügt. Auf diese Weise können wir jeden Knoten in einer Ebene überprüfen, bevor wir die Knoten in der nächsten Ebene durchlaufen. Wenn der Wert nicht gefunden wird, gibt die Funktion genau wie bei der Tiefensuche false zurück.

Welches benutze ich?

Obwohl sowohl die Tiefensuche (DFS) als auch die Breitensuche (BFS) legitime Ansätze sind und zu den gleichen Ergebnissen führen können, wird jeder Ansatz unter bestimmten Umständen bevorzugt. Es ist jedoch nicht oft offensichtlich, welches der beiden Verfahren effizienter ist.

Haftungsausschluss: Dies sind allgemeine Richtlinien! Auf jeden Fall nicht immer die optimalsten Ansätze.

DFS: Im Allgemeinen bevorzugt, wenn der Baum sehr tief ist und gewünschte Werte oder Daten selten auftreten.

BFS: Im Allgemeinen bevorzugt bei flachen Bäumen, die nicht zu breit sind. Wird auch verwendet, wenn bekannt ist, dass der gewünschte Knoten näher an der Wurzelebene liegt.

Wenn Sie sich nicht sicher sind, ist es wahrscheinlich besser, beide Methoden auszuprobieren und festzustellen, welche effizienter ist.

Angenommen, Sie verwenden den Baum oben und suchen nach dem Knoten mit der Nummer 8. Der Baum ist nicht so tief, sodass Sie vielleicht denken, es wäre besser, ein BFS zu verwenden. Es wäre jedoch effizienter, ein DFS zu verwenden.

Vergleichen wir die beiden Methoden und welche Knoten durchlaufen wurden:

DFS: 1, 2, 4, 8

BFS: 1, 2, 3, 4, 5, 6, 7, 8

Wir können bereits erkennen, dass eine Breitensuche mehr Knoten durchläuft und daher Zugriff auf mehr Speicher benötigt.

Wenn wir den Knoten 8 gefunden haben, wäre der DFS-Stapel [8, 9, 5, 3], während die BFS-Warteschlange [8, 9, 10, 11, 13, 14] wäre. Die BFS-Warteschlange enthält 2 weitere Knoten, was in diesem Beispiel nicht viel zu bedeuten scheint. In Bezug auf den Arbeitsspeicher wird jedoch immer noch eine größere Menge verwendet. Daher wäre in dieser speziellen Situation ein DFS effizienter als ein BFS.

Obwohl dieses Beispiel einfach und unkompliziert ist, ist es in Situationen, in denen Bäume tiefer und breiter sind, definitiv viel schwieriger zu bestimmen, welches optimaler ist. Der beste Weg, um die bessere Methode zu diktieren, besteht darin, beides zu versuchen.

Komplexität

Die zeitliche und räumliche Komplexität von DFS und BFS ist recht einfach. Da es sich um eine Baumüberquerung handelt, müssen wir jeden Knoten besuchen, um festzustellen, ob ein Wert oder Daten im Baum vorhanden sind. Ein einzelner Besuch jedes Knotens bedeutet, dass die Zeitkomplexität für DFS und BFS 0 (n) oder linear ist. Wenn wir Bäume als sortierte Arrays betrachten, müssten wir nur eine einzige Zeit durchlaufen, um festzustellen, ob ein Wert mit dem Wert übereinstimmt, nach dem wir suchen. In ähnlicher Weise ist DFS in Bezug auf die Raumkomplexität O (h) und BFS ist O (w). Für DFS steht "h" für Höhe, da der Platzbedarf der Funktion davon abhängt, wie viele Knoten der Baum tief ist. Für BFS steht 'w' ebenfalls für width, da der Abstand davon abhängt, wie breit der Baum ist. Natürlich ändern sich diese großen O-Bezeichnungen in Abhängigkeit von der Datenstruktur, aber aus Gründen der Baumstruktur sind die zeitlichen und räumlichen Komplexitäten gleich.

Vielen Dank, dass Sie sich die Zeit genommen haben, diesen Artikel zu lesen! Wenn Sie Feedback oder Fragen haben, lassen Sie es mich wissen! Hoffe du hast einen schönen Tag!