Ist die Höhe des Baumes die Anzahl der Kanten oder die Anzahl der Knoten?

7

Ich bin so verwirrt von einigen Online-Theoremen über Baumhöhen. Bedeutet Baumhöhe die Anzahl der Kanten oder Knoten? Wenn Knoten, enthält es den Knoten, von dem aus gezählt wird? Kann die Höhe eines Baumes bei 0 beginnen?

Olórin
quelle

Antworten:

6

Wie Yuval sagt , gibt es keine Standarddefinition. Dies liegt nicht daran, dass Informatiker unentschlossen sind, sondern daran, dass es manchmal bequemer ist, eine Definition zu verwenden, und manchmal bequemer, die andere zu verwenden. Zum Beispiel ein vollständiger, ausgeglichener binärer Höhenbaum h hat 2h Blätter, wenn Sie Höhe als Anzahl der Kanten und definieren 2h- -1Scheitelpunkte insgesamt, wenn Sie die Höhe als Anzahl der Scheitelpunkte definieren. Jede dieser Aussagen wird weniger bequem, wenn Sie die andere Definition verwenden und weiter schreiben müssenh- -1 oder h+1.

Die Situation ist genau die gleiche wie bei den natürlichen Zahlen: Manchmal ist es bequemer zu sagen, dass Null eine natürliche Zahl ist (zum Beispiel sind die natürlichen Zahlen nur dann ein Semiring , wenn Null enthalten ist); In anderen Fällen ist es bequemer, Null wegzulassen (z. B. wenn Sie immer durch eine natürliche Zahl dividieren möchten). In der Tat passieren ähnliche Dinge in der gesamten Mathematik. Ein anderes Beispiel ist, dass es üblich ist, darauf zu bestehen, dass Graphen mindestens eine Kante (oder mindestens einen Scheitelpunkt) haben, um zu vermeiden, dass Sie alle Ihre Theoreme "IfG ist also nicht trivial ... "

David Richerby
quelle
5

Es gibt keine einzige akzeptierte Definition. Einige Autoren definieren es als die Anzahl der Kanten, andere als die Anzahl der Knoten. Einige Autoren verwenden beide Definitionen sogar in verschiedenen Veröffentlichungen. Aufgrund dieses verwirrenden Sachverhalts sollte in jedem Papier angegeben werden, welche Definition es verwendet.

Yuval Filmus
quelle
0

Die Höhe eines Baums bedeutet einfach die Gesamtzahl der Knoten in diesem Baum auf dem Pfad vom Wurzelknoten zum tiefsten Knoten im Baum. Wenn beispielsweise die Höhe eines Baums 'h' ist, dann die minimale Anzahl von Knoten darin Baum kann b 'h' sein und die maximale Anzahl von Knoten kann 2 ^ h-1 sein.

Manisha
quelle
1
Nein, wie in den anderen Antworten angegeben, gibt es zwei "konkurrierende", aber unterschiedliche Definitionen der Höhe eines Baumes.
David Richerby