Mi renkontis la jenan tipon de problemo. Estas necese efektivigi datuman stokan ujon, kiu provizas la jenan funkcion:
- enmeti novan elementon
- forigi elementon per seria numero
- akiri elementon per orda nombro
- datumoj estas konservitaj en ordigita formo
Datumoj estas konstante aldonitaj kaj forigitaj, la strukturo devas certigi rapidan operacion. Komence mi provis efektivigi tian aferon uzante normajn ujojn de horoj. Ĉi tiu vojo ne estis kronita per sukceso kaj venis la kompreno, ke mi bezonas efektivigi ion mem. La nura afero, kiu venis al la menso, estis uzi binaran serĉarbon. Ĉar ĝi plenumas la postulon de rapida enmeto, forigo kaj konservado de datumoj en ordigita formo. Restas nur eltrovi kiel indeksi ĉiujn elementojn kaj rekalkuli la indeksojn kiam la arbo ŝanĝiĝas.
struct node_s {
data_t data;
uint64_t weight; // вес узла
node_t *left;
node_t *right;
node_t *parent;
};La artikolo enhavos pli da bildoj kaj teorio ol kodo. La kodo videblas ĉe la suba ligilo.
pezo
Por atingi ĉi tion, la arbo spertis ioman modifon, pri kiu aldoniĝis pliaj informoj pezo nodo. La noda pezo estas nombro da posteuloj de ĉi tiu nodo + 1 (pezo de ununura elemento).
Funkcio por akiri nodan pezon:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}La pezo de la folio estas egale egala al 0.
Poste, ni transiru al vida reprezentado de ekzemplo de tia arbo. Nigra la noda ŝlosilo estos montrita en koloro (la valoro ne estos montrita, ĉar tio ne estas necesa), ruĝa - noda pezo, verda — noda indekso.
Kiam nia arbo estas malplena, ĝia pezo estas 0. Ni aldonu radikan elementon al ĝi:
La pezo de la arbo fariĝas 1, la pezo de la radika elemento fariĝas 1. La pezo de la radika elemento estas la pezo de la arbo.
Ni aldonu kelkajn pliajn elementojn:
Ĉiufoje kiam nova elemento estas aldonita, ni malsupreniras la nodojn kaj pliigas la pezon de ĉiu nodo preterpasita. Kiam nova nodo estas kreita, pezo estas asignita al ĝi 1. Se nodo kun tia ŝlosilo jam ekzistas, tiam ni anstataŭigos la valoron kaj reiros al la radiko, nuligante la ŝanĝojn en la pezoj de ĉiuj nodoj, kiujn ni pasis.
Se nodo estas forigita, tiam ni malsupreniras kaj malpliigas la pezojn de la preterpasitaj nodoj.
Indeksoj
Nun ni pluiru al kiel indeksi nodojn. Nodoj ne eksplicite stokas sian indekson, ĝi estas kalkulita surbaze de la pezo de la nodoj. Se ili stokis sian indekson, tiam ĝi estus postulata Li) tempo ĝisdatigi la indeksojn de ĉiuj nodoj post ĉiu ŝanĝo en la arbo.
Ni transiru al vida reprezentado. Nia arbo estas malplena, ni aldonu la unuan nodon al ĝi:
La unua nodo havas indekson 0, kaj nun 2 kazoj eblas. En la unua, la indekso de la radika elemento ŝanĝiĝos, en la dua ĝi ne ŝanĝiĝos.
Ĉe la radiko, la maldekstra subarbo pezas 1.
Dua kazo:
La indekso de la radiko ne ŝanĝiĝis ĉar la pezo de ĝia maldekstra subarbo restis 0.
La indekso de nodo estas kalkulita kiel la pezo de ĝia maldekstra subarbo + la nombro pasita de la gepatro. Kio estas ĉi tiu nombro?, Ĉi tio estas la indeksa nombrilo, komence ĝi egalas 0, ĉar la radiko ne havas gepatron. Tiam ĉio dependas de kie ni malsupreniras al la maldekstra infano aŭ al la dekstra. Se maldekstre, tiam nenio estas aldonita al la vendotablo. Se ni aldonas la indekson de la nuna nodo al la dekstra.
Ekzemple, kiel la indekso de elemento kun ŝlosilo 8 (la dekstra infano de la radiko) estas kalkulita. Ĉi tio estas "Radika Indekso" + "pezo de maldekstra subarbo de nodo kun ŝlosilo 8" + "1" == 3 + 2 + 1 == 6
La indekso de la elemento kun ŝlosilo 6 estos "Root Index" + 1 == 3 + 1 == 4
Sekve, necesas tempo por akiri kaj forigi elementon per indekso O (log n), ĉar por ricevi la deziratan elementon ni unue devas trovi ĝin (malsupreniri de la radiko al ĉi tiu elemento).
Profundo
Surbaze de la pezo, vi ankaŭ povas kalkuli la profundon de la arbo. Necesas por ekvilibrigi.
Por fari tion, la pezo de la nuna nodo devas esti rondigita al la unua nombro al la potenco de 2 kiu estas pli granda ol aŭ egala al la donita pezo kaj preni la binaran logaritmon de ĝi. Ĉi tio donos al ni la profundon de la arbo, supozante ke ĝi estas ekvilibra. La arbo estas ekvilibrigita post enigo de nova elemento. Mi ne donos teorion pri kiel ekvilibrigi arbojn. La fontkodoj disponigas ekvilibran funkcion.
Kodo por konverti pezon al profundo.
/*
* Возвращает первое число в степени 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));
}Rezultoj
- enmeto de nova elemento okazas en O (log n)
- forigo de elemento per seria numero okazas en O (log n)
- akiri elementon per seria numero okazas en O (log n)
Rapido O (log n) Ni pagas pro tio, ke ĉiuj datumoj estas konservitaj en ordigita formo.
Mi ne scias kie tia strukturo povus esti utila. Nur enigmo por denove kompreni kiel funkcias arboj. Dankon pro via atento.
referencoj
La projekto enhavas testajn datumojn por kontroli la rapidecon de operacio. La arbo pleniĝas 1000000 elementoj. Kaj estas sinsekva forigo, enmeto kaj retrovo de elementoj 1000000 unufoje. Tio estas 3000000 operacioj. La rezulto montriĝis sufiĉe bona ~ 8 sekundoj.
fonto: www.habr.com