Mi lehet a megoldása ennek a 2 algoritmusos feladatnak?
1. A bináris keresőfa alakja nagyon el tud romlani, egyes ágai túl hosszúra nőhetnek (akár listává torzulhat a fa), így elveszíti a benne történő keresés a hatékonyságát. Erre a problémára tudnak megoldást adni az „önkiegyensúlyozó” bináris keresőfák, például az AVL fák vagy a piros-fekete fák. Érdekes viszont a következő ötlet: ha nagyon elromlik a fa alakja, járjuk be inorder bejárással, írjuk egy tömbbe a csúcsok címeit, majd az így kapott, a csúcsok kulcsai szerint szigorúan monoton növekvően rendezett tömbből építsük fel újra bináris keresőfát úgy, hogy alakja optimális legyen.
2. Mutasd meg, hogy 5 elem rendezéséhez elég 7 összehasonlítás. Lehet ettől jobbat is csinálni?
válasza:Az elsőben a kérdésben van a válasz. Arra értelmetlen a kérdésed. Itt egy példára van szükséged? Mert a fentiek alapján, WIKI-t kellene olvasni vagy 1-2 leírást és megtudod csinálni. Ofc, azért órán is érdemes figyelni. By the way, minden információ az interneten rendelkezésedre áll.
A Második feladatban, szerintem gondolkozz el és vezesd le papíron. Úgy könnyebben megérted. :)
válasza:Az elsoben melyik resz nem megy? A bejaras vagy az optimalis fa felepitese?
Elobbi sima inorder traversal.
Utobbinal van egy rendezett tombod, egy optimalis BST-ben meg ugye 1-nel nem nagyobb a kulonbseg adott node 2 reszfajanak magassaga kozott. Tehat annyi a dolgod, hogy kivalasztod a rendezett tombod kozepso elemet, ez lesz a root, aztan felepited rekurzivan a bal es jobb reszfat, ugyanezen logika alapjan, a gyokertol balra es jobbra elhelyezkedo elemekbol.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!