Indexelt bináris fa

A következő típusú problémával találkoztam. Olyan adattároló tárolót kell megvalósítani, amely a következő funkciókat biztosítja:

• új elem beszúrása
• távolítsa el az elemet a sorozatszám alapján
• sorszám szerint kapja meg az elemet
• az adatokat rendezett formában tároljuk

Az adatok hozzáadása és eltávolítása folyamatosan történik, a szerkezetnek biztosítania kell a gyors működési sebességet. Eleinte megpróbáltam megvalósítani egy ilyet szabványos konténerekkel std. Ezt az utat nem koronázta siker, és jött a megértés, hogy valamit magamnak kell megvalósítanom. Az egyetlen dolog, ami eszembe jutott, egy bináris keresőfa használata volt. Mert megfelel az adatok gyors beszúrásának, törlésének és rendezett formában történő tárolásának követelményének. Már csak azt kell kitalálni, hogyan kell az összes elemet indexelni, és újraszámítani az indexeket, amikor a fa megváltozik.

struct node_s {    
    data_t data;

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

    node_t *left;
    node_t *right;

    node_t *parent;
};

A cikk több képet és elméletet tartalmaz, mint kódot. A kód az alábbi linken megtekinthető.

súly

Ennek elérése érdekében a fa enyhe módosításon esett át, további információk kerültek hozzáadásra súly csomópont. A csomópont súlya az ennek a csomópontnak a leszármazottainak száma + 1 (egyetlen elem súlya).

Funkció a csomópont súlyának meghatározásához:

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

    return 0;
}

A lap súlya ennek megfelelően egyenlő 0.

Ezután térjünk át egy ilyen fa példájának vizuális megjelenítésére. Fekete a csomópont kulcsa színesen jelenik meg (az érték nem jelenik meg, mivel ez nem szükséges), piros - csomó súlya, zöld — csomóponti index.

Ha a fánk üres, a súlya 0. Adjunk hozzá egy gyökérelemet:

A fa súlya 1 lesz, a gyökérelemé 1. A gyökérelem súlya a fa súlya.

Adjunk hozzá még néhány elemet:

Minden alkalommal, amikor új elemet adunk hozzá, lefelé haladunk a csomópontokon, és növeljük az egyes átadott csomópontok súlyszámlálóját. Amikor új csomópont jön létre, a rendszer súlyt rendel hozzá 1. Ha már létezik ilyen kulccsal rendelkező csomópont, akkor felülírjuk az értéket, és visszamegyünk a gyökérhez, törölve az összes átadott csomópont súlyának változásait.
Ha egy csomópont eltávolításra kerül, akkor lefelé megyünk, és csökkentjük az átadott csomópontok súlyát.

Indexek

Most térjünk át a csomópontok indexelésére. A csomópontok nem tárolják kifejezetten az indexüket, azt a csomópontok súlya alapján számítják ki. Ha tárolnák az indexüket, akkor szükség lenne rá O (n) ideje frissíteni az összes csomópont indexét a fa minden módosítása után.
Térjünk át a vizuális ábrázolásra. A fánk üres, adjuk hozzá az 1. csomópontot:

Az első csomópontnak van indexe 0, és most 2 eset lehetséges. Az elsőben a gyökérelem indexe változik, a másodikban nem.

A gyökérnél a bal oldali részfa súlya 1.

Második eset:

A gyökér indexe nem változott, mert bal oldali részfájának súlya 0 maradt.

Egy csomópont indexe a bal oldali részfa súlya + a szülőtől átadott szám alapján kerül kiszámításra. Mi ez a szám?, Ez az indexszámláló, kezdetben egyenlő 0, mert a gyökérnek nincs szülője. Aztán minden attól függ, hogy hova megyünk le a bal gyerekhez vagy a jobbhoz. Ha balra, akkor semmi sem kerül hozzáadásra a számlálóhoz. Ha az aktuális csomópont indexét hozzáadjuk a megfelelőhöz.

Például egy 8-as kulcsú elem indexének kiszámítása (a gyökér jobb gyermeke). Ez a "gyökérindex" + "a csomópont bal oldali részfájának súlya a 8-as kulccsal" + "1" == 3 + 2 + 1 == 6
A 6-os kulcsú elem indexe "Gyökérindex" + 1 == 3 + 1 == 4

Ennek megfelelően egy elem indexenkénti beszerzése és törlése időbe telik O (log n), mert ahhoz, hogy megkapjuk a kívánt elemet, először meg kell találnunk (a gyökértől le kell menni ehhez az elemhez).

mélység

A súly alapján kiszámolhatja a fa mélységét is. Kiegyensúlyozáshoz szükséges.
Ehhez az aktuális csomópont súlyát az első számra kell kerekíteni 2 hatványára, amely nagyobb vagy egyenlő, mint az adott súly, és ebből ki kell venni a bináris logaritmust. Ez megadja nekünk a fa mélységét, feltételezve, hogy kiegyensúlyozott. Új elem beillesztése után a fa kiegyensúlyozódik. Nem adok elméletet a fák egyensúlyáról. A forráskódok kiegyenlítő funkciót biztosítanak.

Kód a súly mélységgé alakításához.

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

Eredményei

• új elem beillesztése történik O (log n)
• egy elem törlése sorozatszám alapján történik O (log n)
• egy elem sorozatszám szerinti megszerzése történik O (log n)

Sebesség O (log n) Fizetünk azért, hogy minden adatot rendezett formában tárolunk.

Nem tudom, hol lehet hasznos egy ilyen szerkezet. Csak egy rejtvény, hogy újra megértsük a fák működését. Köszönöm a figyelmet.

referenciák

• Fa forráskódja

A projekt tesztadatokat tartalmaz a működés sebességének ellenőrzésére. A fa megtelik 1000000 elemeket. És van az elemek szekvenciális törlése, beillesztése és visszakeresése 1000000 egyszer. Azaz 3000000 tevékenységek. Az eredmény egészen jónak bizonyult ~ 8 másodperc.

Forrás: will.com