Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » RS-Baum längster Pfad maximal doppel wie kürzester

RS-Baum längster Pfad maximal doppel wie kürzester

Universität / Fachhochschule

Tags: Baum, Höhe, Induktion

Nekks aktiv_icon

11:18 Uhr, 01.10.2016

Guten Tag,

meine Aufgabe ist es zu zeigen, dass der längste Pfad eines Rot-Schwarz-Baumes maximal doppelt so lang ist, wie der kürzeste.

Man kann beweisen, dass die Höhe eines RS-Baumes maximal

2 \cdot {log}_{2} (n + 1)

ist (wenn man von der Mindestanzahl schwarzer Knoten ausgeht und entsprechend umformt).
Geht man nun von einem vollständig gefüllten, binären Baum aus, so ergibt sich für

n = 2^{h + 1} - 1

. Durch Umformen würde man erhalten:

h = {log}_{2} (n + 1) - 1

.

Sagt man nun, dass ein Unterbaum eines Knotens

x

ein vollständig gefüllter binärer Baum ist und der andere die Mindestzahl an Elementen besitzt, dann würde nun gelten:

1) h_{1} = h + 1 = {log}_{2} (n + 1)

(aufgrund der Wurzel nimmt die Höhe um 1 zu, der kürzeste Pfad wäre nun

{log}_{2} (n + 1))

2) h_{2} = h + 1 = 2 \cdot {log}_{2} (n + 1) + 1

Daran würde man erkennen, dass der längste Pfad doppelt so lang wäre, wie der kürzeste und für

n

gelte:

n = (2^{h} - 1) + (2^{\frac{h - 1}{2}} - 1) + 1 = 2^{h} + 2^{\frac{h - 1}{2}} - 1,

wenn

h

die Höhe des gesamten Baumes wäre.
Aber damit habe ich doch nichts bewiesen, oder?

lieben Gruß

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

ledum aktiv_icon

15:07 Uhr, 02.10.2016

Hallo
den Beweis findest du in wiki unter Rot-Schwarz-Baum
de.wikipedia.org/wiki/Rot-Schwarz-Baum
Gruß ledum

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1325439

1325220

	Status: nicht eingeloggt	Noch nicht registriert?