Dienen binäre Bäume einem bestimmten Zweck beim Speichern hierarchischer Daten? Was ist ihre kanonische Verwendung?

12

Ich verstehe die Struktur von binären Bäumen und wie man sie durchquert. Ich bemühe mich jedoch, ihre tatsächlichen Verwendungen, Zwecke in Programmen und Programmierung zu realisieren. Wenn ich an Beispiele für hierarchische Daten aus der Praxis denke, haben sie mit ziemlicher Sicherheit mehr als zwei Kinder. Beispielsweise kann eine Mutter in einem Stammbaum häufig mehr als zwei Kinder haben.

Sind Binärbäume wirklich nur nützlich, um linear zusammengehörige Daten zu speichern, da Arrays und Listen schneller verarbeitet werden können? Alternativ dienen sie einem bestimmten Zweck beim Speichern hierarchischer Daten? Wenn ja, welche Beispiele gibt es für die Anwendung von Binärbäumen? Welche Daten sind so, dass ein Knoten höchstens 2 Kinder hat?

data-structures binary-tree sw123456
quelle
Ich denke, die Hauptverwendung eines Binärbaums besteht darin, Daten zu bestellen. https://en.wikipedia.org/wiki/Binary_search_tree
Mandrill

Antworten:

25

Nein, binäre Bäume dienen nicht zum Speichern hierarchischer Daten in dem Sinne, an den Sie denken. Der primäre Anwendungsfall für n-ary-Bäume, bei denen nes sich um eine feste Zahl handelt, ist die schnelle Suchfunktion , keine semantische Hierarchie.

Denken Sie an das alte Spiel, in dem eine Person an eine Zahl zwischen 1 und 100 denkt und die andere es mit möglichst wenigen Vermutungen erraten muss. Wenn Sie falsch raten, muss die Person, die an die Zahl denkt, Ihnen mitteilen, ob Sie es auch sind hoch oder zu niedrig? Nach einer Weile wird es langweilig, weil Sie schnell herausfinden, dass Sie immer bei 50 beginnen, dann bei 25 oder 75 beginnen und den zu durchsuchenden Bereich mit jeder neuen Vermutung in zwei Hälften teilen sollten, und schließlich können Sie eine beliebige Zahl erraten in höchstens 7 raten, garantiert.

Es ist vielleicht kein lustiges Spiel, aber diese Eigenschaft macht binäre (und andere n-fache) Bäume nützlich: Sie können sie verwenden, um einen sehr großen Datensatz in sehr kurzer Zeit zu durchsuchen.

Mason Wheeler
quelle
Ausgezeichnete Antwort, vielen Dank. Binärbäume sind also wirklich nur eine andere Struktur zum Speichern von Daten wie in einem Array oder einer Liste, aber mit dem zusätzlichen Vorteil schneller Suchfunktionen?
sw123456
1
@ sw123456: Das stimmt. Wie bei jedem Engineering kommt es zu Kompromissen, (verwendet mehr - und stärker fragmentierten - Speicher als ein Array mit der gleichen Anzahl von Elementen, O (n) Zugriff auf Element #n des Datensatzes anstelle von O (1) Zugriff usw.), aber eine schnelle Suche ist definitiv der Hauptvorteil von Binärbäumen.
Mason Wheeler
@ sw123456 Ich bin froh, dass ich helfen konnte, es zu erklären :)
Mason Wheeler
3
Der Zugriff auf Elemente ist O (log (n)), wenn der Baum ausgeglichen ist. O (n) ist der schlimmste Fall, wenn es entartet ist (die meisten Knoten mit nur einer Klammer).
Mandrill
@ sw123456 Beim Netzwerkrouting wird eine geringfügige Änderung eines Binärbaums namens "Trie" verwendet (der für eine effizientere Ausführung der Problemdomäne erstellt wurde). Es speichert tatsächlich Hierarchieinformationen, während Router den Baum Bit für Bit durchlaufen, wenn sie nach einer IP-Adresse suchen, um herauszufinden, wohin das Paket weitergeleitet werden soll. IP-Adressen sind ebenfalls von Natur aus hierarchisch. Beim Durchlaufen einer IP-Adresse, um die längste Präfixübereinstimmung zu finden, durchläuft der Router die IP-Hierarchie, Subnetz-IPs usw. Semantisch ist dies nicht klar, aber die Beziehung besteht. Router verwenden diese Struktur zur Sucheffizienz, wie Mason antwortete.
Chris Cirefice
3

