Tháinig mé trasna ar an gcineál faidhbe seo a leanas. Is gá coimeádán stórála sonraí a chur i bhfeidhm a sholáthraíonn an fheidhmiúlacht seo a leanas:
- cuir isteach eilimint nua
- bain eilimint de réir sraithuimhir
- faigh eilimint de réir orduimhreacha
- stóráiltear sonraí i bhfoirm shórtáilte
Tá sonraí á gcur leis agus á mbaint i gcónaí, ní mór don struchtúr luas tapa oibríochta a chinntiú. Ar dtús rinne mé iarracht rud den sórt sin a chur i bhfeidhm ag baint úsáide as coimeádáin chaighdeánacha ó uair an chloig. Ní raibh rath ar an gcosán seo agus tháinig an tuiscint go raibh orm rud éigin a chur i bhfeidhm mé féin. Ba é an t-aon rud a tháinig chun cuimhne ná crann cuardaigh dénártha a úsáid. Toisc go gcomhlíonann sé an ceanglas maidir le cur isteach tapa, scriosadh agus stóráil sonraí i bhfoirm shórtáilte. Níl fágtha ach a dhéanamh amach conas na heilimintí go léir a innéacsú agus na hinnéacsanna a athríomh nuair a athraíonn an crann.
struct node_s {
data_t data;
uint64_t weight; // вес узла
node_t *left;
node_t *right;
node_t *parent;
};Beidh níos mó pictiúr agus teoiric ná cód san alt. Is féidir an cód a fheiceáil ag an nasc thíos.
Meáchan
Chun é seo a bhaint amach, rinneadh mionathrú ar an gcrann, cuireadh faisnéis bhreise leis meáchan nód. Is é an meáchan nód líon sliocht an nód seo + 1 (meáchan dúil amháin).
Feidhm chun meáchan nód a fháil:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}Tá meáchan an bhileog comhionann go comhfhreagrach le 0.
Ansin, déanaimis bogadh ar aghaidh chuig léiriú amhairc ar shampla de chrann den sórt sin. Dubh taispeánfar an eochair nód i ndath (ní thaispeánfar an luach, ós rud é nach bhfuil sé seo riachtanach), dearg - meáchan snaidhm, glas — innéacs nód.
Nuair a bhíonn ár gcrann folamh, is é 0 an meáchan atá aige. Cuirimis buneilimint leis:
Éiríonn meáchan an chrainn 1, déantar meáchan na heiliminte fréimhe 1. Is é meáchan an eilimint fhréamh meáchan an chrainn.
Cuirimis cúpla eilimint eile leis:
Gach uair a chuirtear eilimint nua leis, téann muid síos na nóid agus méadaítear cuntar meáchain gach nód a rith. Nuair a chruthaítear nód nua, sanntar meáchan dó 1. Má tá nód le eochair den sórt sin ann cheana féin, ansin déanfaimid an luach a fhorscríobh agus dul ar ais go dtí an fhréamh, ag cealú na n-athruithe i meáchain na nóid go léir a ritheamar.
Má tá nód á bhaint, ansin téann muid síos agus laghdaítear meáchain na nóid a ritheadh.
Innéacsanna
Anois, a ligean ar bogadh ar aghaidh go dtí conas a nóid innéacs. Ní stórálann nóid a n-innéacs go sainráite, ríomhtar é bunaithe ar mheáchan na nóid. Dá mbeadh a n-innéacs stóráilte acu, bheadh gá leis O (n) am chun innéacsanna na nóid go léir a nuashonrú tar éis gach athrú ar an gcrann.
A ligean ar bogadh ar aghaidh chuig léiriú amhairc. Tá ár gcrann folamh, cuirimis an 1ú nód leis:
Tá innéacs ag an gcéad nód 0, agus anois is féidir 2 chás. Ar an gcéad dul síos, athróidh innéacs an fhréamhghné, sa dara ní athróidh sé.
Ag an fhréamh, is é 1 an meáchan atá ag an bhfochrann ar chlé.
Dara cás:
Níor tháinig aon athrú ar innéacs na fréimhe toisc gur fhan meáchan an fhochrainn chlé 0.
Ríomhtar innéacs nód mar mheáchan an fhochrainn chlé + an uimhir a ritheadh ón tuismitheoir. Cad é an uimhir seo?, Is é seo an cuntar innéacs, ar dtús tá sé cothrom le 0, mar níl aon tuismitheoir ag an bhfréamh. Ansin braitheann sé go léir ar an áit a dtéann muid síos go dtí an leanbh clé nó an ceann ceart. Más rud é ar an taobh clé, ní chuirtear aon rud leis an gcuntar. Má chuirimid innéacs an nód reatha leis an gceann ceart.
Mar shampla, conas a ríomhtar innéacs eilimint le heochair 8 (leanbh ceart an fhréamh). Seo "Innéacs Fréamh" + "meáchan an fhochrainn chlé den nód le heochair 8" + "1" == 3 + 2 + 1 == 6
Beidh innéacs na heiliminte le heochair 6 mar "Innéacs Fréamh" + 1 == 3 + 1 == 4
Dá réir sin, tógann sé am chun eilimint a fháil agus a scriosadh de réir innéacs O(log n), mar gheall ar d'fhonn an eilimint atá ag teastáil a fháil ní mór dúinn é a fháil ar dtús (téigh síos ón bhfréamh go dtí an eilimint seo).
Doimhneacht
Bunaithe ar an meáchan, is féidir leat doimhneacht an chrainn a ríomh freisin. Riachtanach le haghaidh cothromaíochta.
Chun seo a dhéanamh, ní mór meáchan an nód reatha a shlánú go dtí an chéad uimhir go dtí an chumhacht de 2 atá níos mó ná nó cothrom leis an meáchan tugtha agus an logarithm dénártha a bhaint as. Tabharfaidh sé seo doimhneacht an chrainn dúinn, ag glacadh leis go bhfuil sé cothrom. Déantar an crann a chothromú tar éis eilimint nua a chur isteach. Ní thabharfaidh mé teoiric faoi conas crainn a chothromú. Soláthraíonn na cóid foinse feidhm chothromaithe.
Cód chun meáchan a thiontú go doimhneacht.
/*
* Возвращает первое число в степени 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));
}Torthaí
- cuirtear isteach eilimint nua i O(log n)
- tarlaíonn scriosadh eilimint de réir sraithuimhir i O(log n)
- Tarlaíonn eilimint a fháil trí shraithuimhir i O(log n)
Luas O(log n) Íocaimid as an bhfíric go bhfuil na sonraí go léir stóráilte i bhfoirm shórtáilte.
Níl a fhios agam cén áit a bhféadfadh struchtúr den sórt sin a bheith úsáideach. Just a bhfreagra a thuiscint arís conas a oibríonn crainn. Go raibh maith agat as do aird.
tagairtí
Tá sonraí tástála sa tionscadal chun luas na hoibríochta a sheiceáil. Tá an crann ag líonadh suas 1000000 eilimintí. Agus tá scriosadh seicheamhach, cuir isteach agus aisghabháil eilimintí 1000000 uair. Is é sin 3000000 oibríochtaí. Bhí an toradh sách maith ~ 8 soicind.
Foinse: will.com
