Sling (köysi, johto) on tietorakenne, jonka avulla voit tehokkaasti tallentaa ja käsitellä pitkiä merkkijonoja, kuten tekstiä. Tarjoaa pitkän merkkijonon tallennuksen puuna, joka koostuu pienistä osamerkkijonoista. Se on kätevä tekstitiedostojen tallentamiseen ja käsittelyyn ja tarjoaa tehokkaan suorituksen tekstieditorille tyypillisistä toiminnoista: lisäys, poistaminen, peruuttaminen (satunnaiskäyttö) [1] .
Sling on binääripuu, jossa jokainen lehti (solmu ilman lapsia) sisältää merkkijonon (tekstin osamerkkijono) ja pituuden (paino) ja jokainen ei-lehtipuusolmu sisältää vasemman alipuunsa lehtien pituuden. . Solmu, jossa on kaksi lasta, jakaa koko merkkijonon kahteen osaan, joista ensimmäinen osa on tallennettu vasemmalle alipuulle, toinen - oikealle, itse solmun paino on yhtä suuri kuin ensimmäisen osan pituus. Perustoimintojen osalta oletetaan, että merkkijonoja ei muokata tuhoamattomalla tavalla, mikä mahdollistaa kopioinnin kirjoittamisen yhteydessä. Lehtisolmut toteutetaan yleensä vakiopituisina merkkijonoina viitemäärällä, kun se nollataan, muisti vapautuu. Myös kehittyneitä jätteenkeräystekniikoita voidaan käyttää.
Seuraavissa määritelmissä N on hihnan pituus.
Tämä toiminto voidaan suorittaa käyttämällä Split()ja kahta toimintoa Concat().
Katsoaksemme i :ntä merkkiä aloitamme rekursiivisen haun juuresta alkaen:
funktioindeksi ( RopeNode node , kokonaisluku i ) jos solmu . _ paino <= i ja olemassa ( solmu . oikea ) sitten palauttaa indeksi ( solmu . oikea , i - solmu . paino ) loppu jos olemassa ( solmu . vasen ) niin palauta indeksi ( solmu . vasen , i ) end paluusolmu . _ merkkijonon [ i ] loppuKatso esimerkiksi kuvaa 2.1 löytääksesi merkin sijainnista i=10, aloitamme juuresta (A), meillä on, että sen paino 22 on suurempi kuin 10, joten menemme alas vasemmalle (B). Tässä on, että 9 on pienempi kuin 10, vähennä 9 10:stä (saa i=1) ja siirry oikeaan lapsisolmuun (D). Meillä on 6 suurempi kuin 1 ja siirrytään vasemmalle lapselle (G). Tässä 2 on suurempi kuin 1, menemme alas vasemmalle (J). Ja lopuksi, 2 on suurempi kuin 1, mutta koska tämä on lehtisolmu, sillä ei ole lapsia ja viittaamme yksinkertaisesti merkkijonon "na" (eli "a") solmuun tallennettuun indeksiin 1, joka olla vastaus.
Ketjutus tehdään luomalla uusi juuri, jossa lapset vasen = S1 ja oikea = S2 , vakioajassa. Pääsolmun painoksi asetetaan vasemman lapsen S 1 pituus , joka voi kestää O(log N) , jos puu on tasapainossa.
Useimmat nostotoimenpiteet edellyttävät puun tasapainottamista, kiinnityksen jälkeen puu saattaa olla tarpeen tasapainottaa.
Kaksi tapausta on mahdollista:
Toinen tapaus pelkistetään ensimmäiseksi katkaisemalla merkkijono katkaisupisteessä ja luomalla kaksi uutta lehtisolmua ja luomalla niille sitten uusi pääsolmu.
Esimerkiksi kuvan 2.3 22-merkkisen hihnan jakamiseksi kahdeksi osaksi, joiden pituus on 11, pyydämme 12. merkkiä määrittämään K -solmun alimmalla tasolla. Poista linkki K :n ja G :n välillä . Siirry pääryhmään G ja vähennä K :n paino D :n painosta . Kiipeä puuhun ja poista kaikki oikeat alipuulinkit, jotka sisältävät merkkejä 11. merkin jälkeen vähentämällä paino K niiden pääsolmuista (tässä tapauksessa vain D ja A ). Lopuksi rivistetään äskettäin orvoiksi jääneet solmut K ja H luomalla niille uusi emosolmu P , jonka paino on yhtä suuri kuin vasemman alisolmun K pituus .
Useimmat nostotoimenpiteet edellyttävät puun tasapainottamista, merkinnän jälkeen puu saattaa olla tarpeen tasapainottaa.
Voidaan tehdä kahdella Split()ja yhdellä Concat(). Aluksi jaamme merkkijonon kolmella erotettuna i -: nnellä ja i + j -merkillä, vastaavasti, poistettava rivi allokoidaan erilliselle (keskimmäiselle) solmulle. Sitten yhdistämme kaksi muuta solmua.
Jos haluat kysyä merkkijonoa C i , …, C i + j − 1 , etsi solmu u , joka sisältää C i c :n , ja vieraile sitten T :ssä solmusta u alkaen . Johdetaan C i , …, C i + j − 1 vierailevat T :stä järjestyksessä alkaen solmusta u . weight(u) >= j
| Operaatio | Rintareppu | joukko |
|---|---|---|
| Valitus [1] | O(log n) | O(1) |
| Erittely [1] | O(log n) | O(1) |
| Kiinnitä (tuhoa) | O(log n) epätasapainoinen / O(n) pahin tapaus | Päällä) |
| Kytkentä (tuhoamaton) | Päällä) | Päällä) |
| Hahmopassi [1] | Päällä) | Päällä) |
| Lisää [2] | O(log n) epätasapainoinen / O(n) pahin tapaus | Päällä) |
| Liite [2] | O(log n) epätasapainoinen / O(n) pahin tapaus | O(1) pehmustettu, O(n) epätasapainoinen |
| Poistaminen | O(log n) | Päällä) |
| Pyyntö | O(j + log n) | O(j) |
| Luominen | Päällä) | Päällä) |
Edut:
Virheet:
Tässä taulukossa verrataan merkkijono- ja slingtoteutusten algoritmisia ominaisuuksia, ei niiden raakanopeutta . Taulukon merkkijonot ovat vähemmän ylimääräisiä, joten esimerkiksi ketjuttaminen ja jakaminen on paljon nopeampaa pienille merkkijonoille. Kuitenkin käytettäessä taulukoita pitkille merkkijonoille, aika monimutkaisuus ja muistikustannukset ovat jo liian suuria (koska kopioiden määrä kasvaa huomattavasti). Sen sijaan suorituskyky on riippumaton tiedon pituudesta. Lisäksi muistin monimutkaisuuden molemmissa esityksissä arvioidaan O(n). Yhteenvetona voidaan todeta, että silmukat ovat suositeltavia, kun linjat ovat hyvin pitkiä ja ne vaihtuvat usein.
| jouset | |
|---|---|
| Merkkijonojen samankaltaisuusmitat | |
| Alimerkkijonohaku | |
| palindromit | |
| Jakson tasaus | |
| Suffiksirakenteet | |
| Muut | |