Geïndexeerde binaire boom

Ik kreeg een taak van de volgende aard. Het is nodig om een container te implementeren die de volgende functionaliteit biedt:

• voeg een nieuw element toe
• verwijder een element op volgnummer
• haal een element op op volgnummer
• gegevens worden in gesorteerde volgorde opgeslagen

Gegevens worden voortdurend toegevoegd en verwijderd, de structuur moet een snelle werking garanderen. Aanvankelijk probeerde ik zo'n ding te implementeren met behulp van de standaardcontainers van std. Deze aanpak was niet succesvol en het besef kwam dat ik iets zelf moest implementeren. Het enige dat in me opkwam, was een binaire zoekboom te gebruiken. Aangezien deze voldoet aan de eis van snelle invoeging, verwijdering en opslag van gegevens in gesorteerde volgorde. Het enige wat resteert is uit te denken hoe alle elementen te indexeren en de indices te herberekenen wanneer de boom verandert.

struct node_s {    
    data_t data;

    uint64_t weight; // gewicht van de knoop

    node_t *left;
    node_t *right;

    node_t *parent;
};

In dit artikel zullen er meer afbeeldingen en theorie zijn dan code. De code kan aan de onderstaande link worden bekeken.

Gewicht

Voor dit doel heeft de boom een kleine modificatie ondergaan, waarbij extra informatie over gewicht van de knoop is toegevoegd. Het gewicht van de knoop is het aantal nakomelingen van deze knoop + 1 (gewicht van een enkel element).

Functie voor het verkrijgen van het gewicht van een knoop:

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

    return 0;
}

Bij het blad is het gewicht respectievelijk 0.

Laten we nu overgaan naar een visuele voorstelling van een dergelijk kind. Zwarte kleur toont de sleutelnodige (de waarde wordt niet weergegeven, omdat dat niet nodig is), rood is het gewicht van de knoop, groen is de index van de knoop.

Wanneer de boom leeg is, is het gewicht 0. Laten we het wortelelement toevoegen:

Het gewicht van de boom wordt 1, het gewicht van het wortelelement is 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, dalen we naar beneden door de knopen en verhogen we de gewichtsteller van elke doorlopen knoop. Bij het creëren van een nieuwe knoop krijgt deze een gewicht 1. Als een knoop met deze sleutel al bestaat, zullen we de waarde overschrijven en terug omhoog gaan naar de wortel terwijl we de wijzigingen in de gewichten van alle knopen die we zijn gepasseerd ongedaan maken.
Als een knoop wordt verwijderd, dalen we naar beneden en decrementeren we de gewichten van de doorlopen knopen.

Indexen

Laten we nu bekijken hoe we knooppunten kunnen indexeren. Knooppunten bewaren duidelijk niet hun index, deze wordt berekend op basis van het gewicht van de knooppunten. Als ze hun index zouden opslaan, zou dat vereist zijn O(n) om tijd te nemen om de indexen van alle knooppunten bij te werken na elke wijziging in de boom.
Laten we overgaan tot een visuele voorstelling. Onze boom is leeg, laten we het eerste knooppunt toevoegen:

Het eerste knooppunt heeft de index 0, en nu zijn er 2 mogelijke gevallen. In het eerste geval verandert de index van het wortelelement, in het tweede geval verandert deze niet.

De linker subboom van de wortel weegt 1.

Tweede geval:

De index van de wortel is niet veranderd, omdat het gewicht van zijn linker subboom 0 bleef.

Hoe de index van een knooppunt wordt berekend, is het gewicht van de linker subboom + een getal dat van de ouder is doorgestuurd. Wat is dit getal?, Dit is de index telling, die aanvankelijk gelijk is aan 0, omdat de wortel geen ouder heeft. Verder hangt alles af van waar we naartoe gaan, naar het linkerkind of het rechterkind. Als het naar links is, wordt er niets aan de teller toegevoegd. Als het naar rechts is, voegen we de index van het huidige knooppunt toe.

Een voorbeeld van hoe de index van het element met sleutel 8 wordt berekend (rechterkind van de wortel). Dit is "Index van de wortel" + "gewicht van de linker subboom van het knooppunt met sleutel 8" + "1" == 3 + 2 + 1 == 6
De index van het element met sleutel 6 zal zijn "Index van de wortel" + 1 == 3 + 1 == 4

Bijgevolg is het vereist om tijd te hebben om een element op index te krijgen of te verwijderen O(log n), omdat we het benodigde element eerst moeten vinden (van de wortel naar dit element moeten afzakken).

Diepte

Op basis van het gewicht kan ook de diepte van de boom worden berekend. Dit is nodig voor de balans.
Hiervoor moet het gewicht van het huidige knooppunt worden afgerond naar het eerste getal in de macht van 2 dat groter dan of gelijk is aan het gegeven gewicht, en daar de binaire logaritme van genomen worden. Op deze manier krijgen we de diepte van de boom, op voorwaarde dat deze in balans is. De boom wordt in balans gebracht na het invoegen van een nieuw element. Ik zal de theorie over hoe bomen in balans te brengen niet bespreken. In de broncode bevindt zich de functie voor balans.

Code voor het omzetten 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));
}

Conclusies

• het invoegen van een nieuw element gebeurt in O(log n)
• het verwijderen van een element op volgnummer gebeurt in O(log n)
• het verkrijgen van een element op volgnummer gebeurt in O(log n)

Snelheid O(log n) betalen we voor het feit dat alle gegevens in gesorteerde volgorde worden opgeslagen.

Waar zo'n structuur nuttig kan zijn, weet ik niet. Gewoon een oefening om nogmaals te begrijpen hoe bomen werken. Bedankt voor je aandacht.

Links

• Broncode van de boom

In het project bevinden zich testgegevens om de snelheid van de werking te controleren. De boom wordt gevuld 1000000 met elementen. En er vindt een opeenvolgende verwijdering, invoegen en ophalen van elementen plaats 1000000 keer. Dat wil zeggen 3000000 bewerkingen. Het resultaat bleek heel acceptabel te zijn ~ 8 seconden.

Bron: habr.com