Was ist der Unterschied zwischen Baumtiefe und -höhe?

262

Dies ist eine einfache Frage aus der Algorithmus-Theorie.
Der Unterschied zwischen ihnen besteht darin, dass Sie in einem Fall die Anzahl der Knoten und in einem anderen Fall die Anzahl der Kanten auf dem kürzesten Weg zwischen Wurzel und Betonknoten zählen.
Welcher ist welcher?

Gabriel Ščerbák
quelle
78
Tipp: Um Verwechslungen zwischen den Terminologien zu vermeiden: 1. Größe: Stellen Sie sich vor, Sie messen die Größe einer Person von Zeh bis Kopf (Blatt bis Wurzel). 2. Tiefe: Stellen Sie sich vor, Sie messen die Tiefe eines Meeres von der Erdoberfläche bis zum Meeresboden (Wurzel bis Blatt).
Yesh
@ Yesh Dies ist eine großartige Analogie.
Sonderzeichen
1
Um @Yesh eine hervorragende Analogie hinzuzufügen: Für einige innere Knoten in der Mitte des Baums ist die Tiefe die Anzahl der Ebenen unter dem Wurzelknoten und die Höhe die Ebenen über dem untersten untergeordneten Knoten.
Thomas Nguyen

Antworten:

664

Ich habe gelernt, dass Tiefe und Höhe Eigenschaften eines Knotens sind :

  • Die Tiefe eines Knotens ist die Anzahl der Kanten vom Knoten zum Wurzelknoten des Baums.
    Ein Wurzelknoten hat eine Tiefe von 0.

  • Die Höhe eines Knotens ist die Anzahl der Kanten auf dem längsten Pfad vom Knoten zu einem Blatt.
    Ein Blattknoten hat eine Höhe von 0.

Eigenschaften eines Baumes :

  • Die Höhe eines Baumes wäre die Höhe seines Wurzelknotens
    oder gleichwertig die Tiefe seines tiefsten Knotens.

  • Der Durchmesser (oder die Breite ) eines Baums ist die Anzahl der Knoten auf dem längsten Pfad zwischen zwei beliebigen Blattknoten. Der Baum unten hat einen Durchmesser von 6 Knoten.

Ein Baum mit Höhe und Tiefe jedes Knotens

Daniel AA Pelsmaeker
quelle
21
+1 wollte gerade ein Zitat mit demselben Inhalt von hier hinzufügen: en.wikipedia.org/wiki/Tree_%28data_structure%29
Péter Török
2
ist das bedeutet Höhe == maximale Tiefe
Roottraveller
6
@rkm_Hodor: Ja, die Höhe eines Baumes entspricht immer der Tiefe des tiefsten Knotens.
Daniel AA Pelsmaeker
1
Könnten Sie bitte eine Quelle für Ihre Behauptung anführen, dass der Durchmesser eines Baumes Knoten anstelle von Kanten zählt? Dies steht im Widerspruch zur üblichen Definition des Durchmessers eines Graphen (siehe z. B. en.wikipedia.org/wiki/Distance_(graph_theory) ), der nach dem längsten Pfad fragt.
j_random_hacker
1
@j_random_hacker Es ist eine Frage der Definition, wählen Sie die für Sie nützlichste aus. Um von der Anzahl der Eckpunkte zur Anzahl der Kanten zu gelangen, subtrahieren Sie einfach 1. Ich ziehe es vor, die Anzahl der Eckpunkte zu zählen, da dies zu einem Diagramm mit nur einem Knoten mit der Breite 1 und einem leeren Diagramm mit der Breite 0 führt. Mathworld. wolfram.com/GraphDiameter.html
Daniel AA Pelsmaeker
44

Höhe und Tiefe eines Baumes sind gleich ...

aber Höhe und Tiefe eines Knotens sind nicht gleich, weil ...

Die Höhe wird berechnet, indem vom angegebenen Knoten zum tiefstmöglichen Blatt gewechselt wird.

Die Tiefe wird aus der Durchquerung von der Wurzel zum angegebenen Knoten berechnet.

Praveen_Shukla
quelle
4
"Höhe wird durch Überqueren vom Blatt zum gegebenen Knoten berechnet" ist nicht korrekt, das Blatt muss dasjenige sein, das unter allen Blättern des gegebenen Knotens am tiefsten ist.
mächtige WOZ
14

Nach Cormen et al. Einführung in Algorithmen (Anhang B.5.3): Die Tiefe eines Knotens X in einem Baum T ist definiert als die Länge des einfachen Pfades (Anzahl der Kanten) vom Wurzelknoten von T nach X. Die Höhe eines Knotens Y beträgt Die Anzahl der Kanten auf dem längsten einfachen Abwärtspfad von Y zu einem Blatt. Die Höhe eines Baums ist definiert als die Höhe seines Wurzelknotens.

Beachten Sie, dass ein einfacher Pfad ein Pfad ohne wiederholte Scheitelpunkte ist.

