Geïndexeerde binaire boom

Ik kwam het volgende type probleem tegen. Het is noodzakelijk om een ​​gegevensopslagcontainer te implementeren die de volgende functionaliteit biedt:

• nieuw element invoegen
• verwijder element op serienummer
• krijg element op rangtelwoord
• gegevens worden in gesorteerde vorm opgeslagen

Er worden voortdurend gegevens toegevoegd en verwijderd, de structuur moet een hoge werkingssnelheid garanderen. In eerste instantie probeerde ik zoiets te implementeren met behulp van standaardcontainers van soa. Dit pad werd niet met succes bekroond en het inzicht kwam dat ik zelf iets moest implementeren. Het enige dat in me opkwam, was het gebruik van een binaire zoekboom. Omdat het voldoet aan de eis van snelle invoeging, verwijdering en opslag van gegevens in gesorteerde vorm. Het enige dat overblijft is uitzoeken hoe alle elementen moeten worden geïndexeerd en de indices opnieuw moeten worden berekend wanneer de boom verandert.

struct node_s {    
    data_t data;

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

    node_t *left;
    node_t *right;

    node_t *parent;
};

Het artikel zal meer afbeeldingen en theorie bevatten dan code. De code kunt u bekijken via onderstaande link.

Gewicht

Om dit te bereiken onderging de boom een ​​kleine aanpassing, er werd aanvullende informatie over toegevoegd gewicht knooppunt. Het knooppuntgewicht is aantal nakomelingen van dit knooppunt + 1 (gewicht van één enkel element).

Functie voor het verkrijgen van knooppuntgewicht:

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

    return 0;
}

Het gewicht van het vel is overeenkomstig gelijk aan 0.

Laten we vervolgens verder gaan met een visuele weergave van een voorbeeld van zo'n boom. zwart de knooppuntsleutel wordt in kleur weergegeven (de waarde wordt niet weergegeven, aangezien dit niet nodig is), rood — knoopgewicht, groen — knooppuntindex.

Als onze boom leeg is, is het gewicht 0. Laten we er een wortelelement aan toevoegen:

Het gewicht van de boom wordt 1, het gewicht van het wortelelement wordt 1. Het gewicht van het wortelelement is het gewicht van de boom.

Laten we nog een paar elementen toevoegen:

Elke keer dat er een nieuw element wordt toegevoegd, gaan we langs de knooppunten en verhogen we de gewichtsteller van elk gepasseerd knooppunt. Wanneer een nieuw knooppunt wordt gemaakt, wordt er een gewicht aan toegekend 1. Als er al een knooppunt met een dergelijke sleutel bestaat, overschrijven we de waarde en gaan we terug naar de root, waarbij we de veranderingen in de gewichten van alle knooppunten die we zijn gepasseerd annuleren.
Als een knooppunt wordt verwijderd, gaan we naar beneden en verlagen we de gewichten van de gepasseerde knooppunten.

Index

Laten we nu verder gaan met het indexeren van knooppunten. Knooppunten slaan hun index niet expliciet op; deze wordt berekend op basis van het gewicht van de knooppunten. Als ze hun index zouden opslaan, zou dit vereist zijn O (n) tijd om de indexen van alle knooppunten bij te werken na elke wijziging in de boom.
Laten we verder gaan met een visuele weergave. Onze boom is leeg, laten we het eerste knooppunt eraan toevoegen:

Het eerste knooppunt heeft een index 0, en nu zijn er 2 gevallen mogelijk. In het eerste geval zal de index van het rootelement veranderen, in het tweede geval zal deze niet veranderen.

Bij de wortel weegt de linker deelboom 1.

Tweede geval:

De index van de wortel veranderde niet omdat het gewicht van de linker deelboom 0 bleef.

De index van een knooppunt wordt berekend als het gewicht van de linkersubboom + het getal dat door de ouder wordt doorgegeven. Wat is dit nummer?, Dit is de indexteller, aanvankelijk is deze gelijk aan 0, omdat de wortel heeft geen ouder. Dan hangt het allemaal af van waar we naar het linkerkind of het rechter gaan. Als het links is, wordt er niets aan de teller toegevoegd. Als we de index van het huidige knooppunt toevoegen aan het rechterknooppunt.

Hoe bijvoorbeeld de index van een element met sleutel 8 (het rechterkind van de wortel) wordt berekend. Dit is "Root Index" + "gewicht van linker subboom van knooppunt met sleutel 8" + "1" == 3 + 2 + 1 == 6
De index van het element met sleutel 6 is "Root Index" + 1 == 3 + 1 == 4

Dienovereenkomstig kost het tijd om een ​​element per index op te halen en te verwijderen O (log n), omdat we, om het gewenste element te krijgen, het eerst moeten vinden (vanaf de root naar dit element gaan).

diepte

Op basis van het gewicht kunt u ook de diepte van de boom berekenen. Noodzakelijk voor het balanceren.
Om dit te doen, moet het gewicht van het huidige knooppunt worden afgerond op het eerste getal tot de macht van 2 dat groter is dan of gelijk is aan het gegeven gewicht, en daaruit de binaire logaritme halen. Dit geeft ons de diepte van de boom, ervan uitgaande dat deze in balans is. De boom is in balans na het invoegen van een nieuw element. Ik ga geen theorie geven over hoe je bomen in evenwicht kunt brengen. De broncodes zorgen voor een balanceringsfunctie.

Code voor het omrekenen van gewicht naar diepte.

/*
 * Возвращает первое число в степени 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));
}

Resultaten van

• het invoegen van een nieuw element vindt plaats in O (log n)
• het verwijderen van een element op serienummer vindt plaats in O (log n)
• het verkrijgen van een element op serienummer vindt plaats in O (log n)

snelheid O (log n) Wij betalen ervoor dat alle gegevens gesorteerd worden opgeslagen.

Ik weet niet waar zo’n structuur nuttig zou kunnen zijn. Even een puzzel om opnieuw te begrijpen hoe bomen werken. Bedankt voor uw aandacht.

referenties

• Boom broncode

Het project bevat testgegevens om de werkingssnelheid te controleren. De boom raakt vol 1000000 elementen. En er is een opeenvolgende verwijdering, invoeging en ophalen van elementen 1000000 eenmaal. Dat is 3000000 activiteiten. Het resultaat bleek redelijk goed ~ 8 seconden.

Bron: www.habr.com