webentwicklung-frage-antwort-db.com.de

Tiefe gegen Höhe eines Baumes. Grundlagen auffrischen

Ich mache eine Auffrischung und Algorithmen und Datenstrukturen.

Ich bin verwirrt über das Konzept von Tiefe vs Höhe eines Baumes. In vielen Fällen, insbesondere auf Websites, die sich mit Interviewfragen befassen, werden diese Begriffe meines Erachtens synonym verwendet.

Es scheint mir, dass die Basisliteratur sie als anwendbar für einen Knoten und nicht für einen Baum definiert.

Die Tiefe der Wurzel (die ein Knoten ist) ist also 0. Die Höhe der Wurzel (oder eines beliebigen Unterknotens) ist die maximale Höhe der untergeordneten Knoten.

Wenn Sie diese Begriffe jedoch auf einen Baum anwenden, d. H. Die maximale Tiefe eines Baums ermitteln, scheinen diese Begriffe jetzt "bedeutungslos" zu sein und können austauschbar verwendet werden, d. H. Um die maximale Tiefe zu ermitteln, berechnen Sie einfach die maximale Höhe.

Zum Beispiel in diesem Beitrag Überprüfen Sie, ob der Baum ausgeglichen ist konzentrieren sich die Antworten auf die Höhe des Baums, während sich die Definition des Gleichgewichts auf die Tiefe des Baums beziehen könnte

Ist mein Verständnis korrekt oder vermassele ich diese Grundlagen?

17
Cratylus

Wenn von einem Baum die Rede ist, bedeutet dies dasselbe: die Länge des längsten Pfades von der Wurzel bis zu einem Blattknoten.

9
Tudor

Das depth wird normalerweise verwendet, um eine Eigenschaft eines Baumknotens zu beschreiben, während das height verwendet wird, um die Eigenschaft des gesamten Baums zu beschreiben, wie in den folgenden Beispielen:

  • Der Wurzelknoten hat eine Tiefe von Null
  • Knoten X hat eine Tiefe von N
  • Die Höhe des Baumes ist M

Die Höhe eines Baumes ist definiert als die Tiefe seines tiefsten Knotens.

7
dasblinkenlight

Die Höhe eines Knotens ist die Länge des längsten Abwärtspfads zu einem Blatt von diesem Knoten. Die Höhe der Wurzel ist die Höhe des Baumes .

Die Tiefe eines Knotens ist die Länge des Pfades zu seiner Wurzel (d. H. Seines Wurzelpfades). Dies wird üblicherweise bei der Manipulation der verschiedenen selbstausgleichenden Bäume, insbesondere AVL-Bäume benötigt. Der Wurzelknoten hat die Tiefe Null, Blattknoten haben die Höhe Null und ein Baum mit nur einem einzigen Knoten (also Wurzel und Blatt) hat die Tiefe und Höhe Null. Herkömmlicherweise hat ein leerer Baum (Baum ohne Knoten, falls solche zulässig sind) Tiefe und Höhe –1.

4
gsdf

eine Tiefe ist "wie tief ein Knoten ist" [oder wie weit ist er von der Wurzel entfernt]. Höhe ist "wie hoch der Baum ist" [oder wie weit ist das weiteste Blatt davon entfernt]

Formal:

height(v) = 0                                                              v is a leaf
            max{height(u)|for every u such that u is a son of v} + 1       else

depth(v) = 0                                                                v root
           depth(u) + 1    where u is the parent of v                       else

EDIT: Wenn man sich auf das Konzept der maximalen Tiefe bezieht, ist es identisch mit der Höhe eines Baumes [der an der Wurzel maximal ist], man kann es durch Induktion beweisen.

4
amit

Im binären Suchbaum

  1. Höhe eines Knotens: # Kanten auf dem längsten einfachen Abwärtspfad vom Knoten zu einem Blatt
  2. Höhe eines Baumes: Höhe der Wurzel
  3. Tiefe eines Knotens: Länge des einfachen Pfades (# Kanten) von der Wurzel zum Knoten
0
Hasitha

Knotentiefe: ist die Länge eines Pfades von der Wurzel zu einem Knoten. Höhe eines Knotens: ist die Länge eines Pfades vom Knoten zum innersten Knoten (Blatt).

Aber Höhe und Tiefe beim Baum sind gleich. Baumhöhe = Tiefe eines Baumes = Maximale Höhe = Maximale Tiefe.

0
avishek gurung
private static int getHeight(BTreeNode n){

    if(n == null)
        return 0;

    int lHeight = getHeight(n.left);
    int rheight = getHeight(n.right);

    int height = 1+Math.max(lHeight,rheight);

    return height;
}
0
user3209952

Die Höhe des Knotens bezieht sich auf die Blattlänge des längsten Pfads zum Blattknoten vom Quellknoten.

Die Tiefe des Knotens bezieht sich auf den Stammknoten. - Gesamtlänge vom Quellknoten bis zur Wurzel

Wenn Sie jedoch im Allgemeinen von einem ganzen Baum sprechen, beziehen sich beide auf denselben Baum. Dies unterscheidet sich jedoch nur, wenn Sie einen bestimmten Knoten innerhalb des Baums nehmen

0
nandy

Die Höhe eines Baumes ist die Anzahl der Knoten von der Wurzel bis zum Blatt, die dem längsten Pfad folgen. Wenn wir also einen Knoten (Wurzel selbst) haben, ist die Höhe = 1. Leerer Baum: 0

Die Tiefe oder Ebene eines Knotens ist die Anzahl der Kanten von Wurzelknoten zu diesem Knoten. so..depth von root ist 0.

Auf diese Weise ist die maximale Baumtiefe eins weniger als die Baumhöhe.

0
SunilDwivedi