Jeg kom over følgende type problem. Det er nødvendig å implementere en datalagringsbeholder som gir følgende funksjonalitet:
- sette inn nytt element
- fjern element etter serienummer
- få element etter ordenstall
- data lagres i sortert form
Data legges til og fjernes hele tiden, strukturen skal sikre rask driftshastighet. Først prøvde jeg å implementere noe slikt ved å bruke standard containere fra std. Denne veien ble ikke kronet med suksess og forståelsen kom for at jeg trengte å implementere noe selv. Det eneste som kom til tankene var å bruke et binært søketre. Fordi den oppfyller kravet om rask innsetting, sletting og lagring av data i sortert form. Alt som gjenstår er å finne ut hvordan du skal indeksere alle elementene og beregne indeksene på nytt når treet endres.
struct node_s {
data_t data;
uint64_t weight; // вес узла
node_t *left;
node_t *right;
node_t *parent;
};Artikkelen vil inneholde flere bilder og teori enn kode. Koden kan sees på lenken nedenfor.
Vekt
For å oppnå dette gjennomgikk treet en liten modifikasjon, tilleggsinformasjon ble lagt til om vekt node. Nodevekten er antall etterkommere av denne noden + 1 (vekten av et enkelt element).
Funksjon for å få nodevekt:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}Vekten på arket er tilsvarende lik 0.
Deretter, la oss gå videre til en visuell representasjon av et eksempel på et slikt tre. svart nodenøkkelen vises i farger (verdien vises ikke, siden dette ikke er nødvendig), rød - knutevekt, grønn — nodeindeks.
Når treet vårt er tomt, er vekten 0. La oss legge til et rotelement til det:
Vekten av treet blir 1, vekten av rotelementet blir 1. Vekten av rotelementet er vekten av treet.
La oss legge til noen flere elementer:
Hver gang et nytt element legges til, går vi nedover nodene og øker vekttelleren for hver node som passeres. Når en ny node er opprettet, tildeles en vekt til den 1. Hvis en node med en slik nøkkel allerede eksisterer, vil vi overskrive verdien og gå tilbake til roten, og kansellere endringene i vektene til alle noder vi har passert.
Hvis en node blir fjernet, går vi ned og reduserer vektene til de passerte nodene.
Indekser
La oss nå gå videre til hvordan du indekserer noder. Noder lagrer ikke eksplisitt indeksen deres, den beregnes basert på vekten av nodene. Hvis de lagret indeksen sin, ville det være nødvendig O (n) tid til å oppdatere indeksene til alle noder etter hver endring i treet.
La oss gå videre til en visuell representasjon. Treet vårt er tomt, la oss legge til den første noden til det:
Den første noden har en indeks 0, og nå er 2 tilfeller mulige. I den første vil indeksen til rotelementet endres, i den andre vil den ikke endres.
Ved roten veier det venstre undertreet 1.
Andre tilfelle:
Indeksen til roten endret seg ikke fordi vekten til venstre undertre forble 0.
Indeksen til en node beregnes som vekten av dets venstre undertre + tallet som sendes fra overordnet. Hva er dette tallet?, Dette er indekstelleren, i utgangspunktet er den lik 0, fordi roten har ingen forelder. Så kommer alt an på hvor vi går ned til venstre barn eller høyre. Hvis til venstre, blir ingenting lagt til telleren. Hvis vi legger til indeksen til gjeldende node til den høyre.
For eksempel hvordan indeksen til et element med nøkkel 8 (det høyre barnet av roten) beregnes. Dette er "rotindeks" + "vekt av venstre undertre av node med nøkkel 8" + "1" == 3 + 2 + 1 == 6
Indeksen til elementet med nøkkel 6 vil være "Root Index" + 1 == 3 + 1 == 4
Følgelig tar det tid å hente og slette et element etter indeks O (log n), fordi for å få det ønskede elementet må vi først finne det (gå ned fra roten til dette elementet).
dybde
Basert på vekten kan du også beregne dybden på treet. Nødvendig for balansering.
For å gjøre dette, må vekten av gjeldende node avrundes til det første tallet til potensen 2 som er større enn eller lik den gitte vekten og ta den binære logaritmen fra den. Dette vil gi oss dybden på treet, forutsatt at det er balansert. Treet er balansert etter å ha satt inn et nytt element. Jeg vil ikke gi en teori om hvordan man balanserer trær. Kildekodene gir en balanserende funksjon.
Kode for å konvertere vekt til dybde.
/*
* Возвращает первое число в степени 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));
}Resultater av
- innsetting av et nytt element skjer i O (log n)
- sletting av et element etter serienummer skjer i O (log n)
- innhenting av et element etter serienummer skjer i O (log n)
Hastighet O (log n) Vi betaler for at all data lagres i sortert form.
Jeg vet ikke hvor en slik struktur kan være nyttig. Bare et puslespill for igjen å forstå hvordan trær fungerer. Takk for din oppmerksomhet.
referanser
Prosjektet inneholder testdata for å sjekke driftshastigheten. Treet fylles opp 1000000 elementer. Og det er en sekvensiell sletting, innsetting og henting av elementer 1000000 en gang. Det er 3000000 operasjoner. Resultatet viste seg å være ganske bra ~ 8 sekunder.
Kilde: www.habr.com