Indekseret binært træ

Jeg stødte på følgende type problem. Det er nødvendigt at implementere en datalagringsbeholder, der giver følgende funktionalitet:

• indsæt nyt element
• fjern element ved serienummer
• få element ved ordenstal
• data gemmes i sorteret form

Data tilføjes og fjernes konstant, strukturen skal sikre hurtig driftshastighed. Først forsøgte jeg at implementere sådan noget ved hjælp af standardbeholdere fra std. Denne vej blev ikke kronet med succes, og forståelsen kom af, at jeg var nødt til at implementere noget selv. Det eneste, der kom til at tænke på, var at bruge et binært søgetræ. Fordi det opfylder kravet om hurtig indsættelse, sletning og lagring af data i sorteret form. Det eneste, der er tilbage, er at finde ud af, hvordan man indekserer alle elementerne og genberegner indeksene, når træet ændres.

struct node_s {    
    data_t data;

    uint64_t weight; // вес узла

    node_t *left;
    node_t *right;

    node_t *parent;
};

Artiklen vil indeholde flere billeder og teori end kode. Koden kan ses på nedenstående link.

Vægt

For at opnå dette gennemgik træet en lille ændring, yderligere information blev tilføjet om vægt node. Nodevægten er antallet af efterkommere af denne node + 1 (vægt af et enkelt element).

Funktion til at få nodevægt:

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

    return 0;
}

Vægten af ​​arket er tilsvarende lig med 0.

Lad os derefter gå videre til en visuel repræsentation af et eksempel på et sådant træ. sort node-nøglen vil blive vist i farver (værdien vil ikke blive vist, da dette ikke er nødvendigt), rød - knudevægt, grøn — nodeindeks.

Når vores træ er tomt, er dets vægt 0. Lad os tilføje et rodelement til det:

Træets vægt bliver 1, vægten af ​​rodelementet bliver 1. Vægten af ​​rodelementet er vægten af ​​træet.

Lad os tilføje nogle flere elementer:

Hver gang et nyt element tilføjes, går vi ned i noderne og øger vægttælleren for hver node, der passeres. Når en ny node oprettes, tildeles den en vægt 1. Hvis en node med en sådan nøgle allerede eksisterer, vil vi overskrive værdien og gå tilbage til roden og annullere ændringerne i vægten af ​​alle noder, som vi har passeret.
Hvis en node fjernes, så går vi ned og nedsætter vægten af ​​de passerede noder.

Indekser

Lad os nu gå videre til, hvordan man indekserer noder. Noder gemmer ikke eksplicit deres indeks, det beregnes ud fra nodernes vægt. Hvis de gemte deres indeks, ville det være nødvendigt O (n) tid til at opdatere indekserne for alle noder efter hver ændring i træet.
Lad os gå videre til en visuel repræsentation. Vores træ er tomt, lad os tilføje den 1. node til det:

Den første node har et indeks 0, og nu er 2 tilfælde mulige. I det første ændres indekset for rodelementet, i det andet ændres det ikke.

Ved roden vejer det venstre undertræ 1.

Andet tilfælde:

Rodens indeks ændrede sig ikke, fordi vægten af ​​dens venstre undertræ forblev 0.

Indekset for en node beregnes som vægten af ​​dets venstre undertræ + det tal, der sendes fra forælderen. Hvad er dette tal?, Dette er indekstælleren, som oprindeligt er lig med 0, fordi roden har ingen forælder. Så kommer det helt an på, hvor vi går ned til venstre barn eller højre. Hvis til venstre, tilføjes intet til tælleren. Hvis vi tilføjer indekset for den aktuelle node til den højre.

For eksempel hvordan indekset for et element med nøgle 8 (det højre underordnede af roden) beregnes. Dette er "Root Index" + "vægt af venstre undertræ af node med tast 8" + "1" == 3 + 2 + 1 == 6
Indekset for elementet med tast 6 vil være "Root Index" + 1 == 3 + 1 == 4

Derfor tager det tid at hente og slette et element efter indeks O (log n), for for at få det ønskede element skal vi først finde det (gå ned fra roden til dette element).

dybde

Ud fra vægten kan du også beregne træets dybde. Nødvendig for balancering.
For at gøre dette skal vægten af ​​den aktuelle node afrundes til det første tal til 2 potens, som er større end eller lig med den givne vægt og tage den binære logaritme fra den. Dette vil give os dybden af ​​træet, forudsat at det er afbalanceret. Træet er afbalanceret efter indsættelse af et nyt element. Jeg vil ikke give en teori om, hvordan man balancerer træer. Kildekoderne giver en balancerende funktion.

Kode til konvertering af vægt 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));
}

Resultaterne af

• indsættelse af et nyt element sker i O (log n)
• sletning af et element efter serienummer sker i O (log n)
• opnåelse af et element ved serienummer sker i O (log n)

Fart O (log n) Vi betaler for, at al data opbevares i sorteret form.

Jeg ved ikke, hvor en sådan struktur kan være nyttig. Bare et puslespil for igen at forstå, hvordan træer fungerer. Tak for din opmærksomhed.

RЎSЃS <P "RєRё

• Træets kildekode

Projektet indeholder testdata for at kontrollere driftshastigheden. Træet er ved at blive fyldt op 1000000 elementer. Og der er en sekventiel sletning, indsættelse og genfinding af elementer 1000000 enkelt gang. Det er 3000000 operationer. Resultatet viste sig at være ganske godt ~ 8 sekunder.

Kilde: www.habr.com