Keko; binääripuu; linkitetty rakenne; miten löytyy "last"?

epät. koodari

Eli ongelma lyhykäisyydessään:

On olemassa keko, joka on linkitettynä rakenteena toteutettu binääripuu, jolle pitäisi tehdä insert yms. operaatioita.

Millä algoritmilla (myös mikä tahansa ohjelmointikieli/pseudokoodi/linkki kelpaa), miten linkitetystä puurakenteesta löytyy se paikka, jonne seuraava operaatio tehdään?

Eli, miten päivitetään muuttuja "last", joka viittaa viimeisimpään kekoon lisättyyn alkioon? Ja siis ennen kaikkea, millä algoritmilla tuo "last" päivitetään, jos halutaan tietää esim. seuraava paikka, jonne lisäys pitää tehdä?

3

1148

Äänestä

    Vastaukset 3

    Anonyymi (Kirjaudu / Rekisteröidy)
    5000
    • Nimimerkki

      Seuraavan objektin paikkahan riippuu täysin tietorakenteesta johon (ja objektin jonka) haluat tietoja syöttää. Jos käytät jotain järjestettyä puuta, alkio laitetaan puussa oikealle paikalleen, järjestämättömässä linkitetyssä listassa alkoi laitetaan listan viimeiseksi jne... Eli binääripuun tapauksessa sinulla ei voi olla tiedossa mihin seuraava alkoi puussa laitetaan, ennen kuin tiedät mikä alkio syötetään.

      Linkki viimeisimpään alkioon on helppo ylläpitää, mutta siitä ei ole iloa kun halutaan syöttää seuraava arvo. AVL-puu tai puna-musta-puu hauilla netistä löytyy varmasti vinkkiä. Toisaalta esimerkiksi Javassa on valmiina tuommoiset tietorakenteet (java.util.*), jos sinun ei koulua varten tarvitse moisia tehdä uudestaan.

      • epät. koodari

        Keko-rakenne jo itsessään sanelee aika paljon sitä, miten binääripuu pitää rakentaa. Siinä uusi alkio lisätään aina ensin keon viimeiseksi alkioksi ja sitten kuplitaan ylöspäin omalle paikalleen avaimen arvon perusteella.

        Mutta, nou hätä. Ratkaisin jo ongelman ja joo, koulua varten tätä moskaa pitää pähkäillä...

      • taulukkona
        epät. koodari kirjoitti:

        Keko-rakenne jo itsessään sanelee aika paljon sitä, miten binääripuu pitää rakentaa. Siinä uusi alkio lisätään aina ensin keon viimeiseksi alkioksi ja sitten kuplitaan ylöspäin omalle paikalleen avaimen arvon perusteella.

        Mutta, nou hätä. Ratkaisin jo ongelman ja joo, koulua varten tätä moskaa pitää pähkäillä...

        toteutettuna on paljon nopeampi!

    Ketjusta on poistettu 0 sääntöjenvastaista viestiä.

    Takaisin ylös

    Luetuimmat keskustelut

    1. Ampuminen kylpylässä

      Onko vornasen timbe käynyt hiukan kylpemässä vai mikä tämä ampumatapaus on kylpylässä? Tuntuu aika villi meno olevan naa
      Naantali
      60
      1322

    2. Moottoripyöräonnettomuus

      Mopomiitissä tapahtunut onnettomuus ja uutisointi. Ajoradan ylityksen vaarallisuudesta ei mitään uutisointia. Ei myöskää
      Alajärvi
      90
      1017

    3. haluatko lopettaa

      ihan lopullisesti
      Ikävä
      164
      927

    4. Jos oikeasti haluat mies

      Tiedät mitä on tehtävä. Luotan, että etenet jos haluat. En voi tehdä enää mitään kun ei ole numeroasi.
      Ikävä
      105
      864

    5. Uusi ruokapaikka

      Tuleeko Haapavedelle uusi lounaspaikka ,haetaan kokkia? Uusi firma kyseessä
      Haapavesi
      30
      853

    6. Kemijärvellä vesionnettomuus

      Pitkänsillan ja taiteilijanniemen välillä nähty henkilön painuvan veden alle. Mitä on tapahtunut? Onko vesihiisi taas as
      Kemijärvi
      25
      788

    7. Kerro minulle totuus

      Minä haluan kuulla sen nyt. Kenen kanssa sinä olet nykyisin, ja miksi jätit minut? 🐒
      Ikävä
      201
      762

    8. Hautakivien massapoisto aloitettu Härkökankaan vanhalla hautausmaalla kaikessa hiljaisuudessa!

      Suomussalmen seurakunnan kirkkoneuvosto on tehnyt historiansa surullisimman päätöksen hautojen haltuunotosta ja raivauks
      Suomussalmi
      44
      738

    9. Miten sinä voit?

      Kysytkö kukaan sitä sinulta? Olen huomannut, että jos kohtaa empaattisen ihmisen ja hän kysyy noin, saattaa padot murtua
      Ikävä
      93
      707

    10. voi luoja kun uskaltaisin

      laittaa viestiä sinulle...
      Ikävä
      26
      690

    11. Hei, voitko kuunnella

      Voisitko auttaa minua selvittämään asioita? En halua ajaa sinua hulluuteen kanssani, en sitoa sinua, en esittää vaatimu
      Ikävä
      124
      680

    12. VILLISIKALAUMA TULOSSA IISALMEEN

      Yle: Poliisi varoittaa Iisalmen keskustaa lähestyvästä villisika­laumasta Poliisi on pyytänyt Pohjois-Savossa Iisalmessa
      Iisalmi
      43
      616

    13. Miten yrität

      Vielä saada kaivattusi?
      Ikävä
      61
      602

    14. Joku porukka lähtenyt täältä

      Ihmeen hiljainen on palsta nyt. Yleensä tänne tulvii aloituksia yms, mutta nyt on kyllä erikoisen hiljaista.
      Ikävä
      155
      601

    15. Useita poliisiautoja kunnantalolla

      Maijojen kyydissä tuttuja naamoja ja nyt kannetaan arkistolaatikoita autoihin. Nyt se on alkanut. Pidätykset.
      Ähtäri
      12
      585

    16. Jos näkisimme vielä joskus

      ... mihin veisit miut treffeille? 😊
      Ikävä
      85
      548

    17. On todella ikävää

      Todella ikävää, että asiat ovat menneet tällaisiksi. Tämä ei ollut missään vaiheessa tarkoitukseni. Olen tehnyt virheit
      Ikävä
      78
      530

    18. Olipa yllätys

      Kuten hyvin moni tiesi/arvasi että valetta alusta loppuun toi *olemme ystäviä* satu. Instassaan käsi kädessä kuva kertoo
      Kotimaiset julkkisjuorut
      187
      501

    19. Ottanet yhteyttä

      Facebookissa,jos on jotain asiaa.Miehelle! T.M-nainen.
      Ikävä
      55
      497

    20. Tiedätkö ton lähilammen?

      🤔
      Ikävä
      39
      495
    Aihe
    TietosuojaselosteKäyttöehdotEvästeasetuksetSäännöt