Mo pade iru iṣoro ti o tẹle. O jẹ dandan lati ṣe eiyan ibi ipamọ data ti o pese iṣẹ ṣiṣe atẹle:
- fi titun ano
- yọ ano nipa nọmba ni tẹlentẹle
- gba ano nipa ordinal nọmba
- data ti wa ni fipamọ ni lẹsẹsẹ fọọmu
Data ti wa ni afikun nigbagbogbo ati yọkuro, eto naa gbọdọ rii daju iyara iṣẹ ṣiṣe. Ni akọkọ Mo gbiyanju lati ṣe iru nkan bẹẹ nipa lilo awọn apoti boṣewa lati wakati. Ọna yii ko ni ade pẹlu aṣeyọri ati oye wa pe Mo nilo lati ṣe ohunkan funrararẹ. Ohun kan ṣoṣo ti o wa si ọkan ni lati lo igi wiwa alakomeji. Nitoripe o pade ibeere ti fifi sii ni iyara, piparẹ ati ibi ipamọ data ni fọọmu tito lẹsẹsẹ. Gbogbo ohun ti o ku ni lati ṣawari bi o ṣe le ṣe atọka gbogbo awọn eroja ati tun ṣe iṣiro awọn atọka nigbati igi ba yipada.
struct node_s {
data_t data;
uint64_t weight; // вес узла
node_t *left;
node_t *right;
node_t *parent;
};Nkan naa yoo ni awọn aworan ati ilana diẹ sii ju koodu lọ. Awọn koodu le wa ni bojuwo ni awọn ọna asopọ ni isalẹ.
Iwuwo
Lati ṣaṣeyọri eyi, igi naa ṣe iyipada diẹ, a ṣafikun alaye afikun nipa iwuwo ipade. Iwọn ipade jẹ nọmba awọn ọmọ ti yi ipade + 1 (àdánù ti a nikan ano).
Iṣẹ fun gbigba iwuwo node:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}Awọn àdánù ti awọn dì ni correspondingly dogba si 0.
Nigbamii, jẹ ki a lọ si aṣoju wiwo ti apẹẹrẹ ti iru igi kan. dudu bọtini ipade yoo han ni awọ (iye kii yoo han, nitori eyi ko ṣe pataki), ni pupa - iwuwo sorapo, alawọ ewe - ipade atọka.
Nigbati igi wa ba ṣofo, iwuwo rẹ jẹ 0. Jẹ ki a fi ipilẹ gbongbo kun si:
Ìwọ̀n igi náà yóò di 1, ìwọ̀n gbòǹgbò gbòǹgbò náà yóò di 1.
Jẹ ki a fi awọn eroja diẹ kun:
Nigbakugba ti a ba ṣafikun eroja tuntun, a lọ si isalẹ awọn apa ati mu iṣiro iwuwo ti ipade kọọkan ti kọja. Nigbati ipade tuntun ba ṣẹda, iwuwo kan ni a yan si 1. Ti ipade kan pẹlu iru bọtini kan wa tẹlẹ, lẹhinna a yoo kọ iye naa ki o pada si gbongbo, fagile awọn ayipada ninu awọn iwuwo ti gbogbo awọn apa ti a ti kọja.
Ti ipade kan ba ti yọ kuro, lẹhinna a lọ si isalẹ ki o dinku awọn iwuwo ti awọn apa ti o kọja.
Atọka
Bayi jẹ ki a lọ siwaju si bi o ṣe le ṣe atọka awọn apa. Awọn apa ko tọju atọka wọn ni gbangba, o jẹ iṣiro da lori iwuwo awọn apa. Ti wọn ba tọju atọka wọn, lẹhinna o yoo nilo O (n) akoko lati ṣe imudojuiwọn awọn atọka ti gbogbo awọn apa lẹhin iyipada kọọkan ninu igi naa.
Jẹ ki a lọ siwaju si aṣoju wiwo. Igi wa ti ṣofo, jẹ ki a fi aaye akọkọ kun si:
Ipade akọkọ ni atọka kan 0, ati nisisiyi awọn ọran 2 ṣee ṣe. Ni akọkọ, atọka ti eroja root yoo yipada, ni keji kii yoo yipada.
Ni gbongbo, igi abẹlẹ osi ṣe iwọn 1.
Ọran keji:
Atọka ti gbongbo ko yipada nitori iwuwo igi abẹlẹ osi rẹ wa 0.
Atọka ipade kan jẹ iṣiro bi iwuwo ti abẹlẹ osi rẹ + nọmba ti o kọja lati ọdọ obi. Kini nọmba yii?, Eyi ni counter atọka, lakoko o jẹ dogba si 0, nitori gbongbo ko ni obi. Lẹhinna gbogbo rẹ da lori ibi ti a sọkalẹ lọ si ọmọ osi tabi ọtun. Ti o ba wa ni apa osi, lẹhinna ko si ohun ti a fi kun si counter. Ti a ba fi awọn atọka ti awọn ti isiyi ipade si ọtun kan.
Fun apẹẹrẹ, bawo ni Atọka ti ano pẹlu bọtini 8 (ọmọ ọtun ti gbongbo) ṣe iṣiro. Eyi ni "Atọka Gbongbo" + "iwuwo ti apa osi ti ipade pẹlu bọtini 8" + "1" == 3 + 2 + 1 == 6
Atọka eroja pẹlu bọtini 6 yoo jẹ "Atọka Gbongbo" + 1 == 3 + 1 == 4
Nitorinaa, o gba akoko lati gba ati paarẹ nkan kan nipasẹ atọka O (wọle n), nitori lati le gba eroja ti o fẹ a gbọdọ kọkọ wa (lọ si isalẹ lati gbongbo si eroja yii).
Ijinle
Da lori iwuwo, o tun le ṣe iṣiro ijinle igi naa. Pataki fun iwontunwosi.
Lati ṣe eyi, iwuwo ti oju ipade lọwọlọwọ gbọdọ wa ni yika si nọmba akọkọ si agbara ti 2 eyiti o tobi ju tabi dogba si iwuwo ti a fun ati mu logarithm alakomeji lati ọdọ rẹ. Eyi yoo fun wa ni ijinle igi, ti a ro pe o jẹ iwontunwonsi. Igi naa jẹ iwọntunwọnsi lẹhin fifi nkan tuntun sii. Emi kii yoo funni ni imọran nipa bi o ṣe le ṣe iwọntunwọnsi awọn igi. Awọn koodu orisun pese iṣẹ iwọntunwọnsi.
Koodu fun iyipada iwuwo si ijinle.
/*
* Возвращает первое число в степени 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));
}Awọn esi
- ifibọ ti a titun ano waye ni O (wọle n)
- piparẹ ohun ano nipa nọmba ni tẹlentẹle waye ninu O (wọle n)
- gbigba ohun ano nipa nọmba ni tẹlentẹle waye ninu O (wọle n)
Iyara O (wọle n) A sanwo fun otitọ pe gbogbo data ti wa ni ipamọ ni fọọmu lẹsẹsẹ.
Emi ko mọ ibiti iru eto le wulo. O kan adojuru lati ni oye lekan si bi awọn igi ṣe n ṣiṣẹ. Mo dupe fun ifetisile re.
jo
Ise agbese na ni data idanwo lati ṣayẹwo iyara iṣẹ. Igi naa n kun 1000000 eroja. Ati pe piparẹ ọkọọkan wa, fifi sii ati imupadabọ awọn eroja 1000000 lẹẹkan. Ti o jẹ 3000000 awọn iṣẹ ṣiṣe. Abajade ti jade lati dara pupọ ~ 8 awọn aaya.
orisun: www.habr.com