Next: About this document ...
Megoldások a harmadik óra pótgyakorlatához
1. Vegyük azt a csúcsot a fában, amely az m és az n pontok
legalacsonyabban levő közös őse. Ha ez a pont nem az m és nem is az
n, akkor az m és az n minden bejárásnál ugyanabban a
sorrendben íródik ki, vagyis ebben az esetben a feladatbeli
helyzet nem áll elő.
A maradék négy eset (ki kinek milyen oldali részfájában van)
végignézésével látható, hogy minden X,Y pár esetén eldönthető,
hogy m őse-e n-nek.
2. A teljes feladatsorban szerepel a megoldás a Keresőfa 12. feladatnál.
3. A teljes feladatsorban szerepel a megoldás a Keresőfa 23. feladatnál.
4. A teljes feladatsorban szerepel a megoldás a Keresőfa 6. feladatnál.
5. A teljes feladatsorban szerepel a megoldás a Keresőfa 17. feladatnál.
6. Ha van egy ilyen fánk, abból a csúcsokat preorder bejárással kiolvasva
rendezetten kapjuk őket. Azaz egy ilyen fából O(n) lépésben
rendezetten kapjuk az elemeket. Ha tudnának ilyen fát találni
-ben, azaz -nél lényegében gyorsabban,
akkor rendezni is tudnánk ilyen gyorsan, azt meg tudjuk, hogy nem lehet.
Judit Csima
1999-11-10