Wie hoch ist die Höhe eines leeren BST, wenn Sie es im Kontext zum Ausgleich verwenden?

Question

Angenommen, der Datentyp für eine BST ist wie folgt definiert (in SML)

datatype 'a bst_Tree =
   Empty
 | Node of (int * 'a) * 'a bst_Tree * 'a bst_Tree;

Es gibt also zwei Fälle, in denen die BST ist Empty Oder es kann sowohl einen (Schlüssel, Wert) als auch zwei Kinder haben.

Nun, für den Fall einer AVL, bei der der Zustand ist

In einem AVL -Baum unterscheiden
_{- Avl Tree Wikipedia}

Ich möchte in der Lage sein, eine Höhenfunktion zu erstellen, um zu überprüfen, ob der Baum ausgeglichen ist. Mein aktuelles Setup ist wie folgt

fun height (Empty) = ~1
  | height (Node(v, Empty, Empty)) = 0 (* Redundant matching because of third case *)
  | height (Node(v, L, R)) = 1 + Int.max(height(L),height(R))

Ich habe versucht, den Baum in drei Bedingungen zu unterteilen

1. Ein leerer Baum
2. Ein Baum mit einem Wurzelknoten
3. Ein besiedelten Baum

Der Grund dafür ist, dass es keine kanonische Quelle für den Wert für die Höhe von a gibt Empty Baum im Gegensatz zu einem, in dem nur eine Wurzel hat. Für die Zwecke meiner Balance -Funktion hat es den Job gemacht, aber ich versuche eher zu verstehen, warum es keine kanonische Antwort auf die Höhe eines Empty Baum.

Es gibt eine kanonische Antwort, in dem es darum geht, weiter zu sprechen Wikipedia Aber als ich anfänglich über den Stack -Überlauf nachforschte

Herkömmlicherweise entspricht der Wert –1 einem Unterbaum ohne Knoten, während Null einem Subtree mit einem Knoten entspricht.)

Ich packte die Frage, aus der meine Unsicherheit erschien

Was ist die Definition für die Höhe eines Baumes?

Ich denke, Sie sollten sich das ansehen Wörterbuch von Algorithmen und Datenstrukturen auf der NIST -Website. Es gibt eine Definition für die Höhe, dass ein einzelner Knoten Höhe 0 ist.

Das Definition eines gültigen Baumes schließt eine leere Struktur ein. Die Website erwähnt nicht die Höhe eines solchen Baumes, sondern basierend auf der Definition der Höhe sollte er auch 0 sein.

Answer 1

Das Höhe eines verwurzelten Baumes ist definiert als die Länge des längsten einfachen Blatt-zu-Root-Pfades

Bei einem 2 Knotenbaum beträgt diese Länge eindeutig 1.

Bei einem 1 -Knotenbaum (eines Baumes mit nur der Wurzel) muss die Länge 0 sein (es gibt 0 Kanten am Pfad vom Blatt zur Wurzel.)

Bei einem 0 -Knotenbaum macht Well -1 keinen Sinn. Es ist ein Distanz und muss einen Wert haben $ Geq 0 $, aber es ist auch nicht sinnvoll, die Länge von zu messen null.

-1 wird manchmal aufgrund ihrer Konsistenz mit dieser Rezidiv -Beziehung für die Höhe der Knoten ausgewählt: (im Grunde ist das gleiche wie das, was Sie oben gepostet haben)

height(null) = -1
height((v, left, right)) = max(height(left), height(right)) + 1

Aber wir konnten genauso leicht definieren:

height((v, null, null)) = 0
height(null) = 0
height((v, left, right)) = max(height(left), height(right)) + 1

Answer 2

Jede ständige Funktionen als Höhe von Empty, weil nur die Unterschied von Höhen ist wichtig für das Ausgleich. Warum also nicht 0 wählen?