Jede Baumstruktur, in der ein Knoten eine unbegrenzte Anzahl von untergeordneten Knoten haben kann, kann mithilfe eines Binärbaums implementiert werden.

Ersetzen Sie jeden Knoten in Ihrem Baum durch einen Knoten mit einem rechten und einem linken Zeiger. Der linke Zeiger zeigt auf das erste untergeordnete Element des Knotens. Der rechte Knoten geht zum nächsten Geschwister des Knotens. Alle untergeordneten Knoten eines bestimmten Knotens befinden sich in einer verknüpften Liste, die durch ihre rechten Zeiger verbunden ist, wobei der Kopf der Liste auf den linken Zeiger des übergeordneten Knotens zeigt.

Ihr komplizierter n-Ary-Baum ist zu einem einfachen binären Baum geworden.

Ich bin sicher, das ist in Knuth, Vol. 1 irgendwo.

Justsalt
quelle
Dies ist eine wirklich interessante Implementierung. Habe ich Recht zu der Annahme, dass, da jeder untergeordnete Knoten der Anfang einer verknüpften Liste war, der Baum nicht mehr O (log) n) ist, wenn er ausgeglichen ist, oder O (n), wenn er nicht ist, da der Besuch jedes Knotens beginnen würde aus einer linearen Suche? Diese Implementierung würde zu viel langsameren Suchzeiten führen? Aber die Suchzeiten wären schneller als bei einer linearen Standardstruktur? Habe ich das richtig verstanden?
sw123456
@ sw123456, Wenn der ursprüngliche Baum ausgeglichen wäre, wäre der resultierende Binärbaum mit ziemlicher Sicherheit nicht ausgeglichen. Ich glaube, alles andere hängt davon ab, wie viele Kinder ein Knoten hat. Eine lineare Suche würde nur stattfinden, wenn herausgefunden wird, welchen der untergeordneten Knoten eines bestimmten Knotens gefolgt werden soll. Aber ich bin mir nicht sicher, ob Sie das bei jeder anderen Implementierung eines n-ary-Baums vermeiden können.
Justsalt
2

Binäre Bäume, warum sie verwenden?

Beim Programmieren arbeiten Sie viel mit Sammlungen von Daten des gleichen Typs.

Die zwei grundlegenden Möglichkeiten zum Speichern dieser Daten sind: verknüpfte Listen und Arrays.

Sie haben beide Vor- und Nachteile: In einer verknüpften Liste können Elemente einfach an einer beliebigen Position hinzugefügt oder entfernt werden. Der Zugriff auf ein bestimmtes Element ist jedoch schwieriger, da Sie die Liste durchgehen müssen, bis Sie das gewünschte Element erreicht haben.

  • Es wird nicht effizient gesucht, aber das Einfügen und Löschen ist einfach.

Mit einem Array ist der Zugriff auf ein bestimmtes Element einfach, es ist jedoch schwieriger, ein Element einzufügen oder zu löschen, da Einfügen bedeutet: Array um eins erweitern, alle Elemente vor der Einfügeposition 1 nach rechts verschieben und das Element einfügen.

  • Es wird effizient gesucht (wenn sortiert), aber das Einfügen und Löschen ist schwierig.

Sowohl die verknüpfte Liste als auch das Array haben also Nachteile.

Binäre Bäume werden erstellt, um sowohl Probleme des Arrays als auch der verknüpften Liste zu lösen:

  1. Einfaches Einfügen und Löschen
  2. Einfaches Suchen

Binärbäume sind also ideal, wenn Sie viele Daten haben, die sich regelmäßig ändern.

Pieter B
quelle