binärer Suchbaum < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:19 So 11.01.2009 | | Autor: | Klemme |
| Aufgabe | | In einem binären Suchbaum T befinde sich der Schlüssel x in einem Knoten mit zwei nichtleeren Unterbäumen. Zeigen Sie, dass sich der Nachfolger von x in einem Knoten mit leerem linken Unterbaum befindet. |
Hallo,
ich habe bei dieser Aufgabe folgendes Problem: Ich soll etwas zeigen, von dem ich nicht glaube dass es überhaupt stimmt. Mit dem Nachfolger von x ist doch nur der nächste Schlüssel gemeint. Und der kann doch wieder Nachfolger haben (auch im linken Teilbaum). Es wäre nett, wenn mir jemand erklären könnte, was genau ich falsch verstanden habe. Ist mit dem Nachfolger doch etwas anderes gemeint?
LG
Klemme
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:38 Mo 12.01.2009 | | Autor: | bazzzty |
> In einem binären Suchbaum T befinde sich der Schlüssel x in
> einem Knoten mit zwei nichtleeren Unterbäumen. Zeigen Sie,
> dass sich der Nachfolger von x in einem Knoten mit leerem
> linken Unterbaum befindet.
> Hallo,
>
> ich habe bei dieser Aufgabe folgendes Problem: Ich soll
> etwas zeigen, von dem ich nicht glaube dass es überhaupt
> stimmt. Mit dem Nachfolger von x ist doch nur der nächste
> Schlüssel gemeint. Und der kann doch wieder Nachfolger
> haben (auch im linken Teilbaum). Es wäre nett, wenn mir
> jemand erklären könnte, was genau ich falsch verstanden
> habe. Ist mit dem Nachfolger doch etwas anderes gemeint?
Hallo Klemme,
die Aufgabe stimmt schon so, aber vielleicht hast Du wirklich ein falsches Bild vom Nachfolger von $x$. In einem binären Suchbaum gilt für jeden Knoten mit einem Schlüssel $x$, dass der linke Teilbaum (wenn vorhanden) nur kleinere, der rechte Teilbaum (wenn vorhanden) nur größere Schlüssel enthält. Der Nachfolger von $x$ ist der nächstgrößere Schlüssel im Baum.
Wenn nun der Knoten mit Schlüssel $x$ einen rechten Teilbaum hat, warum kann dann der Nachfolger von $x$ keinen linken Teilbaum haben?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:22 Mo 12.01.2009 | | Autor: | Klemme |
Ach so. Alle Schlüssel, die kleiner x sind und damit auch kleiner als der Nachfolger sind im linken Teilbaum von x. Im rechten Teilbaum befinden sich nur noch Schlüssel größer x und größer dem Nachfolger von x. Das heißt, dass die nächsten (größeren) Schlüssel sich im rechten Teilbaum des Nachfolgers befinden müssen.
Hab ich das jetzt richtig verstanden? (Das mit dem größer und kleiner hatte ich schon gewusst, aber den Nachfolger habe ich tatsächlich falsch verstanden)
mfG
Klemme
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:57 Mo 12.01.2009 | | Autor: | bazzzty |
> Ach so. Alle Schlüssel, die kleiner x sind und damit auch
> kleiner als der Nachfolger sind im linken Teilbaum von x.
> Im rechten Teilbaum befinden sich nur noch Schlüssel größer
> x und größer dem Nachfolger von x. Das heißt, dass die
> nächsten (größeren) Schlüssel sich im rechten Teilbaum des
> Nachfolgers befinden müssen.
>
> Hab ich das jetzt richtig verstanden? (Das mit dem größer
> und kleiner hatte ich schon gewusst, aber den Nachfolger
> habe ich tatsächlich falsch verstanden)
Ja, genau. Der Nachfolger von $x$ ist auf jeden Fall im rechten Teilbaum, und alle Schlüssel in diesem Teilbaum sind größer als $x$. Gäbe es noch einen linken Teilbaum am Nachfolger, dann müßte zwischen $x$ und dem Nachfolger noch ein Schlüssel liegen. Das widerspricht aber der Definition des Nachfolgers.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:41 Mo 12.01.2009 | | Autor: | Klemme |
Danke noch mal für die schnelle Hilfe
LG
Klemme
|
|
|
|
