Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
---- Algorithmen (http://www.informatikerboard.de/board/board.php?boardid=17)
----- Suche in einem binären Suchbaum (http://www.informatikerboard.de/board/thread.php?threadid=2970)

Geschrieben von Shizmo am 23.04.2016 um 00:51:

  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


Geschrieben von eulerscheZahl am 23.04.2016 um 06:33:

 

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


Geschrieben von Shizmo am 23.04.2016 um 10:36:

 

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


Geschrieben von eulerscheZahl am 23.04.2016 um 10:43:

 

Stimmt, das letzte Beispiel ist auch falsch.


Geschrieben von Shizmo am 23.04.2016 um 10:58:

 

Okay super, vielen Dank!!! Daumen hoch


Forensoftware: Burning Board, entwickelt von WoltLab GmbH