Em vaig trobar amb el següent tipus de problema. És necessari implementar un contenidor d'emmagatzematge de dades que proporcioni la següent funcionalitat:
- inseriu un element nou
- eliminar l'element pel número de sèrie
- obtenir element per nombre ordinal
- les dades s'emmagatzemen en forma ordenada
Les dades s'afegeixen i s'eliminen constantment, l'estructura ha de garantir una velocitat de funcionament ràpida. Al principi vaig intentar implementar una cosa així utilitzant contenidors estàndard de hores. Aquest camí no va ser coronat amb èxit i va arribar la comprensió que necessitava implementar alguna cosa jo mateix. L'únic que em va venir al cap va ser utilitzar un arbre de cerca binari. Perquè compleix el requisit de ràpida inserció, supressió i emmagatzematge de dades en forma ordenada. Només queda esbrinar com indexar tots els elements i tornar a calcular els índexs quan l'arbre canvia.
struct node_s {
data_t data;
uint64_t weight; // вес узла
node_t *left;
node_t *right;
node_t *parent;
};L'article contindrà més imatges i teoria que codi. El codi es pot veure a l'enllaç següent.
Вес
Per aconseguir-ho, l'arbre va sofrir una lleugera modificació, s'hi va afegir informació addicional pes node. El pes del node és nombre de descendents d'aquest node + 1 (pes d'un sol element).
Funció per obtenir el pes del node:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}El pes del full és corresponentment igual a 0.
A continuació, passem a una representació visual d'un exemple d'aquest arbre. Negre la clau del node es mostrarà en color (el valor no es mostrarà, ja que això no és necessari), vermell - pes del nus, verd - índex de nodes.
Quan el nostre arbre està buit, el seu pes és 0. Afegim-hi un element arrel:
El pes de l'arbre es converteix en 1, el pes de l'element arrel es converteix en 1. El pes de l'element arrel és el pes de l'arbre.
Afegim uns quants elements més:
Cada vegada que s'afegeix un nou element, baixem pels nodes i augmentem el comptador de pes de cada node passat. Quan es crea un nou node, se li assigna un pes 1. Si ja existeix un node amb aquesta clau, sobreescriurem el valor i tornarem a l'arrel, cancel·lant els canvis en els pesos de tots els nodes que hem passat.
Si s'està eliminant un node, baixem i disminuïm els pesos dels nodes passats.
Índexs
Ara passem a com indexar els nodes. Els nodes no emmagatzemen explícitament el seu índex, es calcula en funció del pes dels nodes. Si emmagatzemen el seu índex, seria necessari O (n) temps per actualitzar els índexs de tots els nodes després de cada canvi a l'arbre.
Passem a una representació visual. El nostre arbre està buit, afegim-hi el primer node:
El primer node té un índex 0, i ara són possibles 2 casos. En el primer, l'índex de l'element arrel canviarà, en el segon no canviarà.
A l'arrel, el subarbre esquerre pesa 1.
Segon cas:
L'índex de l'arrel no va canviar perquè el pes del seu subarbre esquerre es va mantenir en 0.
L'índex d'un node es calcula com el pes del seu subarbre esquerre + el nombre passat del pare. Quin és aquest número?, Aquest és el comptador d'índex, inicialment és igual a 0, perquè l'arrel no té cap pare. Aleshores tot depèn d'on baixem al nen esquerre o al dret. Si està a l'esquerra, no s'afegeix res al comptador. Si afegim l'índex del node actual al dret.
Per exemple, com es calcula l'índex d'un element amb la clau 8 (el fill dret de l'arrel). Això és "índex arrel" + "pes del subarbre esquerre del node amb la clau 8" + "1" == 3 + 2 + 1 == 6
L'índex de l'element amb la clau 6 serà "Índex arrel" + 1 == 3 + 1 == 4
En conseqüència, es necessita temps per obtenir i eliminar un element per índex O (registre n), perquè per aconseguir l'element desitjat primer hem de trobar-lo (baixar de l'arrel a aquest element).
Profunditat
A partir del pes, també podeu calcular la profunditat de l'arbre. Necessari per a l'equilibri.
Per fer-ho, s'ha d'arrodonir el pes del node actual al primer nombre a la potència de 2 que és més gran o igual al pes donat i treure'n el logaritme binari. Això ens donarà la profunditat de l'arbre, suposant que estigui equilibrat. L'arbre s'equilibra després d'inserir un nou element. No donaré una teoria sobre com equilibrar els arbres. Els codis font proporcionen una funció d'equilibri.
Codi per convertir el pes a la profunditat.
/*
* Возвращает первое число в степени 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));
}Resultats de
- es produeix la inserció d'un nou element O (registre n)
- l'eliminació d'un element pel número de sèrie es produeix a O (registre n)
- l'obtenció d'un element per número de sèrie es produeix a O (registre n)
Velocitat O (registre n) Paguem pel fet que totes les dades s'emmagatzemen en forma ordenada.
No sé on pot ser útil aquesta estructura. Només un trencaclosques per entendre una vegada més com funcionen els arbres. Gràcies per la vostra atenció.
Referències
El projecte conté dades de prova per comprovar la velocitat de funcionament. L'arbre s'està omplint 1000000 elements. I hi ha una supressió, inserció i recuperació seqüencials d'elements 1000000 un cop. Això és 3000000 operacions. El resultat va resultar ser força bo ~ 8 segons.
Font: www.habr.com