2,4 Baum Frage

[Screen]

Kurze Frage:

Ein 2,4-Baum ( in der Graphentheorie) ist so definiert ,dass er zwischen 2 und 4 Blätter pro inneren Knoten haben darf.
Was würde passieren,wenn man 2 bis 5 Blätter pro Knoten zuließe? Oder 2 bis 7 ?


Ich nehme an, dass die Höhe sich verändert.

Dazu findet man leider nichts im Net ;/

 

[AquaBall]

Logisch ändert sich die Höhe.

Hast du noch ne andere Frage dazu?

 

[Screen]

Logisch ändert sich die Höhe.

Hast du noch ne andere Frage dazu?

Du hast die Frage nicht gelesen.

Die 2,4 Bäume sind eine Datenstruktur , man verwendet keine 2,5 oder 2,7 Bäume. Die Frage ist hier : Wieso ? Was wirkt sich negativ aus ,wenn man mehr als 2 bis 4 Blätter pro Knoten zulässt.

 

[AquaBall]

Warum sollte man die nicht verwenden?

Ich glaub ich habe die Frage schon gelesen, aber vielleicht hab ich deine Lücke nicht verstanden.

Natürlich ist ein reiner Binärbaum am schnellsten durchsucht. Hat aber auch den größten overhead an Datenstruktur.

Eine rein lineare Liste hat den geringsten overhead, aber den maximalen Suchaufwand.
Suchaufwand: O(n), SpeicherPlatz=n

Ein 2-4 Baum ist ein guter Kompromiss: schnelle Suchzeiten, relativ geringer Overhead.
Suchaufwand: O(log n), SpeicherPlatz=2n

Wenn du einen 2-5 machen willst geht das natürlich problemlos, kann also sehr wohl "verwendet werden".
Nur ist halt das Handling dann in Baumhöhe, Suchzeit, VerwaltungsOverhead nicht mehr so günstig.
Und wenn du einen Baum x-ter Ordnung machst, aber weniger als x Blätter, dann bist du halt wieder bei der sequentiellen Liste.

Rein für die Ordnung aus binären Gründen ist es halt wieder günstiger einen 2-8 Baum, statt einen 2-7 Baum zu verwenden.
Deshalb sind 2-5-Bäume und 2-7-Bäume nicht üblich aber sehr wohl machbar.

Ist damit die Frage besser beantwortet?

 

[greatergood]

@AquaBall,

ich bin mir nicht sicher, was du damit meinst, wenn du sagst, ein (2, 5) Baum hätte Nachteiliges Handling in Baumhöhe, Suchzeit, ...etc. Das ist alles unbegründet.

@Topic,

ich meine, dass wenn du einen (2, 5) Baum, oder höher (2, k) Baum für k > 4 hast, dann artet dein baum sozusagen zu einer Liste aus...

nehme an du hast einen (2, 1000) Baum und das mit 1000 Elementen, dann würdest du ohne schlaueren Suchalgorithmus erstmal eine Laufzeit von O (k) zum finden eines Eintrages benötigen, weil alle Schlüssel in einem Knoten stehen. Aber diese Angabe ohne Gewähr... weil wie gesagt, der (2, 4) [oder (2, k)] Baum hat auch die Eigenschafft, dass die Eelemente sortiert sind... man könnte also ne Binärsuche starten, dann wärs vllt O (log k)

 

[AquaBall]

ich bin mir nicht sicher, was du damit meinst, wenn du sagst, ein (2, 5) Baum hätte Nachteiliges Handling in Baumhöhe, Suchzeit, ...etc. Das ist alles unbegründet.

Für 5 Blätter in einem Knoten muss ich (nachdem(!) ich durch den Baum geklettert bin!) im worst case 3 Suchzugriffe machen, gleichviel wie für 8 Blätter.
Deshalb ist 5 ungünstig.

Und andererseitshab ich aber bei 2-8 Suchaufwand: O(log 2n), SpeicherPlatz=2n
Deshalb ist 2-4 ein guter Kompromiss. (besser als lineare Liste)

 

[hüteüberhüte]

Ich kann dem, was AquaBall schreibt, auch nicht so ganz folgen...

Der benötige Speicherbedarf ändert sich sich doch nicht. Listen und Bäume haben den gleichen Speicherbedarf, lediglich die Höhe des "speziellen" Baums unterscheidet sich von der Höhe eines Binärbaums.

Dann muss auch noch unterschieden werden, ob der Baum sortiert ist oder nicht.

Eine unsortierte Liste kann in O(n) durchsucht werden, ein Binärbaum (unsortiert) ebenfalls. Eine sortierte Liste wird ebenfalls in O(n) durchsucht. Ein sortierter Binärbaum in O(log(n)) => Wenn sich dieser "spezielle" Baum sortieren ließe, dann würde die Suche irgendwas zwischen log(n) und n benötigen.

Ein Baum mit jeweils 4 Knoten hätte die Höhe log_4 n. Weiß nicht, ob das einen Vorteil darstellt...