„Algoritmuselmélet - PZH, 2013.04.24.” változatai közötti eltérés
| 34. sor: | 34. sor: | ||
*Minden további szinten az a feladatunk, hogy megnézzük az adott csúcs (x) bal, és jobb fiát <math>(JOBB(x), BAL(x))</math>. | *Minden további szinten az a feladatunk, hogy megnézzük az adott csúcs (x) bal, és jobb fiát <math>(JOBB(x), BAL(x))</math>. | ||
**Megnézzük, hogy nagyobbak-e, mint x, majd megnézzük, hogy kupac tulajdonsággal bírnak-e: | **Megnézzük, hogy nagyobbak-e, mint x, majd megnézzük, hogy kupac tulajdonsággal bírnak-e: | ||
***Ha <math>BAL(x),JOBB(x) > x;BAL(x).B=JOBB(x).B=IGAZ\Rightarrow\Rightarrow x.M := BAL(x).M+1, x.B := IGAZ</math> majd a változónkba belerakjuk a csúcsot. ''Vagyis ha mindkettő nagyobb, és mindkettő kupac tulajdonsággal bír, akkor a csúcs részfa magassága 1-gyel nagyobb lesz, mint az egyik (bal, vagy jobb) | ***Ha <math>BAL(x),JOBB(x) > x;BAL(x).B=JOBB(x).B=IGAZ\Rightarrow\Rightarrow x.M := BAL(x).M+1, x.B := IGAZ</math> majd a változónkba belerakjuk a csúcsot. ''Vagyis ha mindkettő nagyobb, és mindkettő kupac tulajdonsággal bír, akkor a csúcs részfa magassága 1-gyel nagyobb lesz, mint az egyik (bal, vagy jobb) fia magassága, és kupac tulajdonságú lesz.'' | ||
***Ha <math>BAL(x) < x</math> VAGY <math>JOBB(x) < x</math> VAGY <math>BAL(x).B=HAMIS</math> VAGY <math>JOBB(x).B=HAMIS\Rightarrow\Rightarrow x.M := BAL(x).M+1, x.B := HAMIS</math>. ''Vagyis ha bármelyik feltétel nem teljesül (valamelyik fia kisebb, avagy valamelyik gyerekére nem igaz, hogy kupac tulajdonságú), akkor maga a csúcs sem lehet már kupac tulajdonságú (itt a magasságot nem is kéne beállítani, de...hát miért is ne).'' | ***Ha <math>BAL(x) < x</math> VAGY <math>JOBB(x) < x</math> VAGY <math>BAL(x).B=HAMIS</math> VAGY <math>JOBB(x).B=HAMIS\Rightarrow\Rightarrow x.M := BAL(x).M+1, x.B := HAMIS</math>. ''Vagyis ha bármelyik feltétel nem teljesül (valamelyik fia kisebb, avagy valamelyik gyerekére nem igaz, hogy kupac tulajdonságú), akkor maga a csúcs sem lehet már kupac tulajdonságú (itt a magasságot nem is kéne beállítani, de...hát miért is ne).'' | ||
Mivel minden csúcsot csak egyszer látogatunk meg, így <math>O(n)</math> lépésben megyünk végig a gráfon. | Mivel minden csúcsot csak egyszer látogatunk meg, így <math>O(n)</math> lépésben megyünk végig a gráfon. | ||