lisäysoperaatio

Lisäysoperaatio tarkoittaa operaatioa, jolla uusi elementti lisätään olemassa olevaan kokoelmaan tai tietorakenteeseen. Sitä käytetään sekä ohjelmoinnissa että tietojenkäsittelytieteessä erilaisten rakenteiden, kuten taulukoiden, linkitettyjen listojen, puiden ja hakutaulujen, hallinnassa. Lisäys voidaan tehdä erilaisilla säännöillä: alkio voidaan lisätä loppuun, tiettyyn kohtaan tai tiettyyn avaimen arvoon. Merkitsee usein muutoksen tilaan, jossa rakenne kasvaa yhdellä elementillä.

Tietorakenteissa lisäysoperaation suoritusnopeus ja kustannukset riippuvat rakenteesta. Taulukossa tai dynaamisessa listassa lisäys loppuun voi olla amortisoidusti O(1), mutta lisäys keskelle tai alkuun vaatii arvojen siirtämistä ja on O(n). Linkitetty listä lisäys on O(1), kun sijoituskohta tunnetaan, mutta eteneminen oikeaan kohtaan voi olla O(n). Tasapainotetussa puussa tai hakutaulussa lisäys on usein O(log n) tai O(1) keskimäärin, riippuen rakenteesta ja mahdollisista sallituista duplikaateista.

Ulkopuoliset rakenteet, kuten tietokannat, tukevat lisäysoperaatiota INSERT-komennolla, jonka kustannus riippuu indeksien, rajoitteiden ja tallennusvaiheen optimoinneista. Joissakin rakenteissa lisäys voi muuttaa järjestystä, eheyttä tai uniikkiutta, jolloin operaatio saattaa epäonnistua, jos elementti on jo olemassa.

Esimerkkeinä ohjelmointikielissä: list.insert(i, x) tai list.add(x) lisää alkiota listaan; SQL: INSERT INTO taulu ... lisää rivin tietokantaan. Lisäysoperaatio on yksi peruskäsitteistä algoritmeissa ja tietorakenteissa, ja sen ominaisuudet määrittelevät monien operaatioiden tehokkuuden.