Zwei Definitionen von ausgeglichenen binären Bäumen

26

Ich habe zwei Definitionen von ausgeglichenen binären Bäumen gesehen, die für mich unterschiedlich aussehen.

  1. Ein Binärbaum ist ausgeglichen, wenn für jeden Knoten gilt, dass sich die Anzahl der inneren Knoten im linken Teilbaum und die Anzahl der inneren Knoten im rechten Teilbaum um höchstens 1 unterscheiden.

  2. Ein binärer Baum wird ausgeglichen, wenn für zwei Blätter die Differenz der Tiefe höchstens 1 beträgt.

Hat jeder Baum, der def erfüllt. Ich befriedige auch def. 2? Was ist umgekehrt?

data-structures binary-trees Forrest Gump
quelle
2
Haben Sie versucht, beide Richtungen zu beweisen? Was sind Ihre Erkenntnisse?
Raphael

Antworten:

17

Die Definition 1. wird auch als Gewichtsausgleich ¹ und die Definition 2. als Höhenausgleich bezeichnet .

Höhenausgleich bedeutet nicht Gewichtsausgleich; Beispiele sind sowohl AVL- als auch Rot-Schwarz-Bäume. Siehe hier bzw. hier für Beweise.

Gewichtsausgleich bedeutet jedoch Höhenausgleich. Dies kann bewiesen werden, indem durch Induktion (über die Höhe) die folgende stärkere Tatsache gezeigt wird: Ein gewichtsausgeglichener Baum ist auf allen Ebenen bis auf den tiefsten vollständig². Das wesentliche Argument im induktiven Schritt ist, dass die Teilbäume nicht mehr als einen Höhenunterschied haben können, weil sie - beide mit der nach Induktionshypothese behaupteten Eigenschaft - dann nicht gewichtsausgeglichen wären.

  1. Der Artikel enthält eine andere, allgemeinere Definition.
  2. kkk−1
Raphael
quelle
Ich habe gerade festgestellt, dass die stärkere Tatsache verwendet werden kann, um die Beweise, mit denen ich verknüpfe, verschwenderisch zu vereinfachen.
Raphael
Vielleicht ist es eine gute Idee, diese Erkenntnis in Ihre Antwort aufzunehmen.
Diskrete Eidechse
@Discretelizard Du meinst, die anderen Antworten?
Raphael
Oh, ich wusste nicht, dass diese Links Antworten auf Informatik waren oder dass sie Ihre Antworten waren. Nun, auf jeden Fall wollte ich nur sagen, dass es eine gute Idee sein könnte, die vereinfachten Beweise aufzuschreiben. Ihre verknüpften Antworten scheinen dann der richtige Ort zu sein.
Diskrete Eidechse