Es saskāros ar šāda veida problēmu. Ir nepieciešams ieviest datu uzglabāšanas konteineru, kas nodrošina šādas funkcijas:
- ievietot jaunu elementu
- noņemt elementu pēc sērijas numura
- iegūt elementu pēc kārtas skaitļa
- dati tiek glabāti sakārtotā veidā
Dati tiek nepārtraukti pievienoti un noņemti, struktūrai jānodrošina ātrs darbības ātrums. Sākumā es mēģināju ieviest šādu lietu, izmantojot standarta konteinerus no std. Šis ceļš nav vainagojies panākumiem un nāca sapratne, ka vajag kaut ko īstenot pašam. Vienīgais, kas ienāca prātā, bija izmantot bināro meklēšanas koku. Jo tas atbilst prasībai par ātru datu ievietošanu, dzēšanu un glabāšanu sakārtotā veidā. Atliek tikai izdomāt, kā indeksēt visus elementus un pārrēķināt indeksus, kad koks mainās.
struct node_s {
data_t data;
uint64_t weight; // вес узла
node_t *left;
node_t *right;
node_t *parent;
};Rakstā būs vairāk attēlu un teorijas nekā koda. Kodu var apskatīt zemāk esošajā saitē.
Svars
Lai to panāktu, koks tika nedaudz pārveidots, tika pievienota papildu informācija svaru mezgls. Mezgla svars ir šī mezgla pēcnācēju skaits + 1 (viena elementa svars).
Funkcijas mezgla svara iegūšanai:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}Loksnes svars ir attiecīgi vienāds ar 0.
Tālāk pāriesim pie šāda koka piemēra vizuāla attēlojuma. Melns mezgla atslēga tiks parādīta krāsā (vērtība netiks rādīta, jo tas nav nepieciešams), sarkans - mezgla svars, zaļš — mezglu indekss.
Kad mūsu koks ir tukšs, tā svars ir 0. Pievienosim tam saknes elementu:
Koka svars kļūst par 1, saknes elementa svars kļūst par 1. Saknes elementa svars ir koka svars.
Pievienosim vēl dažus elementus:
Katru reizi, kad tiek pievienots jauns elements, mēs ejam uz leju pa mezgliem un palielinām katra nodotā mezgla svara skaitītāju. Kad tiek izveidots jauns mezgls, tam tiek piešķirts svars 1. Ja mezgls ar šādu atslēgu jau pastāv, mēs pārrakstīsim vērtību un atgriezīsimies līdz saknei, atceļot visu mūsu nodoto mezglu svaru izmaiņas.
Ja mezgls tiek noņemts, mēs ejam uz leju un samazinām nodoto mezglu svaru.
Indeksi
Tagad pāriesim pie mezglu indeksēšanas. Mezgli nepārprotami neuzglabā savu indeksu, tas tiek aprēķināts, pamatojoties uz mezglu svaru. Ja viņi saglabātu savu indeksu, tad tas būtu vajadzīgs O (n) laiks atjaunināt visu mezglu indeksus pēc katrām izmaiņām kokā.
Pāriesim pie vizuālā attēlojuma. Mūsu koks ir tukšs, pievienosim tam 1. mezglu:
Pirmajā mezglā ir indekss 0, un tagad ir iespējami 2 gadījumi. Pirmajā saknes elementa indekss mainīsies, otrajā tas nemainīsies.
Saknē kreisais apakškoks sver 1.
Otrais gadījums:
Saknes indekss nemainījās, jo tās kreisā apakškoka svars palika 0.
Mezgla indekss tiek aprēķināts kā tā kreisā apakškoka svars + no vecāka nodotais skaitlis. Kāds ir šis skaitlis?, Šis ir indeksa skaitītājs, sākotnēji tas ir vienāds ar 0, jo saknei nav vecāku. Tad viss ir atkarīgs no tā, kur mēs nolaižamies pie kreisā bērna vai labā. Ja pa kreisi, tad skaitītājam nekas netiek pievienots. Ja mēs pievienojam pašreizējā mezgla indeksu pareizajam mezglam.
Piemēram, kā tiek aprēķināts elementa indekss ar atslēgu 8 (saknes labais bērns). Tas ir "Saknes indekss" + "mezgla kreisā apakškoka svars ar atslēgu 8" + "1" == 3 + 2 + 1 == 6
Elementa indekss ar taustiņu 6 būs "Saknes indekss" + 1 == 3 + 1 == 4
Attiecīgi ir nepieciešams laiks, lai iegūtu un izdzēstu elementu pēc indeksa O (log n), jo, lai iegūtu vēlamo elementu, vispirms tas ir jāatrod (no saknes jāiet uz leju līdz šim elementam).
Dziļums
Pamatojoties uz svaru, varat arī aprēķināt koka dziļumu. Nepieciešams līdzsvarošanai.
Lai to izdarītu, pašreizējā mezgla svars ir jānoapaļo līdz pirmajam skaitlim līdz pakāpei 2, kas ir lielāks vai vienāds ar doto svaru, un jāņem no tā binārais logaritms. Tas dos mums koka dziļumu, pieņemot, ka tas ir līdzsvarots. Koks tiek līdzsvarots pēc jauna elementa ievietošanas. Es nesniegšu teoriju par to, kā līdzsvarot kokus. Avota kodi nodrošina līdzsvarošanas funkciju.
Kods svara pārvēršanai dziļumā.
/*
* Возвращает первое число в степени 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));
}Rezultāti
- notiek jauna elementa ievietošana O (log n)
- elementa dzēšana pēc sērijas numura notiek O (log n)
- elementa iegūšana pēc sērijas numura notiek O (log n)
Ātrums O (log n) Mēs maksājam par to, ka visi dati tiek glabāti sakārtotā veidā.
Es nezinu, kur šāda struktūra varētu būt noderīga. Tikai mīkla, lai vēlreiz saprastu, kā darbojas koki. Paldies par jūsu uzmanību.
atsauces
Projektā ir testa dati, lai pārbaudītu darbības ātrumu. Koks piepildās 1000000 elementi. Un notiek elementu secīga dzēšana, ievietošana un izgūšana 1000000 vienreiz. Tas ir 3000000 operācijas. Rezultāts izrādījās diezgan labs ~ 8 sekundes.
Avots: www.habr.com