Indexovaný binárny strom

Narazil som na nasledujúci typ problému. Je potrebné implementovať kontajner na ukladanie údajov, ktorý poskytuje nasledujúce funkcie:

• vložte nový prvok
• odstráňte prvok podľa sériového čísla
• získať prvok podľa poradového čísla
• údaje sú uložené v triedenej forme

Dáta sa neustále pridávajú a odstraňujú, štruktúra musí zabezpečiť vysokú rýchlosť prevádzky. Najprv som sa pokúsil implementovať takúto vec pomocou štandardných kontajnerov z std. Táto cesta nebola korunovaná úspechom a prišlo pochopenie, že potrebujem niečo realizovať sám. Jediné, čo mi napadlo, bolo použiť binárny vyhľadávací strom. Pretože spĺňa požiadavku na rýchle vkladanie, mazanie a ukladanie dát v triedenej podobe. Zostáva len vymyslieť, ako indexovať všetky prvky a prepočítať indexy pri zmene stromu.

struct node_s {    
    data_t data;

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

    node_t *left;
    node_t *right;

    node_t *parent;
};

Článok bude obsahovať viac obrázkov a teórie ako kódu. Kód si môžete pozrieť na nižšie uvedenom odkaze.

Hmotnosť

Aby sa to dosiahlo, strom prešiel miernou úpravou, boli pridané ďalšie informácie o hmotnosť uzol. Hmotnosť uzla je počet potomkov tohto uzla + 1 (hmotnosť jedného prvku).

Funkcia na získanie hmotnosti uzla:

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

    return 0;
}

Hmotnosť listu sa zodpovedajúcim spôsobom rovná 0.

Ďalej prejdime k vizuálnemu znázorneniu príkladu takéhoto stromu. čierna kľúč uzla sa zobrazí farebne (hodnota sa nezobrazí, pretože to nie je potrebné), červená - hmotnosť uzla, zelený — index uzla.

Keď je náš strom prázdny, jeho hmotnosť je 0. Pridajme k nemu koreňový prvok:

Hmotnosť stromu sa stane 1, hmotnosť koreňového prvku sa stane 1. Hmotnosť koreňového prvku je hmotnosť stromu.

Pridajme ešte niekoľko prvkov:

Zakaždým, keď sa pridá nový prvok, ideme po uzloch nadol a zvyšujeme počítadlo hmotnosti každého prejdeného uzla. Keď sa vytvorí nový uzol, priradí sa mu váha 1. Ak uzol s takýmto kľúčom už existuje, potom hodnotu prepíšeme a vrátime sa späť do koreňa, pričom zrušíme zmeny váh všetkých uzlov, ktoré sme prešli.
Ak sa uzol odstraňuje, potom ideme dole a znížime váhy prechádzajúcich uzlov.

Indexy

Teraz prejdime k tomu, ako indexovať uzly. Uzly explicitne neukladajú svoj index, počíta sa na základe hmotnosti uzlov. Ak by uložili svoj index, potom by sa to vyžadovalo O (n) čas na aktualizáciu indexov všetkých uzlov po každej zmene v strome.
Prejdime k vizuálnej reprezentácii. Náš strom je prázdny, pridajme k nemu 1. uzol:

Prvý uzol má index 0, a teraz sú možné 2 prípady. V prvom sa index koreňového prvku zmení, v druhom sa nezmení.

V koreni ľavý podstrom váži 1.

Druhý prípad:

Index koreňa sa nezmenil, pretože váha jeho ľavého podstromu zostala 0.

Index uzla sa vypočíta ako váha jeho ľavého podstromu + číslo odovzdané z rodiča. Čo je toto číslo?, Toto je počítadlo indexu, na začiatku sa rovná 0, pretože koreň nemá rodiča. Potom všetko závisí od toho, kam sa dostaneme k ľavému dieťaťu alebo k pravému. Ak doľava, do počítadla sa nepridáva nič. Ak pridáme index aktuálneho uzla k správnemu.

Napríklad, ako sa vypočíta index prvku s kľúčom 8 (pravý potomok koreňa). Toto je "Root Index" + "váha ľavého podstromu uzla s kľúčom 8" + "1" == 3 + 2 + 1 == 6
Index prvku s kľúčom 6 bude "Root Index" + 1 == 3 + 1 == 4

V súlade s tým trvá získanie a odstránenie prvku podľa indexu čas O (log n), pretože aby sme získali požadovaný prvok, musíme ho najprv nájsť (prejsť od koreňa k tomuto prvku).

hĺbka

Na základe hmotnosti môžete vypočítať aj hĺbku stromu. Nevyhnutné na vyváženie.
Aby ste to dosiahli, hmotnosť aktuálneho uzla sa musí zaokrúhliť na prvé číslo na mocninu 2, ktorá je väčšia alebo rovná danej hmotnosti, a vziať z nej binárny logaritmus. To nám dá hĺbku stromu za predpokladu, že je vyvážený. Strom sa po vložení nového prvku vyrovná. Nebudem uvádzať teóriu o tom, ako vyvážiť stromy. Zdrojové kódy poskytujú funkciu vyrovnávania.

Kód pre prevod hmotnosti na hĺbku.

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

Výsledky

• dôjde k vloženiu nového prvku O (log n)
• k vymazaniu prvku podľa sériového čísla dochádza v O (log n)
• získanie prvku podľa sériového čísla nastáva v O (log n)

Rýchlosť O (log n) Platíme za to, že všetky dáta sú uložené v triedenej podobe.

Neviem, kde by takáto štruktúra mohla byť užitočná. Len hádanka, aby ste opäť pochopili, ako stromy fungujú. Ďakujem za tvoju pozornosť.

referencie

• Zdrojový kód stromu

Projekt obsahuje testovacie údaje na kontrolu rýchlosti prevádzky. Strom sa zapĺňa 1000000 prvkov. A tam je postupné mazanie, vkladanie a vyhľadávanie prvkov 1000000 raz. Teda 3000000 operácií. Výsledok sa ukázal byť celkom dobrý ~ 8 sekúnd.

Zdroj: hab.com