Susidūriau su tokio tipo problema. Būtina įdiegti duomenų saugojimo konteinerį, kuris teikia šias funkcijas:
- įterpti naują elementą
- pašalinti elementą pagal serijos numerį
- gauti elementą pagal eilės skaičių
- duomenys saugomi surūšiuota forma
Duomenys nuolat pridedami ir šalinami, struktūra turi užtikrinti greitą veikimo greitį. Iš pradžių bandžiau įgyvendinti tokį dalyką naudodamas standartinius konteinerius iš standartinis. Šio kelio nevainikavo sėkmė ir atėjo supratimas, kad reikia pačiam kažką įgyvendinti. Vienintelis dalykas, kuris atėjo į galvą, buvo naudoti dvejetainį paieškos medį. Kadangi jis atitinka greito duomenų įterpimo, ištrynimo ir saugojimo surūšiuota forma reikalavimą. Belieka tik sugalvoti, kaip indeksuoti visus elementus ir perskaičiuoti indeksus pasikeitus medžiui.
struct node_s {
data_t data;
uint64_t weight; // вес узла
node_t *left;
node_t *right;
node_t *parent;
};Straipsnyje bus daugiau nuotraukų ir teorijos nei kodo. Kodą galite peržiūrėti žemiau esančioje nuorodoje.
svoris
Norint tai pasiekti, medis buvo šiek tiek modifikuotas, apie jį buvo pridėta papildomos informacijos svoris mazgas. Mazgo svoris yra šio mazgo palikuonių skaičius + 1 (vieno elemento svoris).
Mazgo svorio nustatymo funkcija:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}Lapo svoris atitinkamai lygus 0.
Toliau pereikime prie vaizdinio tokio medžio pavyzdžio vaizdavimo. Juoda mazgo raktas bus rodomas spalvotai (vertė nebus rodoma, nes tai nėra būtina), raudonas - mazgo svoris, žalias - mazgo indeksas.
Kai mūsų medis tuščias, jo svoris yra 0. Pridėkime prie jo šaknies elementą:
Medžio svoris tampa 1, šaknies elemento svoris tampa 1. Šaknies elemento svoris yra medžio svoris.
Pridėkime dar kelis elementus:
Kiekvieną kartą, kai pridedamas naujas elementas, mes nusileidžiame mazgais ir padidiname kiekvieno praeito mazgo svorio skaitiklį. Sukūrus naują mazgą, jam priskiriamas svoris 1. Jei mazgas su tokiu raktu jau yra, tada perrašysime reikšmę ir grįšime į šaknį, atšaukdami visų perėjusių mazgų svorio pokyčius.
Jei mazgas pašalinamas, einame žemyn ir sumažiname perduotų mazgų svorį.
Indeksai
Dabar pereikime prie mazgų indeksavimo. Mazgai aiškiai nesaugo savo indekso, jis apskaičiuojamas pagal mazgų svorį. Jei jie saugotų savo indeksą, tada jis būtų reikalingas O (n) laikas atnaujinti visų mazgų indeksus po kiekvieno medžio pakeitimo.
Pereikime prie vizualinio vaizdavimo. Mūsų medis tuščias, pridėkime prie jo 1 mazgą:
Pirmasis mazgas turi indeksą 0, o dabar galimi 2 atvejai. Pirmajame šakninio elemento indeksas pasikeis, antruoju – nesikeis.
Šaknyje kairysis pomedis sveria 1.
Antras atvejis:
Šaknies indeksas nepasikeitė, nes jos kairiojo pomedžio svoris liko 0.
Mazgo indeksas apskaičiuojamas kaip jo kairiojo pomedžio svoris + skaičius, perduotas iš pirminio. Kas yra šis skaičius?, Tai yra indekso skaitiklis, iš pradžių jis lygus 0, nes šaknis neturi tėvų. Tada viskas priklauso nuo to, kur nusileisime iki kairiojo vaiko ar dešiniojo. Jei į kairę, tada prie skaitiklio niekas nepridedama. Jei prie dešiniojo pridėsime dabartinio mazgo indeksą.
Pavyzdžiui, kaip apskaičiuojamas elemento su 8 raktu (dešiniuoju šaknies antruoju) indeksas. Tai yra "Šakninis indeksas" + "mazgo kairiojo pomedžio svoris su raktu 8" + "1" == 3 + 2 + 1 == 6
Elemento su 6 klavišu indeksas bus "Šakninis indeksas" + 1 == 3 + 1 == 4
Atitinkamai, norint gauti ir ištrinti elementą pagal indeksą, reikia laiko O (log n), nes norėdami gauti norimą elementą, pirmiausia turime jį rasti (nusileisti nuo šaknies iki šio elemento).
Gylis
Pagal svorį taip pat galite apskaičiuoti medžio gylį. Būtinas balansavimui.
Norėdami tai padaryti, dabartinio mazgo svorį reikia suapvalinti iki pirmojo skaičiaus iki 2 laipsnio, kuris yra didesnis arba lygus nurodytam svoriui, ir iš jo paimti dvejetainį logaritmą. Tai suteiks mums medžio gylį, darant prielaidą, kad jis yra subalansuotas. Medis subalansuojamas įdėjus naują elementą. Aš nepateiksiu teorijos, kaip subalansuoti medžius. Šaltinio kodai suteikia balansavimo funkciją.
Kodas svorio konvertavimui į gylį.
/*
* Возвращает первое число в степени 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));
}rezultatai
- įterpiamas naujas elementas O (log n)
- elementas ištrinamas pagal serijos numerį O (log n)
- elemento gavimas pagal serijos numerį įvyksta O (log n)
Greitis O (log n) Mokame už tai, kad visi duomenys yra saugomi surūšiuota forma.
Nežinau, kur tokia struktūra gali būti naudinga. Tiesiog galvosūkis, norint dar kartą suprasti, kaip veikia medžiai. Ačiū už dėmesį.
Nuorodos
Projekte yra bandymų duomenys, skirti patikrinti veikimo greitį. Medis pildosi 1000000 elementai. Ir yra nuoseklus elementų trynimas, įterpimas ir gavimas 1000000 kartą. Tai yra 3000000 operacijos. Rezultatas gavosi visai geras ~ 8 sek.
Šaltinis: www.habr.com