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

@@ 102. sor: / 102. sor: @@
 }}
-===8. Feladat===
+===8. Feladat (Van megoldás)===
-TODO
+Bizonyítsa be, hogy egy piros-fekete fában egy levél testvére vagy levél, vagy piros csúcs!
 {{Rejtett
 |mutatott=<big>'''Megoldás'''</big>
 |szöveg=
-TODO
+*Összesen 5 felállás lehet: [[File:algel_pzh_2012tavasz_8_1.png|400px]]
+**Ebből az 1. és a 4. jó is ''(a 4. persze csak akkor, ha X az nem a főgyökér)''.
+**A 3. - kis módosítással - látszik, hogy szintén fenn állhat gond nélkül: [[File:algel_pzh_2012tavasz_8_2.png|100px]]
+**Egyedül a 2. és az 5. problémás. Ezek viszont rosszak is, hiszen mindkét esetben elmondható, hogy X-nek a fekete magassága jobbra 1, balra viszont legalább 2, mert az Y csúcsnak legalább 1-1 levél fia van. Tehát belső csúcsnál ilyen állapot nem állhat fent.
+*Az első 2 esetben azt bizonyítottuk, hogy levél testvére lehet levél, vagy piros csúcs.
+*A 3. esetben pedig azt, hogy nem lehet fekete csúcs a levél testvére.
+*Így be is bizonyítottuk, hogy levél testvére CSAK levél, vagy piros csúcs lehet.
 }}
 [[Kategória:Infoalap]]