 Suche in einem binären Suchbaum |
Shizmo
Tripel-As
Dabei seit: 16.10.2015
Beiträge: 174
 |
|
| 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]](http://www.matheboard.de/latex2png/latex2png.php?\Rightarrow) Meine Strategie geht nicht auf![[latex]\wedge[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\wedge) irgendwo hab ich einen Denkfehler 
LG
|
|
23.04.2016 00:51 |
|
|
|
|
| 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
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
23.04.2016 06:33 |
|
|
Shizmo
Tripel-As
Dabei seit: 16.10.2015
Beiträge: 174
|
|
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:36 |
|
|
Shizmo
Tripel-As
Dabei seit: 16.10.2015
Beiträge: 174
|
|
Okay super, vielen Dank!!! 
|
|
|
23.04.2016 10:58 |
|
|
|
