G 5.2 - Ausgeglichenheit vs. Fastvollständigkeit

mb_w
Neuling
Neuling
Beiträge: 9
Registriert: 29. Sep 2008 15:41

G 5.2 - Ausgeglichenheit vs. Fastvollständigkeit

Beitrag von mb_w »

Hallo,

in der Aufgab 5.2 soll man verschiedene Bäume nach gegebenen Kriterien zeichne. Mir wird dabei aber der Unterschied zwischen ausgeglichenem und fast vollständigem Baum nicht klar.

Ich danke für jede Hilfe!

Grüße
Michael

mister_tt
Kernelcompilierer
Kernelcompilierer
Beiträge: 502
Registriert: 29. Sep 2008 15:54

Re: G 5.2 - Ausgeglichenheit vs. Fastvollständigkeit

Beitrag von mister_tt »

Moin moin,

Die sind natürlich ähnlich. Beide Definitionen fordern, dass es ein \(k \geq 0\) gibt, sodass jedes Blatt sich auf Stufe k oder \(k + 1\) befindet und jeder Knoten auf Stufe kleiner k Grad 2 hat.
Der Unterschied ist, dass ein fast vollständiger Baum aussieht wie auf Folie 7-20 links unten... D.h. wenn du dir mit den Definitionen oben die Stufe \(k + 1\) von links nach rechts anschaust, dürfen dir keine Lücken auffallen. Auf Stufe \(k + 1\) gibt es also einen Knoten, sodass alle Knoten links von diesem existieren und alle Knoten rechts von diesem "frei" sind.
Bei einem ausgeglichenen Baum hingegen dürfen auf Stufe \(k + 1\) ganz links ein paar Knoten "fehlen" und weiter rechts dürfen trotzdem welche vorkommen...

Hoffe, das war einigermaßen verständlich...
Grüße,
Simon

daniel_b
Computerversteher
Computerversteher
Beiträge: 363
Registriert: 15. Okt 2008 16:23

Re: G 5.2 - Ausgeglichenheit vs. Fastvollständigkeit

Beitrag von daniel_b »

Nicht-informatisch gesprochen ist der Unterschied nur der, welche Knoten auf der untersten Ebene fehlen dürfen:

- Beim ausgeglichenen Baum kannst du beliebige Knoten aus der untersten Reihe wegnehmen, es bleibt ausgeglichen
- um "fast vollständig" beizubehalten, darfst du auch Knoten entfernen, die unterste Reihe aber nur "von rechts her" abbauen

Und bei beiden Definitionen ist natürlich Vorraussetzung, dass alles oberhalb vollständig ist.

mb_w
Neuling
Neuling
Beiträge: 9
Registriert: 29. Sep 2008 15:41

Re: G 5.2 - Ausgeglichenheit vs. Fastvollständigkeit

Beitrag von mb_w »

Jetzt ists klar geworden. Danke!

Grüße
Michael

Antworten

Zurück zu „Archiv“