Heap und fast vollständig ungleich balanciert

Wissenschaft Informatik
#1

Hallo Leute!

ich ärgere mich gerade über einen Satz im Skript. Da steht das die Klasse der fast vollständigen Bäume nicht zu den balancierten Bäumen gehören, da sie zwar die Ausgewogenheitsbedigung erfüllen, jedoch nicht in O(log n) restrukturierbar sind, sondern in O(n) im worst case.
Auf der anderen Seite ist es doch möglich im Heap mit O(log n) einzufügen! Dazu gehört doch auch das Restrukturieren, oder?
Also irgendwas versteh ich hier total falsch, die balancierten Bäume garantieren einfügen in O(log n) und die Heaps auch, warum gehört die Klasse der fast vollständigen Bäume dann nicht zu den balancierten Bäumen?

Hilfe!! :smiley:

beste Grüße

#2

Hallo,

ich ärgere mich gerade über einen Satz im Skript. Da steht das
die Klasse der fast vollständigen Bäume nicht zu den
balancierten Bäumen gehören, da sie zwar die
Ausgewogenheitsbedigung erfüllen, jedoch nicht in O(log n)
restrukturierbar sind, sondern in O(n) im worst case.

du verschweigst irgendeine wichtige Information: Was hat es mit dem „restrukturierbar“ auf sich? Handelt es sich nicht um allgemeine Bäume, sondern vielleicht um geordnete? Ohne weiter raten zu wollen, könnte ich mir vorstellen, dass mit dem genannten Worst Case z.B. das Einfügen von 0 in folgenden geordneten, fast vollständigen Binärbaum gemeint ist:

 4
 2 6
1 3 5

Bei der folgenden Argumentation stimmt deine Logik nicht:

Also irgendwas versteh ich hier total falsch, die balancierten
Bäume garantieren einfügen in O(log n) und die Heaps auch,
warum gehört die Klasse der fast vollständigen Bäume dann
nicht zu den balancierten Bäumen?

Die Heaps sind nicht alle fast vollständigen Bäume! Nur weil ganz bestimmte fast vollständige Bäume (Heaps) Einfügungen in O(log n) unterstützen, gilt das noch lange nicht für alle.

Viele Grüße,

Andreas

#3

Hallo Andreas,

ich danke Dir für die Antwort. Wie ich das nun dank deiner Anwtort verstehe ist, dass es fast vollständige Bäume gibt, die nicht in O(log n) restrukturierbar sind und welche (und dazu gehören wohl die Heaps), die es sind.
Bekomme ich nun einen Baum zu sehen der diese fast vollständige Struktur aufweist, dann kann ich nicht ohne weiteres sagen, dass dieser in O(log n) restrukturierbar ist.
Wenn ich aber weiß das es sich um einen Heap handelt und seine Restrukturierungsmethoden kenne, sowie seine Ordnung, dann weiß ich: ja die Heaps sind in O(log n) restrukturierbar und gehören somit zu der Klasse der balancierten Bäume.
Ich hoffe das ich es somit einigermaßen verstanden habe. Danke für deine / eure Zeit und Interesse!

die Hintergründe nochmal etwas klarer aufgeschrieben:

Klasse der balancierten Bäume:

  • erfüllen die Ausgewogenheitsbedingung (es existiert ein c>0 für alle Bäume der Klasse der balancierten Bäume, für die gilt: die Höhe der Bäume ist maximal c mal log(Anzahl Knoten))

  • erfüllen die Restrukturierungsbedingung (in O(log n) die Ausgewogenheit wieder herstellbar)

Heaps:

  • ist ein fast vollständiger Baum (alle Knoten auf der untersten Ebene sind so weit wie möglich links angeordnet)
  • Ordnung: die Elternknoten haben einen kleineren Wert als ihre Kindsknoten (bei einem MinHeap)

Einfügen in den Heap ist in O(log n) möglich, dabei wird der neue Knoten in die unterste Ebene soweit links wie möglich eingefügt und dann entsprechend seines Gewichts mit seinen Eltern vertauscht, solange bis die Ordnung wieder stimmt.