Thàinig mi tarsainn air an t-seòrsa duilgheadas a leanas. Tha e riatanach inneal stòraidh dàta a chuir an gnìomh a bheir seachad na gnìomhan a leanas:
- cuir a-steach eileamaid ùr
- thoir air falbh eileamaid le àireamh sreathach
- faigh eileamaid le àireamh òrdail
- dàta air a stòradh ann an cruth eagraichte
Tha dàta an-còmhnaidh ga chur ris agus ga thoirt air falbh, feumaidh an structar dèanamh cinnteach à astar obrachaidh luath. An toiseach dh’ fheuch mi ri leithid de rud a chuir an gnìomh a’ cleachdadh soithichean àbhaisteach bho gd. Cha deach an t-slighe seo a chrùnadh le soirbheachas agus thàinig an tuigse gum feum mi rudeigin a chuir an gnìomh mi-fhìn. B 'e an aon rud a thàinig gu inntinn a bhith a' cleachdadh craobh rannsachaidh dà-chànanach. Leis gu bheil e a’ coinneachadh ris an riatanas airson cuir a-steach luath, cuir às agus stòradh dàta ann an cruth òrdachadh. Chan eil air fhàgail ach faighinn a-mach mar a nì thu clàr-amais air na h-eileamaidean gu lèir agus ath-àireamhachadh nan clàran-amais nuair a dh’ atharraicheas a’ chraobh.
struct node_s {
data_t data;
uint64_t weight; // вес узла
node_t *left;
node_t *right;
node_t *parent;
};Bidh barrachd dhealbhan agus teòiridh anns an artaigil na còd. Faodar an còd fhaicinn aig a’ cheangal gu h-ìosal.
Cuideam
Gus seo a choileanadh, chaidh atharrachadh beag a dhèanamh air a 'chraobh, chaidh fiosrachadh a bharrachd a chur ris cuideam nód. Tha cuideam an nòta àireamh sliochd an nòs so + 1 (cuideam aon eileamaid).
Gnìomh airson cuideam nòta fhaighinn:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}Tha cuideam na duilleig co-ionann ris 0.
An ath rud, gluaisidh sinn air adhart gu riochdachadh lèirsinneach de eisimpleir de chraobh mar sin. Dubh thèid an iuchair nód a shealltainn ann an dath (cha tèid an luach a shealltainn, leis nach eil seo riatanach), ann an dearg - cuideam snaidhm, uaine - clàr-amais nod.
Nuair a tha a’ chraobh againn falamh, tha a cuideam 0. Cuiridh sinn bun-eileamaid ris:
Bidh cuideam na craoibhe gu bhith 1, bidh cuideam na h-eileamaid bunaiteach gu bhith 1. Is e cuideam na h-eileamaid freumh cuideam na craoibhe.
Nach cuir sinn beagan eileamaidean eile ris:
Gach uair a thèid eileamaid ùr a chuir ris, bidh sinn a’ dol sìos na nodan agus ag àrdachadh cuntair cuideam gach nód a thèid seachad. Nuair a thèid nód ùr a chruthachadh, thèid cuideam a thoirt dha 1. Ma tha nód le leithid de iuchair ann mu thràth, bidh sinn a’ sgrìobhadh thairis air an luach agus a’ dol air ais chun fhreumh, a’ cuir dheth na h-atharrachaidhean ann an cuideaman nan nodan air fad a chaidh sinn seachad.
Ma thèid nód a thoirt air falbh, thèid sinn sìos agus lughdaichidh sinn cuideam nan nodan a chaidh seachad.
Clàran-innse
A-nis gluaisidh sinn air adhart gu mar a nì thu clàr-amais nodan. Chan eil nodan a 'stòradh an clàr-amais gu soilleir, tha e air a thomhas a rèir cuideam nan nodan. Nam biodh iad a 'gleidheadh an clàr-amais aca, bhiodh feum air O (n) ùine airson clàran-amais nan nodan uile ùrachadh às deidh gach atharrachadh sa chraoibh.
Gluaisidh sinn air adhart gu riochdachadh lèirsinneach. Tha a’ chraobh againn falamh, cuireamaid a’ chiad nód ris:
Tha clàr-amais aig a’ chiad nód 0, agus a-nis tha 2 chùis comasach. Anns a 'chiad fhear, atharraichidh clàr-amais an eileamaid bunaiteach, anns an dàrna fear chan atharraich e.
Aig a 'bhun-stèidh, tha cuideam 1 air an fho-chraobh chlì.
An dàrna cùis:
Cha do dh'atharraich clàr-amais a' bhunait oir dh'fhuirich cuideam an fho-chraobh chlì aige 0.
Tha clàr-amais nód air a thomhas mar chuideam an fho-chraobh chlì aige + an àireamh a chaidh seachad bhon phàrant. Dè an àireamh a tha seo?, Is e seo an clàr-cunntais, an toiseach tha e co-ionann ri 0, oir chan eil pàrant aig a’ bhunait. An uairsin tha e uile an urra ri càite an tèid sinn sìos chun leanabh clì no an tè cheart. Ma tha air an taobh chlì, chan eil dad air a chur ris a 'chunntair. Ma chuireas sinn clàr-amais an nód làithreach ris an fhear cheart.
Mar eisimpleir, mar a tha clàr-amais eileamaid le iuchair 8 (leanabh ceart na freumh) air a thomhas. 'S e seo "Clàr-amais Root" +"cuideam fo-chraobh clì an nòta le iuchair 8" + "1" == 3 + 2 + 1 == 6
'S e "Root Index" + 6 == 1 + 3 == clàr-amais na h-eileamaid le iuchair 1 4
Mar sin, bheir e ùine airson eileamaid fhaighinn agus a dhubhadh às le clàr-amais O (log n), oir gus an eileamaid a tha thu ag iarraidh fhaighinn feumaidh sinn an toiseach a lorg (rach sìos bhon fhreumh chun an eileamaid seo).
Depth
Stèidhichte air a 'chuideam, faodaidh tu cuideachd doimhneachd na craoibhe obrachadh a-mach. Tha e riatanach airson cothromachadh.
Gus seo a dhèanamh, feumaidh cuideam an nód gnàthach a bhith cruinn chun chiad àireamh gu cumhachd 2 a tha nas motha na no co-ionann ris a’ chuideam a chaidh a thoirt seachad agus an logarithm binary a thoirt bhuaithe. Bheir seo dhuinn doimhneachd na craoibhe, a 'gabhail ris gu bheil e cothromach. Tha an craobh air a chothromachadh às deidh dha eileamaid ùr a chuir a-steach. Cha toir mi seachad teòiridh air mar as urrainn dhut craobhan a chothromachadh. Tha na còdan stòr a’ toirt seachad gnìomh cothromachaidh.
Còd airson cuideam atharrachadh gu doimhneachd.
/*
* Возвращает первое число в степени 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));
}Builean
- cuir a-steach eileamaid ùr a’ tachairt ann an O (log n)
- tha cuir às do eileamaid le àireamh sreathach a’ tachairt ann O (log n)
- gheibhear eileamaid le àireamh sreathach ann an O (log n)
Luas O (log n) Bidh sinn a’ pàigheadh airson gu bheil an dàta gu lèir air a stòradh ann an cruth eagraichte.
Chan eil fios agam càite am biodh structar mar seo feumail. Dìreach tòimhseachan airson tuigsinn a-rithist mar a tha craobhan ag obair. Tapadh leibh airson an aire agad.
iomraidhean
Tha dàta deuchainn anns a’ phròiseact gus sgrùdadh a dhèanamh air astar an obrachaidh. Tha an craobh air a lìonadh 1000000 eileamaidean. Agus tha cuir às, cuir a-steach agus toirt air ais eileamaidean ann an sreath 1000000 aon uair. S e sin 3000000 obrachaidhean. Thionndaidh an toradh a-mach gu bhith math gu leòr ~ 8 diogan.
Source: www.habr.com