Ech koum op déi folgend Zort vu Problem. Et ass néideg en Datelagerbehälter ëmzesetzen deen déi folgend Funktionalitéit ubitt:
- neit Element anzeginn
- ewechzehuelen Element vun Serien Zuel
- kréien Element vun Uerdnung Zuel
- Daten ginn a sortéierter Form gespäichert
D'Donnéeë ginn dauernd bäigefüügt a geläscht, d'Struktur muss séier Operatiounsgeschwindegkeet garantéieren. Am Ufank hunn ech probéiert esou eng Saach mat Standardbehälter aus ze realiséieren Stonnen. Dëse Wee war net mat Erfolleg gekréint an d'Verständnis koum datt ech eppes selwer muss ëmsetzen. Dat eenzegt wat an de Kapp koum war e binäre Sichbaum ze benotzen. Well et entsprécht der Fuerderung vun enger schneller Insertion, Läschung a Lagerung vun Daten a sortéierter Form. Alles wat bleift ass erauszefannen wéi all d'Elementer indexéiert ginn an d'Indeze nei berechnen wann de Bam ännert.
struct node_s {
data_t data;
uint64_t weight; // вес узла
node_t *left;
node_t *right;
node_t *parent;
};Den Artikel enthält méi Biller an Theorie wéi Code. De Code kann um Link hei ënnen gekuckt ginn.
Gewiicht
Fir dëst z'erreechen, huet de Bam eng liicht Modifikatioun gemaach, zousätzlech Informatioune goufe bäigefüügt Gewiicht node. Node Gewiicht ass Zuel vun Nokommen vun dësem Node + 1 (Gewiicht vun engem eenzegen Element).
Funktioun fir Node Gewiicht ze kréien:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}D'Gewiicht vum Blat ass entspriechend gläich wéi 0.
Als nächst wäerte mir op eng visuell Representatioun vun engem Beispill vun esou engem Bam goen. Schwaarz den Node Schlëssel gëtt a Faarf ugewisen (de Wäert gëtt net gewisen, well dëst net néideg ass), rout - Knot Gewiicht, gréng - Node Index.
Wann eise Bam eidel ass, ass säi Gewiicht 0. Loosst eis e Wuerzelelement derbäi addéieren:
D'Gewiicht vum Bam gëtt 1, d'Gewiicht vum Wuerzelelement gëtt 1. D'Gewiicht vum Wuerzelelement ass d'Gewiicht vum Bam.
Loosst eis e puer méi Elementer derbäi:
All Kéier wann en neit Element bäigefüügt gëtt, gi mir d'Noden erof an erhéijen de Gewiichtszähler vun all Node passéiert. Wann en neie Knuet erstallt gëtt, gëtt et e Gewiicht zougewisen 1. Wann e Knuet mat sou engem Schlëssel schonn existéiert, da wäerte mir de Wäert iwwerschreiwe an zréck op d'Wuerzel goen, d'Verännerungen an de Gewiichter vun all Noden annuléieren, déi mir passéiert hunn.
Wann e Node geläscht gëtt, da gi mir erof a reduzéieren d'Gewiichter vun de passéierten Noden.
Indexen
Loosst eis elo weidergoen wéi d'Noden indexéieren. Noden späicheren hiren Index net explizit, et gëtt berechent op Basis vum Gewiicht vun den Noden. Wa se hiren Index gespäichert hunn, da wier et néideg O (n) Zäit fir d'Indexe vun all Noden no all Changement am Bam ze aktualiséieren.
Loosst eis op eng visuell Representatioun goen. Eise Bam ass eidel, loosst eis den 1. Node derbäi setzen:
Den éischte Node huet en Index 0, an elo sinn 2 Fäll méiglech. An der éischter ännert den Index vum Rootelement, an der zweeter wäert et net änneren.
An der Wuerzel weegt de lénksen Ënnerbaum 1.
Zweet Fall:
Den Index vun der Wuerzel huet sech net geännert well d'Gewiicht vu sengem lénksen Ënnerbaum 0 blouf.
Den Index vun engem Node gëtt berechent wéi d'Gewiicht vu sengem lénksen Ënnerbaum + d'Zuel, déi vum Elterendeel passéiert ass. Wat ass dës Zuel?, Dëst ass den Indexzähler, am Ufank ass et gläich wéi 0, well d'Wurzel huet keen Elterendeel. Dann hänkt alles dovun of, wou mer op dat lénkst Kand erofgoen oder dat richtegt. Wann lénks, da gëtt näischt op de Comptoir bäigefüügt. Wa mir den Index vum aktuellen Node op de richtege addéieren.
Zum Beispill, wéi den Index vun engem Element mam Schlëssel 8 (de richtege Kand vun der Wuerzel) berechent gëtt. Dëst ass "Root Index" + "Gewiicht vum lénksen Subtree vum Node mam Schlëssel 8" + "1" == 3 + 2 + 1 == 6
Den Index vum Element mam Schlëssel 6 ass "Root Index" + 1 == 3 + 1 == 4
Deementspriechend brauch et Zäit fir en Element per Index ze kréien an ze läschen O (aloggen n), well fir dat gewënscht Element ze kréien, musse mir et als éischt fannen (vun der Wuerzel erof op dëst Element erofgoen).
Depth
Baséierend op d'Gewiicht kënnt Dir och d'Tiefe vum Bam berechnen. Néideg fir Balance.
Fir dëst ze maachen, muss d'Gewiicht vum aktuellen Node op déi éischt Nummer op d'Kraaft vun 2 ofgerënnt ginn, déi méi grouss ass wéi oder gläich wéi dat gegebene Gewiicht an de binäre Logarithmus dovun huelen. Dëst wäert eis d'Tiefe vum Bam ginn, unzehuelen datt et ausgeglach ass. De Bam gëtt ausgeglach nodeems en neit Element agefouert gouf. Ech ginn net eng Theorie iwwer wéi d'Beem ze balanséieren. D'Quellcoden bidden eng Balancefunktioun.
Code fir Gewiicht ze Déift Ëmwandlung.
/*
* Возвращает первое число в степени 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));
}Resultater
- Aféierung vun engem neien Element geschitt an O (aloggen n)
- läschen vun engem Element duerch Serien Zuel geschitt an O (aloggen n)
- en Element duerch d'Seriennummer ze kréien geschitt an O (aloggen n)
Speed O (aloggen n) Mir bezuelen fir d'Tatsaach, datt all Daten an zortéiert Form gespäichert ass.
Ech weess net wou esou eng Struktur nëtzlech ka sinn. Just e Puzzel fir nach eng Kéier ze verstoen wéi Beem funktionnéieren. Merci fir är Opmierksamkeet.
Referenze
De Projet enthält Testdaten fir d'Vitesse vun der Operatioun ze kontrolléieren. De Bam fëllt sech op 1000000 Elementer. An et gëtt eng sequenziell Läschung, Aféierung an Erhuelung vun Elementer 1000000 eemol. Dat ass 3000000 Operatiounen. D'Resultat ass zimlech gutt ~ 8 Sekonnen.
Source: will.com