Die Höhe eines Baumes entspricht der maximalen Tiefe eines Baumes . Die Tiefe eines Knotens und die Höhe eines Knotens sind nicht unbedingt gleich. Siehe Abbildung B.6 der 3. Auflage von Cormen et al. zur Veranschaulichung dieser Konzepte.

Ich habe manchmal Probleme gesehen, einen zu bitten, Knoten (Eckpunkte) anstelle von Kanten zu zählen. Bitten Sie daher um Klarstellung, wenn Sie nicht sicher sind, ob Sie Knoten oder Kanten während einer Prüfung oder eines Vorstellungsgesprächs zählen sollten.

Gletscher
quelle
Gibt es einen Unterschied beim Zählen der Knoten und Kanten? Scheint, dass beide das gleiche Ergebnis liefern. Korrigieren Sie mich, wenn ich falsch liege.
VINOTH ENERGETIC
@jdhao wie kann die Tiefe der Wurzel 2 sein? Es ist entweder 0 (wenn Kanten berücksichtigt werden) oder 1 (wenn Knoten berücksichtigt werden).
Neowulf33
@ neowulf33, ja, ich liege furchtbar falsch. Die Tiefe des Wurzelknotens sollte 0 sein. Ich werde meinen Kommentar löschen, um die Leute nicht zu verwirren.
JDHAO
2

Einfache Antwort:
Tiefe:
1. Baum : Die Anzahl der Kanten / Bögen vom Wurzelknoten zum Blattknoten des Baums wird als Tiefe des Baums bezeichnet.
2. Knoten : Die Anzahl der Kanten / Bögen vom Wurzelknoten zu diesem Knoten wird als Tiefe dieses Knotens bezeichnet.

Akshay Sahu
quelle
2

Ein anderer Weg, um dieses Konzept zu verstehen, ist wie folgt: Tiefe: Zeichnen Sie eine horizontale Linie an der Wurzelposition und behandeln Sie diese Linie als Grund. Die Tiefe der Wurzel ist also 0, und alle untergeordneten Elemente wachsen nach unten, sodass jede Knotenebene die aktuelle Tiefe + 1 hat.

Höhe: Gleiche horizontale Linie, aber diesmal ist die Bodenposition externe Knoten, die das Blatt des Baumes sind und nach oben zählen.

Wilson Zhang
quelle
2

Ich wollte diesen Beitrag schreiben, weil ich ein CS-Student bin und immer mehr OpenDSA und andere Open-Source-Lehrbücher verwenden. Aus der am besten bewerteten Antwort geht hervor, dass sich die Art und Weise, wie Höhe und Tiefe unterrichtet werden, von einer Generation zur nächsten geändert hat, und ich poste dies, damit jeder weiß, dass diese Diskrepanz jetzt besteht und hoffentlich keine Fehler mehr verursacht Programme! Vielen Dank.

Von dem OpenDSA Data Structures & Algos-Buch :

Wenn n 1 , n 2 , ..., n k eine Folge von Knoten im Baum ist, so dass n i die Eltern von n i + 1 für 1 <= i <k ist, wird diese Folge als Pfad von n bezeichnet 1 bis n k . Die Länge des Pfades beträgt k - 1. Wenn es einen Pfad von Knoten R zu Knoten M gibt, ist R ein Vorfahr von M und M ein Nachkomme von R. Somit sind alle Knoten im Baum Nachkommen der Wurzel des Baums, während die Wurzel der Vorfahr ist aller Knoten. Die Tiefe eines Knotens M im Baum ist die Länge des Pfades von der Wurzel des Baums nach M. Die Höhe eines Baumes ist eins mehr als die Tiefe des tiefsten Knotens im Baum. Alle Knoten der Tiefe d befinden sich auf Ebene d im Baum. Die Wurzel ist der einzige Knoten auf Ebene 0 und seine Tiefe ist 0.

Abbildung 7.2.1

Abbildung 7.2.1: Ein Binärbaum. Knoten A ist die Wurzel. Die Knoten B und C sind die Kinder von A. Die Knoten B und D bilden zusammen einen Teilbaum. Knoten B hat zwei Kinder: Sein linkes Kind ist der leere Baum und sein rechtes Kind ist D. Die Knoten A, C und E sind Vorfahren von G. Die Knoten D, E und F bilden die Ebene 2 des Baums; Knoten A befindet sich auf Ebene 0. Die Kanten von A nach C nach E nach G bilden einen Pfad der Länge 3. Die Knoten D, G, H und I sind Blätter. Die Knoten A, B, C, E und F sind interne Knoten. Die Tiefe von I beträgt 3. Die Höhe dieses Baumes beträgt 4.

Esche
quelle
Für das, was es wert ist, wurde die Definition unter diesem Link geändert in: "Die Tiefe eines Knotens M im Baum ist die Länge des Pfades von der Wurzel des Baumes nach M. Die Höhe eines Baumes ist die Tiefe des tiefster Knoten im Baum. "
Kaya3