„Algoritmuselmélet - Vizsga, 2013.05.30.” változatai közötti eltérés
aNincs szerkesztési összefoglaló |
|||
| (2 közbenső módosítás, amit 2 másik szerkesztő végzett, nincs mutatva) | |||
| 37. sor: | 37. sor: | ||
*A fa levelei a gyökértől egyenlő távolságra vannak (vagyis a levelek 1 szinten vannak). | *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. | *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: | **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 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). | ***A jobb részfában az elemek nagyobb-egyenlőek, mint S1 (vagyis az 1. elem S1). | ||
| 44. sor: | 44. sor: | ||
***A középső részfában az elemek nagyobb-egyenlőek, mint S1 (vagyis az 1. elem S1), de kisebbek, mint S2. | ***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). | ***A jobb részfában az elemek nagyobb-egyenlőek, mint S2 (vagyis az 1. elem S2). | ||
'''Adjon felső becslést a fa szintszámára n tárolt elem esetén, állítását bizonyítsa is!''' | '''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. | <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:'' | ''Bizonyítás:'' | ||