Am dat peste următorul tip de problemă. Este necesar să implementați un container de stocare a datelor care oferă următoarele funcționalități:
- inserați un element nou
- eliminați elementul după numărul de serie
- obțineți elementul după număr ordinal
- datele sunt stocate în formă sortată
Datele sunt adăugate și eliminate în mod constant, structura trebuie să asigure o viteză rapidă de funcționare. La început am încercat să implementez așa ceva folosind containere standard din std. Această cale nu a fost încununată de succes și a venit înțelegerea că trebuie să implementez ceva eu însumi. Singurul lucru care mi-a venit în minte a fost să folosiți un arbore de căutare binar. Pentru că îndeplinește cerința de inserare rapidă, ștergere și stocare a datelor în formă sortată. Tot ce rămâne este să descoperi cum să indexezi toate elementele și să recalculezi indicii atunci când arborele se schimbă.
struct node_s {
data_t data;
uint64_t weight; // вес узла
node_t *left;
node_t *right;
node_t *parent;
};Articolul va conține mai multe imagini și teorie decât cod. Codul poate fi vizualizat la linkul de mai jos.
Greutate
Pentru a realiza acest lucru, arborele a suferit o ușoară modificare, despre care au fost adăugate informații suplimentare greutate nodul. Greutatea nodului este numărul de descendenți ai acestui nod + 1 (greutatea unui singur element).
Funcția pentru obținerea greutății nodului:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}Greutatea foii este în mod corespunzător egală cu 0.
În continuare, să trecem la o reprezentare vizuală a unui exemplu de astfel de copac. negru cheia nodului va fi afișată în culoare (valoarea nu va fi afișată, deoarece nu este necesar), roșu - greutatea nodului, verde — indicele nodului.
Când arborele nostru este gol, greutatea lui este 0. Să îi adăugăm un element rădăcină:
Greutatea copacului devine 1, greutatea elementului rădăcină devine 1. Greutatea elementului rădăcină este greutatea copacului.
Să mai adăugăm câteva elemente:
De fiecare dată când se adaugă un nou element, coborâm nodurile și creștem contorul de greutate al fiecărui nod trecut. Când este creat un nou nod, i se atribuie o greutate 1. Dacă un nod cu o astfel de cheie există deja, atunci vom suprascrie valoarea și vom reveni la rădăcină, anulând modificările ponderilor tuturor nodurilor pe care le-am trecut.
Dacă un nod este eliminat, atunci coborâm și reducem greutățile nodurilor trecute.
Indici
Acum să trecem la cum să indexăm nodurile. Nodurile nu își stochează în mod explicit indexul, acesta este calculat pe baza ponderii nodurilor. Dacă și-au stocat indexul, atunci ar fi necesar O (n) timpul pentru a actualiza indecșii tuturor nodurilor după fiecare modificare a arborelui.
Să trecem la o reprezentare vizuală. Arborele nostru este gol, să adăugăm primul nod la el:
Primul nod are un index 0, iar acum sunt posibile 2 cazuri. În primul, indicele elementului rădăcină se va schimba, în al doilea nu se va schimba.
La rădăcină, subarborele din stânga cântărește 1.
Al doilea caz:
Indicele rădăcinii nu s-a schimbat deoarece greutatea subarborelui din stânga a rămas 0.
Indicele unui nod este calculat ca greutatea subarborelului său din stânga + numărul transmis de la părinte. Care este acest număr?, Acesta este contorul index, inițial este egal cu 0, deoarece rădăcina nu are părinte. Apoi totul depinde de unde coborâm la copilul stâng sau la cel drept. Dacă la stânga, atunci nu se adaugă nimic la contor. Dacă adăugăm indicele nodului curent la cel din dreapta.
De exemplu, cum se calculează indicele unui element cu cheia 8 (fiul drept al rădăcinii). Acesta este „Indexul rădăcinii” + „greutatea subarborelui stâng al nodului cu cheia 8” + „1” == 3 + 2 + 1 == 6
Indicele elementului cu cheia 6 va fi „Root Index” + 1 == 3 + 1 == 4
În consecință, este nevoie de timp pentru a obține și șterge un element după index O (jurnal n), deoarece pentru a obține elementul dorit trebuie mai întâi să-l găsim (coborâm de la rădăcină la acest element).
adâncime
Pe baza greutății, puteți calcula și adâncimea copacului. Necesar pentru echilibrare.
Pentru a face acest lucru, greutatea nodului curent trebuie să fie rotunjită la primul număr la puterea lui 2 care este mai mare sau egală cu greutatea dată și să ia logaritmul binar din acesta. Acest lucru ne va oferi adâncimea copacului, presupunând că este echilibrat. Arborele este echilibrat după introducerea unui nou element. Nu voi da o teorie despre cum să echilibrez copacii. Codurile sursă oferă o funcție de echilibrare.
Cod pentru conversia greutății în adâncime.
/*
* Возвращает первое число в степени 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));
}Rezultatele
- inserarea unui nou element are loc în O (jurnal n)
- ștergerea unui element după numărul de serie are loc în O (jurnal n)
- obţinerea unui element după numărul de serie are loc în O (jurnal n)
Viteză O (jurnal n) Plătim pentru faptul că toate datele sunt stocate în formă sortată.
Nu știu unde ar putea fi utilă o astfel de structură. Doar un puzzle pentru a înțelege din nou cum funcționează copacii. Vă mulțumim pentru atenție.
referințe
Proiectul conține date de testare pentru a verifica viteza de funcționare. Copacul se umple 1000000 elemente. Și există o ștergere, inserare și recuperare secvențială a elementelor 1000000 o singura data. Acesta este 3000000 operațiuni. Rezultatul s-a dovedit a fi destul de bun ~ 8 secunde.
Sursa: www.habr.com