Törmäsin seuraavan tyyppiseen ongelmaan. On tarpeen ottaa käyttöön tietojen tallennussäiliö, joka tarjoaa seuraavat toiminnot:
- lisää uusi elementti
- poista elementti sarjanumerolla
- saada elementti järjestysnumerolla
- tiedot tallennetaan lajiteltuna
Dataa lisätään ja poistetaan jatkuvasti, rakenteen tulee varmistaa nopea toimintanopeus. Aluksi yritin toteuttaa tällaista käyttämällä tavallisia kontteja std. Tätä polkua ei kruunannut menestys ja tuli ymmärrys, että minun täytyy itse toteuttaa jotain. Ainoa asia, joka tuli mieleen, oli käyttää binaarihakupuuta. Koska se täyttää vaatimuksen nopeasta tietojen lisäämisestä, poistamisesta ja tallentamisesta lajiteltuina. Jäljelle jää vain selvittää, kuinka kaikki elementit indeksoidaan ja indeksit lasketaan uudelleen, kun puu muuttuu.
struct node_s {
data_t data;
uint64_t weight; // вес узла
node_t *left;
node_t *right;
node_t *parent;
};Artikkeli sisältää enemmän kuvia ja teoriaa kuin koodia. Koodi on katsottavissa alla olevasta linkistä.
Paino
Tämän saavuttamiseksi puuta muokattiin hieman, ja siitä lisättiin lisätietoja paino solmu. Solmun paino on tämän solmun jälkeläisten lukumäärä + 1 (yksittäisen elementin paino).
Toiminto solmun painon saamiseksi:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}Arkin paino on vastaavasti yhtä suuri 0.
Seuraavaksi siirrytään tällaisen puun esimerkin visuaaliseen esitykseen. musta solmuavain näytetään värillisenä (arvoa ei näytetä, koska se ei ole välttämätöntä), punainen - solmun paino, vihreä - solmuindeksi.
Kun puumme on tyhjä, sen paino on 0. Lisätään siihen juurielementti:
Puun painoksi tulee 1, juurielementin painoksi 1. Juurielementin paino on puun paino.
Lisätään vielä muutama elementti:
Joka kerta kun uusi elementti lisätään, menemme alas solmuissa ja lisäämme jokaisen ohitetun solmun painolaskuria. Kun uusi solmu luodaan, sille määritetään paino 1. Jos solmu tällaisella avaimella on jo olemassa, kirjoitamme arvon päälle ja palaamme juureen peruuttamalla kaikkien ohitettujen solmujen painojen muutokset.
Jos solmua poistetaan, menemme alas ja vähennämme ohitettujen solmujen painoja.
Indeksit
Siirrytään nyt solmujen indeksointiin. Solmut eivät eksplisiittisesti tallenna indeksiä, se lasketaan solmujen painon perusteella. Jos he tallentavat hakemistonsa, se vaadittaisiin O (n) aika päivittää kaikkien solmujen indeksit jokaisen puun muutoksen jälkeen.
Siirrytään visuaaliseen esitykseen. Puumme on tyhjä, lisätään siihen ensimmäinen solmu:
Ensimmäisellä solmulla on indeksi 0, ja nyt 2 tapausta on mahdollista. Ensimmäisessä juurielementin indeksi muuttuu, toisessa se ei muutu.
Juuressa vasen alipuu painaa 1.
Toinen tapaus:
Juuren indeksi ei muuttunut, koska sen vasemman alipuun paino pysyi 0:ssa.
Solmun indeksi lasketaan sen vasemman alipuun painona + emolta välitettynä numerona. Mikä tämä luku on?, Tämä on indeksilaskuri, aluksi se on yhtä suuri 0, koska juurella ei ole vanhempia. Sitten kaikki riippuu siitä, missä mennään vasemmalle tai oikealle lapselle. Jos vasemmalla, laskuriin ei lisätä mitään. Jos lisäämme nykyisen solmun indeksin oikeaan.
Esimerkiksi kuinka elementin indeksi avaimella 8 (juuren oikea lapsi) lasketaan. Tämä on "juuriindeksi" + "avaimen 8 solmun vasemman alipuun paino" + "1" == 3 + 2 + 1 == 6
Elementin indeksi avaimella 6 on "Juuriindeksi" + 1 == 3 + 1 == 4
Vastaavasti elementin hakeminen ja poistaminen indeksin mukaan vie aikaa O (log n), koska saadaksemme halutun elementin meidän on ensin löydettävä se (mene alas juuresta tähän elementtiin).
syvyys
Painon perusteella voit myös laskea puun syvyyden. Tasapainotuksen kannalta välttämätön.
Tätä varten nykyisen solmun paino on pyöristettävä ensimmäiseen numeroon 2:n potenssiin, joka on suurempi tai yhtä suuri kuin annettu paino, ja ottaa siitä binäärilogaritmi. Tämä antaa meille puun syvyyden olettaen, että se on tasapainossa. Puu tasapainotetaan uuden elementin lisäämisen jälkeen. En anna teoriaa puiden tasapainottamisesta. Lähdekoodit tarjoavat tasapainotustoiminnon.
Koodi painon muuttamiseksi syvyydeksi.
/*
* Возвращает первое число в степени 2, которое больше или ровно x
*/
uint64_t bntree::cpl2(uint64_t x) {
x = x - 1;
x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16);
x = x | (x >> 32);
return x + 1;
}
/*
* Двоичный логарифм от числа
*/
long bntree::ilog2(long d) {
int result;
std::frexp(d, &result);
return result - 1;
}
/*
* Вес к глубине
*/
uint64_t bntree::weight_to_depth(node_t *p) {
if (p == NULL) {
return 0;
}
if (p->weight == 1) {
return 1;
} else if (p->weight == 2) {
return 2;
}
return this->ilog2(this->cpl2(p->weight));
}Tulokset
- uusi elementti lisätään sisään O (log n)
- elementin poistaminen sarjanumerolla tapahtuu O (log n)
- elementin hankkiminen sarjanumerolla tapahtuu O (log n)
Nopeus O (log n) Maksamme siitä, että kaikki tiedot tallennetaan lajiteltuna.
En tiedä missä tällainen rakenne voisi olla hyödyllinen. Vain palapeli ymmärtääksesi taas, kuinka puut toimivat. Kiitos huomiostasi.
viittaukset
Projekti sisältää testidataa toiminnan nopeuden tarkistamiseksi. Puu täyttyy 1000000 elementtejä. Ja elementtejä poistetaan, lisätään ja haetaan peräkkäin 1000000 kerran. Tuo on 3000000 toiminnot. Tulos osoittautui varsin hyväksi ~ 8 sekuntia.
Lähde: will.com