„Algoritmuselmélet - Vizsga, 2013.05.30.” változatai közötti eltérés

(4 közbenső módosítás, amit 2 másik szerkesztő végzett, nincs mutatva)

37. sor:

*A fa levelei a gyökértől egyenlő távolságra vannak (vagyis a levelek 1 szinten vannak).

*A belső csúcsokban mutatókat (M) és 1, vagy 2 kulcsot (S) tárolunk.

**Ha a csúcsnak 2 fia van, akkor 2 mutatót, és egy kulcsot tárol. [[File:~~2_3_2~~.png|300px]]

**Ha a csúcsnak 2 fia van, akkor 2 mutatót, és egy kulcsot tárol. [[File:Algel vizsga 2013tavasz V1 2 2fia.png|300px]]

***A bal részfában az elemek kisebbek, mint S1.

***A jobb részfában az elemek nagyobb-egyenlőek, mint S1 (vagyis az 1. elem S1).

**Ha a csúcsnak 3 fia van, akkor 3 mutatót, és 2 kulcsot tárol. [[File:~~2_3_3~~.png|400px]]

**Ha a csúcsnak 3 fia van, akkor 3 mutatót, és 2 kulcsot tárol. [[File:Algel_vizsga_2013tavasz_V1_2_3fia.png|400px]]

***A bal részfában az elemek kisebbek, mint S1.

***A középső részfában az elemek nagyobb-egyenlőek, mint S1 (vagyis az 1. elem S1), de kisebbek, mint S2.

***A jobb részfában az elemek nagyobb-egyenlőek, mint S2 (vagyis az 1. elem S2).

~~:::::::::::::::::[[File:2_3_pelda.PNG|400px]]~~

'''Adjon felső becslést a fa szintszámára n tárolt elem esetén, állítását bizonyítsa is!'''

<math>log_2n+1\leq m \leq log_3n+1</math>, ahol <math>m</math> a fa szintszáma.

$$$ Ez nem pont fordítva van a dián? $$$

''Bizonyítás:''

@@ 37. sor: / 37. sor: @@
 *A fa levelei a gyökértől egyenlő távolságra vannak (vagyis a levelek 1 szinten vannak).
 *A belső csúcsokban mutatókat (M) és 1, vagy 2 kulcsot (S) tárolunk.
-**Ha a csúcsnak 2 fia van, akkor 2 mutatót, és egy kulcsot tárol. [[File:2_3_2.png|300px]]
+**Ha a csúcsnak 2 fia van, akkor 2 mutatót, és egy kulcsot tárol. [[File:Algel vizsga 2013tavasz V1 2 2fia.png|300px]]
 ***A bal részfában az elemek kisebbek, mint S1.
 ***A jobb részfában az elemek nagyobb-egyenlőek, mint S1 (vagyis az 1. elem S1).
-**Ha a csúcsnak 3 fia van, akkor 3 mutatót, és 2 kulcsot tárol. [[File:2_3_3.png|400px]]
+**Ha a csúcsnak 3 fia van, akkor 3 mutatót, és 2 kulcsot tárol. [[File:Algel_vizsga_2013tavasz_V1_2_3fia.png|400px]]
 ***A bal részfában az elemek kisebbek, mint S1.
 ***A középső részfában az elemek nagyobb-egyenlőek, mint S1 (vagyis az 1. elem S1), de kisebbek, mint S2.
 ***A jobb részfában az elemek nagyobb-egyenlőek, mint S2 (vagyis az 1. elem S2).
-:::::::::::::::::[[File:2_3_pelda.PNG|400px]]
 '''Adjon felső becslést a fa szintszámára n tárolt elem esetén, állítását bizonyítsa is!'''
 <math>log_2n+1\leq m \leq log_3n+1</math>, ahol <math>m</math> a fa szintszáma.
+$$$ Ez nem pont fordítva van a dián? $$$
 ''Bizonyítás:''