Indeksert binært tre

Jeg fikk en oppgave av følgende art. Det er nødvendig å implementere en datalagringsbeholder som tilbyr følgende funksjonalitet:

• sette inn et nytt element
• fjerne et element etter rekkefølgen
• hente et element etter rekkefølgen
• dataene lagres i sortert rekkefølge

Dataene legges kontinuerlig til og fjernes, og strukturen må sikre rask drift. Jeg prøvde først å implementere noe ved å bruke standardbeholdere fra std. Denne veien førte ikke frem, og det ble klart at jeg måtte implementere noe selv. Det eneste som kom opp i tankene mine, var å bruke et binært søketre, ettersom det oppfyller kravet om rask innsetting, fjerning og lagring av data i sortert rekkefølge. Det gjensto bare å finne ut hvordan man skulle indeksere alle elementene og omberegne indeksene når treet endres.

struct node_s {    
    data_t data;

    uint64_t weight; // vekten til noden

    node_t *left;
    node_t *right;

    node_t *parent;
};

I artikkelen vil det være flere bilder og teori enn kode. Koden kan sees ved lenken nedenfor.

Vekt

For dette formålet ble treet utsatt for en liten modifikasjon, ekstra informasjon om vekten til noden. Vekten til noden er antall etterkommere av denne noden + 1 (vekten til et enkelt element).

Funksjonen for å hente vekten til noden:

uint64_t bntree::get_child_weight(node_t *node) {
    if (node) {
        return node->weight;
    }

    return 0;
}

For et blad er vekten tilsvarende lik 0.

Deretter går vi videre til en visuell fremstilling av et eksempel på et slikt tre. I svart farge vil nøkkelen til noden bli vist (verdien vil ikke bli vist, da det ikke er nødvendig), i rødt — vekten til noden, i grønt — indeksen til noden.

Når treet vårt er tomt, er vekten lik 0. La oss legge til rot-elementet:

Vekten til treet blir 1, vekten til rot-elementet er 1. Vekten til rot-elementet 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 vekt-telleren for hver node vi passerer. Når vi lager en ny node, settes vekten til ham 1. Hvis noden med en slik nøkkel allerede eksisterer, overskriver vi verdien og går tilbake opp til roten, mens vi annullerer vekten til alle nodene vi har gått forbi.
Hvis en node fjernes, går vi nedover og dekrementerer vekten til de noder vi passerer.

Indexes

La oss nå gå videre til hvordan man indekserer noder. Noder lagrer ikke sin indeks, den beregnes basert på vekten av nodene. Hadde de lagret sin indeks, ville det vært nødvendig O(n) med tid for å oppdatere indekser for alle noder etter hver endring i treet.
La oss gå videre til en visuell fremstilling. Vårt tre er tomt, la oss legge til den første noden:

Den første noden har indeks 0, og nå er det to mulige tilfeller. I det første tilfellet endres roten sin indeks, i det andre tilfellet endres den ikke.

Rots treet har venstre deltre som veier 1.

Andre tilfelle:

Indeksen til roten har ikke endret seg, ettersom vekten av venstre deltre forblir 0.

Hvordan indeksen til en node beregnes, er vekten av venstre deltre + tallet som er sendt fra forelderen. Hva er dette tallet? Det er indeks-telleren, som opprinnelig er 0, siden roten ikke har noen forelder. Videre avhenger alt av hvilken vei vi går, til venstre barn eller høyre. Hvis vi går til venstre, legges det ikke til noe til telleren. Hvis vi går til høyre, legges indeksen til den nåværende noden til.

For eksempel, hvordan indeksen til elementet med nøkkel 8 (høyre barn av roten) beregnes. Det er "Indeksen til roten" + "vekten av venstre deltre til noden med nøkkel 8" + "1" == 3 + 2 + 1 == 6
Indeksen til elementet med nøkkel 6 vil være "Indeksen til roten" + 1 == 3 + 1 == 4

Dermed, for å få, slette et element ved indeks, kreves det tid O(log n), fordi for å få det ønskede elementet, må vi først finne det (gå fra roten til dette elementet).

Dybde

Både vekten kan brukes til å beregne dybden av treet. Nødvendig for balansering.
For dette må vekten av den nåværende noden avrundes til det første tallet med eksponent 2 som er større enn eller lik den gitte vekten, og vi tar den binære logaritmen av det. Dermed får vi dybden av treet, under forutsetning av at det er balansert. Treet balanseres etter innsetting av et nytt element. Jeg vil ikke gå inn på teorien om hvordan man balanserer trær. I kildekodene er det presentert en balanseringsfunksjon.

Koden 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

• innsetting av et nytt element skjer på O(log n)
• fjerning av elementet etter rekkefølge skjer på O(log n)
• henting av elementet etter rekkefølge skjer på O(log n)

Hastigheten O(log n) betaler for at alle dataene lagres i sortert form.

Hvor en slik struktur kan være nyttig — vet jeg ikke. Bare en oppgave for å forstå hvordan trær fungerer. Takk for oppmerksomheten.

Lenker

• Kildekoden til treet

Prosjektet inneholder testdata for å sjekke hastigheten. Treet fylles med 1000000 elementer. Og det skjer sekvensiell fjerning, innsetting og henting av elementer 1000000 ganger. Det vil si 3000000 operasjoner. Resultatet var ganske bra ~ 8 sekunder.

Kilde: habr.com