Indexovaný binární strom

Narazil jsem na následující typ problému. Je nutné implementovat kontejner pro ukládání dat, který poskytuje následující funkce:

• vložit nový prvek
• odstraňte prvek podle sériového čísla
• získat prvek podle pořadového čísla
• data jsou uložena v setříděné podobě

Data jsou neustále přidávána a odebírána, struktura musí zajistit vysokou rychlost provozu. Nejprve jsem se pokusil implementovat takovou věc pomocí standardních kontejnerů z std. Tato cesta nebyla korunována úspěchem a přišlo pochopení, že potřebuji něco realizovat sám. Jediné, co mě napadlo, bylo použít binární vyhledávací strom. Protože splňuje požadavek na rychlé vkládání, mazání a ukládání dat v setříděné podobě. Zbývá jen vymyslet, jak indexovat všechny prvky a přepočítat indexy při změně stromu.

struct node_s {    
    data_t data;

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

    node_t *left;
    node_t *right;

    node_t *parent;
};

Článek bude obsahovat více obrázků a teorie než kódu. Kód lze zobrazit na odkazu níže.

Hmotnost

Aby toho bylo dosaženo, strom prošel mírnou úpravou, byly přidány další informace o hmotnost uzel. Hmotnost uzlu je počet potomků tohoto uzlu + 1 (hmotnost jednoho prvku).

Funkce pro získání hmotnosti uzlu:

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

    return 0;
}

Hmotnost listu je odpovídajícím způsobem rovna 0.

Dále přejdeme k vizuálnímu znázornění příkladu takového stromu. Černá klíč uzlu se zobrazí barevně (hodnota se nezobrazí, protože to není nutné), červená - hmotnost uzlu, zelený — index uzlu.

Když je náš strom prázdný, jeho váha je 0. Přidejme k němu kořenový prvek:

Hmotnost stromu se stane 1, hmotnost kořenového prvku se stane 1. Hmotnost kořenového prvku je hmotnost stromu.

Přidejme ještě několik prvků:

Pokaždé, když je přidán nový prvek, sjíždíme uzly dolů a zvyšujeme počítadlo váhy každého prošlého uzlu. Když je vytvořen nový uzel, je mu přiřazena váha 1. Pokud uzel s takovým klíčem již existuje, pak hodnotu přepíšeme a vrátíme se zpět ke kořenu, přičemž zrušíme změny vah všech uzlů, které jsme prošli.
Pokud je uzel odstraňován, pak jdeme dolů a snižujeme váhy předávaných uzlů.

Indexy

Nyní přejdeme k tomu, jak indexovat uzly. Uzly explicitně neukládají svůj index, počítá se na základě váhy uzlů. Pokud by svůj index uložili, bylo by to vyžadováno O (n) čas na aktualizaci indexů všech uzlů po každé změně ve stromu.
Přejděme k vizuální reprezentaci. Náš strom je prázdný, přidejte k němu 1. uzel:

První uzel má index 0a nyní jsou možné 2 případy. V prvním se index kořenového prvku změní, ve druhém se nezmění.

U kořene váží levý podstrom 1.

Druhý případ:

Index kořene se nezměnil, protože váha jeho levého podstromu zůstala 0.

Index uzlu se vypočítá jako váha jeho levého podstromu + číslo předané od rodiče. Co je toto číslo?, Toto je počítadlo indexu, zpočátku se rovná 0, protože kořen nemá rodiče. Pak už vše záleží na tom, kam sestoupíme k levému dítěti nebo k pravému. Pokud doleva, pak se do počítadla nic nepřidává. Přidáme-li index aktuálního uzlu ke správnému.

Například, jak se vypočítá index prvku s klíčem 8 (pravý potomek kořene). Toto je "kořenový index" + "váha levého podstromu uzlu s klíčem 8" + "1" == 3 + 2 + 1 == 6
Index prvku s klíčem 6 bude "Root Index" + 1 == 3 + 1 == 4

V souladu s tím trvá získání a odstranění prvku podle indexu čas O (log n), protože abychom získali požadovaný prvek, musíme jej nejprve najít (jít dolů od kořene k tomuto prvku).

Hloubka

Na základě hmotnosti můžete vypočítat i hloubku stromu. Nezbytné pro vyvážení.
K tomu je třeba zaokrouhlit váhu aktuálního uzlu na první číslo na mocninu 2, která je větší nebo rovna dané hmotnosti, a vzít z ní binární logaritmus. To nám dá hloubku stromu, za předpokladu, že je vyvážený. Po vložení nového prvku se strom vyrovná. Nebudu uvádět teorii o tom, jak vyvážit stromy. Zdrojové kódy poskytují funkci vyvažování.

Kód pro převod hmotnosti na hloubku.

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

• dojde k vložení nového prvku O (log n)
• dojde k odstranění prvku podle sériového čísla O (log n)
• k získání prvku podle sériového čísla dochází v O (log n)

Rychlost O (log n) Platíme za to, že všechna data jsou uložena v setříděné podobě.

Nevím, kde by taková struktura mohla být užitečná. Jen hádanka, abyste znovu pochopili, jak stromy fungují. Děkuji za pozornost.

reference

• Zdrojový kód stromu

Projekt obsahuje testovací data pro kontrolu rychlosti provozu. Strom se plní 1000000 Prvky. A dochází k postupnému mazání, vkládání a načítání prvků 1000000 jednou. To znamená 3000000 operace. Výsledek se ukázal být docela dobrý ~ 8 sekund.

Zdroj: www.habr.com