Ez rastî pirsgirêka jêrîn hatim. Pêdivî ye ku konteynerek hilanîna daneyê ku fonksiyona jêrîn peyda dike bicîh bîne:
- hêmanek nû têxe
- element bi jimareya serial jêbirin
- hêmanek bi jimareya rêzdî bigire
- Daneyên di forma rêzkirî de têne tomar kirin
Daneyên bi domdarî têne zêdekirin û rakirin, pêdivî ye ku avahî leza xebata bilez peyda bike. Di destpêkê de min hewl da ku tiştek wusa bi karanîna konteynerên standard ji were bicîh bikim saetan. Ev rê bi serketinê nehat taca kirin û têgihiştin ku pêwîst e ez bi xwe tiştekî bi cih bînim. Tiştê ku hat bîra min ev bû ku dara lêgerînê ya binary bikar bîne. Ji ber ku ew hewcedariya lêxistina bilez, jêbirin û hilanîna daneyan bi rengek cûrbecûr pêk tîne. Tiştê ku dimîne ev e ku meriv fêr bibe ka meriv çawa hemî hêmanan navnîş dike û gava ku dar diguhezîne nîşanan ji nû ve hesab bike.
struct node_s {
data_t data;
uint64_t weight; // вес узла
node_t *left;
node_t *right;
node_t *parent;
};Gotar dê ji kodê bêtir wêne û teoriyê bigire. Kod dikare li ser lînka jêrîn were dîtin.
Weight
Ji bo ku bigihîje vê yekê, dar di bin guheztinek sivik de bû, di derheqê de agahdariya zêde hate zêdekirin pîvan node. Giraniya nodê ye hejmara neviyên vê nodê + 1 (giraniya yek elementek).
Fonksiyon ji bo bidestxistina giraniya nodê:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}Giraniya pelê bi heman rengî wekhev e 0.
Dûv re, em werin ser temsîlek dîtbar a mînakek darek weha. reş mifteya nodê dê bi reng were xuyang kirin (nirx dê neyê xuyang kirin, ji ber ku ev ne hewce ye), bi sor - giraniya girêk, kesk - index girêk.
Dema ku dara me vala ye, giraniya wê 0 ye. Ka em hêmanek kok lê zêde bikin:
Giraniya darê dibe 1, giraniya hêmana kokê dibe 1. Giraniya hêmanê darê giraniya darê ye.
Ka em çend hêmanên din lê zêde bikin:
Her gava ku hêmanek nû tê zêdekirin, em dakevin girêkan û pîvana giraniya her girêkek derbasbûyî zêde dikin. Dema ku girêkek nû tê çêkirin, giraniyek jê re tê destnîşankirin 1. Ger girêkek bi vî rengî jixwe hebe, wê hingê em ê nirxê binivîsînin û vegerin ser kokê, guheztinên giraniya hemî girêkên ku me derbas kirine betal bikin.
Ger girêkek were rakirin, wê hingê em dadikeve jêr û giraniya girêkên derbasbûyî kêm dikin.
Indexes
Naha em werin ser ka meriv çawa girêkan îndeks dike. Nod bi eşkere nîşaneya xwe hilnagirin, ew li ser bingeha giraniya girêkan tê hesibandin. Ger wan navnîşa xwe hilanîn, wê hingê ew ê hewce be O (n) wextê nûvekirina îndeksên hemî girêkan piştî her guhartina darê.
Werin em biçin ser temsîlek dîtbar. Dara me vala ye, em girêka 1em lê zêde bikin:
Di girêka yekem de indexek heye 0, û niha 2 bûyer mimkun in. Di ya yekem de, navnîşa hêmana root dê biguhere, di ya duyemîn de ew ê neguhere.
Di kokê de, binê dara çepê 1 giran e.
Rewşa duyemîn:
Ji ber ku giraniya binê dara wê ya çepê 0 ma, nîşaneya kokê neguherî.
Indeksa girêkekê wekî giraniya jêrdara wê ya çepê + jimareya ku ji dêûbavê derbas bûye tê hesibandin. Ev hejmar çend e?, Ev jimarvana îndeksê ye, di destpêkê de ew wekhev e 0, ji ber koka dê û bav tune. Dûv re ew hemî bi wê ve girêdayî ye ku em li ku derê dakevin zarokê çepê an yê rastê. Ger li çepê, wê hingê tiştek li jimareyê nayê zêdekirin. Ger em nîşaneya girêka heyî li ya rast lê zêde bikin.
Mînakî, nîşana hêmanek bi key 8 (zaroka rastê ya kokê) çawa tê hesibandin. Ev "Indeksa Root" + "giraniya binê dara çepê ya bi kilîta 8" + "1" == 3 + 2 + 1 == 6
Indeksa hêmana bi key 6 dê bibe "Indeksa Root" + 1 == 3 + 1 == 4
Li gorî vê yekê, ji bo bidestxistin û jêbirina hêmanek bi navnîşan dem digire O (têkevê n), ji ber ku ji bo ku em hêmana xwestinê bi dest bixin divê pêşî em wê bibînin (ji kokê dakevin vê hêmanê).
Depth
Li ser bingeha giraniyê, hûn dikarin kûrahiya darê jî hesab bikin. Ji bo hevsengiyê pêwîst e.
Ji bo vê yekê, divê giraniya girêka heyî bi jimareya yekem bi hêza 2-yê ku ji giraniya diyarkirî mezintir an wekhev e were dorpêç kirin û logarîtma binaryê jê bistînin. Ev ê kûrahiya darê bide me, bihesibînin ku ew hevseng e. Dar piştî têxistina hêmanek nû hevseng e. Ez ê teoriyek nekim ka meriv çawa daran hevseng dike. Kodên çavkaniyê fonksiyonek hevsengiyê peyda dikin.
Koda ji bo veguhertina giraniyê bi kûrahiyê.
/*
* Возвращает первое число в степени 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));
}Encam
- têketina hêmanek nû tê de pêk tê O (têkevê n)
- jêbirina hêmanek ji hêla jimareya rêzik ve tê de pêk tê O (têkevê n)
- bidestxistina hêmanek bi jimareya rêzî tê de pêk tê O (têkevê n)
Zûbûnî O (têkevê n) Em ji bo rastiya ku hemî daneyan di forma rêzkirî de têne hilanîn didin.
Ez nizanim ku avahiyek wusa dibe ku kêrhatî be. Tenê puzzleyek ku careke din fêm bike ka dar çawa dixebitin. Spas ji bo baldariya we.
references
Proje daneyên testê vedihewîne da ku leza xebatê kontrol bike. Dar tijî dibe 1000000 hêmanên. Û jêbirin, têxistin û vegerandina hêmanan li dû hev heye 1000000 carek. Ku heye 3000000 operasyonên. Encam ~ 8 saniyeyan pir baş derket.
Source: www.habr.com