„Algoritmuselmélet 2010.11.19. PZH megoldásai” változatai közötti eltérés
| 77. sor: | 77. sor: | ||
}} | }} | ||
===7. Feladat=== | ===7. Feladat (Van megoldás)=== | ||
Egy piros-fekete fa gyökerének mindkét gyereke fekete. A gyökér baloldali részfájában 14, a jobboldali részfájában 63 elemet tárolunk. Mennyi lehet a fa fekete-magassága? | |||
{{Rejtett | {{Rejtett | ||
|mutatott=<big>'''Megoldás'''</big> | |mutatott=<big>'''Megoldás'''</big> | ||
|szöveg= | |szöveg= | ||
*Először vizsgáljuk a jobboldali részfát: | |||
**Tudjuk, hogy <math> n \leq 2^m-1 \Rightarrow 63 \leq 2^m-1 \Rightarrow m \geq 6 </math>, vagyis a jobb oldali részfa magassága legalább 6.<br><br> | |||
**Továbbá <math> fm \geq \frac{m}{2} \Rightarrow fm \geq 3 </math> <br><br> | |||
*Most nézzük a baloldali részfát: | |||
**Ismert, hogy <math> b_v \geq 2^{fm(v)}-1 \Rightarrow 14 \geq 2^{fm(v)}-1 \Rightarrow fm \leq 3.907 \Rightarrow \Rightarrow fm < 4 </math> | |||
*A 2 korlátot összevetve jön ki, hogy a bal és jobb részfa esetén <math> fm = 3.</math> | |||
*Emiatt az eredeti fában pedig <math> fm = 4.</math> | |||
}} | }} | ||