„Algoritmuselmélet - Vizsga, 2013.05.30.” változatai közötti eltérés
| 9. sor: | 9. sor: | ||
}} | }} | ||
===2. Feladat=== | ===2. Feladat (Van megoldás)=== | ||
Adja meg a 2-3 fa definícióját! Adjon felső becslést a fa szintszámára n tárolt elem esetén, állítását bizonyítsa is! | |||
{{Rejtett | {{Rejtett | ||
|mutatott=<big>'''Megoldás'''</big> | |mutatott=<big>'''Megoldás'''</big> | ||
|szöveg= | |szöveg= | ||
'''Adja meg a 2-3 fa definícióját!''' | |||
*Elemeket csak a levelekben tárolunk. | |||
*Az elemek balról jobbra növekvő sorrendben állnak. | |||
*Minden belső csúcsnak 2, vagy 3 fia lehet, se több, se kevesebb. ''(Kivéve, ha csak 1 elemet tárolunk a fában, mert akkor a gyökérnek csak 1 fia van.)'' | |||
*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 elemet (S) tárolunk. | |||
**Ha a csúcsnak 2 fia van, akkor 2 mutatót, és egy elememet tárol. [[File:2_3_2.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 elemet tárol. [[File:2_3_3.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). | |||
'''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. | |||
''Bizonyítás:'' | |||
*<math>log_2n+1\leq m</math> | |||
**Minden belső csúcsnak legalább 2 fia van, így az <math>i.</math> szinten legalább <math>2^{i-1}</math> csúcs van, tehát: <math>2^{m-1} \geq n \Rightarrow m-1 \geq log_2n \Rightarrow m \geq log_2n+1</math> | |||
*<math>m\leq log_3n+1</math> | |||
**Minden belső csúcsnak maximum 3 fia van, így az <math>i.</math> szinten maximum <math>3^{i-1}</math> csúcs van, tehát: <math>3^{m-1} \leq n \Rightarrow m-1 \leq log_3n \Rightarrow m \leq log_3n+1</math> | |||
}} | }} | ||