1. Welt
  2. Argumentationen
  3. #1462
Alexander Fufaev

Anzahl unterschiedlicher Heaps der Höhe h

aus dem Bereich: Argumentationen
Optionen

    Das Ziel ist es, herauszufinen, wie viele unterschiedliche Realisierungen eines vollständig besetzten Heaps der Höhe \(h\) es gibt. Eigenschaft eines vollständig besetzten Heaps: Ein vollständig besetzter Heap (Binärbaum) kann bei der Höhe \(h\), mit \(h = \{1,2,3,4...\}\), maximal \(n = 2^{h-1}\) Blätter und minimal 1 Blatt haben.

    #1 Wie viele Blätter dürfen maximal bei einem vollständig besetzten Heap entfernt werden?
    Nach der obigen Eigenschaft dürfen bei einer Höhe \(h\) des Baumes maximal \(n-1 = 2^{h-1}-1\) Blätter entfernt werden (Kombinatorik), damit mindestens 1 Blatt übrig bleibt.

    #2 Wie viele Möglichkeiten \(p\) gibt es, \(k\) Elemente aus \(n\) Elementen herauszunehmen?
    Die Kombinatorik beantwortet uns diese Frage. Das sind \[ C(n;k) = \frac{n!}{k! \, (n-k)!} \] Möglichkeiten, wobei \(C\) der Binomialkoeffizient ist. Nach #2 ist \(n = 2^{h-1}\). Und \(k\) ist die Zahl der entfernten Blätter.

    #3 Wie viele Möglichkeiten \(\Sigma\) insgesamt gibt es, \(k=0\), \(k=1\), ... , \(k=n-1\) Elemente aus \(n\) Elementen herauszunehmen?
    Das ist mit #2 die Summe der einzelnen Binomialkoeffizienten: \[ \Sigma = C(n;0) + C(n;1) + ... + C(n;n-1) = \underset{k=0}{\overset{n-1}{\boxed{+}}} \, C(n;k) \]

    Es kann gezeigt werden, dass die Summe der Binomialkoeffizienten folgendermaßen geschrieben werden kann: \[ \Sigma = \underset{k=0}{\overset{n-1}{\boxed{+}}} \, C(n;k) = 2^n -1 \]

    Mit \(n = 2^{h-1}\) und \(n-1 = 2^{h-1} - 1\) gibt es bei einem Heap der Höhe \(h\) folgende Anzahl an möglichen Realisierungen:

    Anzahl an Heaps \[ \Sigma = 2^{2^{h-1}} - 1 \]
    Beispiel Es gibt \[ \Sigma = 2^{2^{4-1}} - 1 = 255 \] unterschiedliche vollständig besetzte Heaps der Höhe \(h=4\).
    Weltkarte
    Verwalten
    Profil
    Die Stimme fragt...
    Wie erlange ich den Zugang?

    Um das Portal von Ak'tazun betreten zu können, musst Du die rote Pille schlucken. Nachdem Du durch das Portal gegangen bist, gelangst Du in die Matrix, wo Du beispielsweise folgendes tun kannst:

    • Inhalte hinzufügen & verwalten
    • Illustrationen ohne Copyrightzeichen herunterladen
    • Einige Inhalte kommentieren
    • Mittels Kommunikator RT2000 chatten
    • Telegram-Gruppe beitreten
    Bist Du dabei?
    Ja, bin dabei!
    Portale in die anderen Welten

    Reise zu den sicheren anderen Welten des Internets, um nach dem Wissen zu suchen. Findest Du eine Welt besonders interessant, dann kannst Du in der Universaldenkerwelt ein Portal zu dieser Welt erbauen, um den anderen Besuchern den schnellen Zugang dazu zu gewährleisten.

    Portalraum betreten
    Kommunikator
    ONLINE 5
    Gäste online: 5
    Denker online: 0
    Der Kommunikator RT2000 funktioniert nur innerhalb der Matrix!
    Ich will in die Matrix!Mayday! Kontakt aufnehmen.