Forum
 
Fragen
 
Suchen
 
Über Uns
 
 

Suche in einem binären Suchbaum
Neue Frage »

23.04.2016, 00:51 Auf diesen Beitrag antworten »
Shizmo Suche in einem binären Suchbaum

Hallo, ich steh grad auf dem Schlauch:

Zitat:
Angenommen es werden die Zahlen von 1 bis 1000 in einem binären Suchbaum verwaltet. Darin soll die Zahl 363 gesucht werden. Welche der folgenden Sequenzen kann nicht aus dem zuvor beschriebenen Baum beim Suchen entstanden sein? Begründen Sie ihre Antwort.
  • 2, 252, 401, 398, 330, 344, 397, 363
  • 924, 220, 911, 244, 898, 258, 362, 363
  • 2, 399, 387, 219, 266, 382, 381, 278, 363
  • 925, 202, 911, 240, 912, 245, 363
  • 500, 250, 499, 12, 300, 370, 363
  • 935, 278, 347, 621, 299, 392, 358, 363


Hmm, also ich weiß was ein binärer Suchbaum ist, zB Beispiel1, wenn die Zahlen 2, 252, 401, 398, 330, 344, 397, 363 so eingefügt werden und danach die übrigen Zahlen von 1-1000, dann würde das in etwa so ausschauen:

code: 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

 2
  \
  252
    \
    401
    / 
 398
  /
330
   \
  344
     \
    397
     /
   363


So und jetzt noch die übrigen Zahlen von 1-1000.

Die Eigenschaften vom Suchbaum sind nicht verletzt und die Suche kann auch ganz normal stattfinden bis ich zum Element 363 komme.

Der Pseudocode von Baumsuche(x,k) schaut nämlich so aus:
code: 
1:
2:
3:
4:
5:
6:
7:

if x==Nil or k==x.key
   return x

if k<x.kex
   return Baumsuche(x.left,k)
else
   return Baumsuche(x.right,k)

Und irgendwie schaut es bei den anderen Beispielen nicht anders aus.

[latex]\Rightarrow[/latex] Meine Strategie geht nicht auf[latex]\wedge[/latex] irgendwo hab ich einen Denkfehler großes Grinsen

LG
 
 
23.04.2016, 06:33 Auf diesen Beitrag antworten »
eulerscheZahl

code: 
1:

925, 202, 911, 240, 912, 245, 363

von der 911 geht es nach links. Also können nur noch Werte gefunden werden, die kleiner als 911 sind. 912 darf nicht vorkommen.
Das passt auch nicht: 500, 250, 499, 12, 300, 370, 363
23.04.2016, 10:36 Auf diesen Beitrag antworten »
Shizmo

Vielen Dank für deine Antwort.

Also könnte man damit argumentieren, dass wenn es ein Kind ohne Nachfolger (mit Ausnahme der 363) gibt, die Suchsequenz nicht richtig sein kann?

Dann sollte aber das letzte Beispiel auch falsch sein:

code: 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

   935
   /
 278
    \
   347
   /  \
299  621
       /
     392
     /
  358
     \
     363


LG
23.04.2016, 10:43 Auf diesen Beitrag antworten »
eulerscheZahl

Stimmt, das letzte Beispiel ist auch falsch.
 Anzeige
 
23.04.2016, 10:58 Auf diesen Beitrag antworten »
Shizmo

Okay super, vielen Dank!!! Daumen hoch
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »


Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Suche in einem binären Suchbaum

 
© 2005-2019 bei Informatikerboard.de | Archiv, alt, neueste | Kontakt | Jugendschutz | Nutzungsbedingungen