Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

5.9. Feladatok

5.9. Feladatok

  1. Üres piros-fekete fába szigorúan monoton növekedő kulcsok sorozatát szúrjuk be egymás után. Hány kulcs kerül összesen beszúrásra, mire a második forgatás megtörténik (a forgatást előidéző kulcsot is beszámítjuk)? Mennyi lesz ekkor a gyökér fekete magassága?

  2. A 250, 265, 270, 260, 150 kulcsokat a megadott sorrendben szúrjuk be bináris kereső fába üres fából kiindulva! Ezután járjuk be a fát a rekurzív inorder bejárási algoritmussal a gyökérből indulva. A bejárás során alkalmazott művelet a kulcs kiírása. Mi lesz a harmadik kiírt kulcs? Hányszor hívja meg az algoritmus saját magát?

  3. Bináris keresőfába szúrjuk be az alábbi kulcsokat a felsorolásuk sorrendjében üres fával indulva, majd töröljük a gyökérelemet! 500, 250, 800, 700, 120, 300, 750, 900, 850, 780, 230, 210, 240. Melyik kulcs lett az új gyökér és hány mutatót kellett megváltoztatni a törlés során? Hány kulcs-összehasonlítás volt a fa feltöltése során?