🥇 Osisi ọnụọgụ abụọ nwere ike ịdepụta

Ahụrụ m ụdị nsogbu a. Ọ dị mkpa iji mejuputa akpa nchekwa data nke na-enye ọrụ ndị a:

fanye ihe ọhụrụ
wepụ mmewere site na nọmba serial
nweta mmewere site na nọmba ordinal
A na-echekwa data n'ụdị edoziri

A na-agbakwunye ma wepụ data mgbe niile, ihe owuwu ahụ ga-emerịrị ngwa ngwa ọrụ. Na mbụ, m gbalịrị imejuputa ihe dị otú ahụ site na iji ọkọlọtọ ọkọlọtọ si awa. Ụzọ a enweghị okpueze na ihe ịga nke ọma na nghọta bịara na m kwesịrị ime ihe n'onwe m. Naanị ihe batara n'uche bụ iji osisi ọchụchọ ọnụọgụ abụọ. N'ihi na ọ na-emezu ihe achọrọ nke ntinye ngwa ngwa, ihichapụ na nchekwa data n'ụdị edoziri. Naanị ihe fọdụrụ bụ iji chọpụta ka esi edepụta ihe niile na-atụgharị ma gbanwee indices mgbe osisi ahụ gbanwere.

struct node_s {    
    data_t data;

    uint64_t weight; // вес узла

    node_t *left;
    node_t *right;

    node_t *parent;
};

Edemede a ga-enwe foto na tiori karịa koodu. Enwere ike ịlele koodu ahụ na njikọ dị n'okpuru.

Ibu ibu

Iji mezuo nke a, osisi ahụ nwere ntakịrị mgbanwe, agbakwunyere ozi ndị ọzọ gbasara ya ibu ọnụ. Ibu ọnụ bụ ọnụ ọgụgụ nke ụmụ ọnụ ọnụ a + 1 (ịdị arọ nke otu mmewere).

Ọrụ maka inweta ibu node:

uint64_t bntree::get_child_weight(node_t *node) {
    if (node) {
        return node->weight;
    }

    return 0;
}

Ibu nke mpempe akwụkwọ kwekọrọ na ya 0.

Ọzọ, ka anyị gaa n'ihu na ihe ngosi anya nke ihe atụ nke osisi dị otú ahụ. Nwa A ga-egosipụta igodo ọnụ na agba (a gaghị egosi uru ya, ebe ọ bụ na nke a adịghị mkpa), uhie - eriri afọ, acha akwụkwọ ndụ - ọnụ index.

Mgbe osisi anyị tọgbọrọ chakoo, arọ ya bụ 0. Ka anyị tinye ihe mgbọrọgwụ na ya:

Ibu nke osisi na-aghọ 1, arọ nke mgbọrọgwụ element na-aghọ 1. Ibu nke mgbọrọgwụ element bụ arọ nke osisi.

Ka anyị tinye ihe ole na ole ọzọ:

Oge ọ bụla agbakwunyere mmewere ọhụrụ, anyị na-agbada ọnụ ma na-abawanye counter arọ nke ọnụ ọnụ ọ bụla gafere. Mgbe emepụtara ọnụ ụzọ ọhụrụ, a na-ekenye ya ibu arọ 1. Ọ bụrụ na ọnụ nwere igodo dị otú ahụ adịlarị, mgbe ahụ, anyị ga-edegharị uru ahụ wee laghachi na mgbọrọgwụ, na-akagbu mgbanwe n'ịdị arọ nke ọnụ ọnụ niile anyị gafere.
Ọ bụrụ na a na-ewepụ ọnụ ọnụ, mgbe ahụ, anyị na-agbada ma na-ebelata ịdị arọ nke ọnụ ọnụ ndị gafere.

Ndekọ

Ugbu a, ka anyị gaa n'ihu ka esi edepụta ọnụ ọnụ. Nodes anaghị echekwa index ha n'ụzọ doro anya, a na-agbakọ ya dabere na ịdị arọ nke ọnụ ọnụ. Ọ bụrụ na ha na-echekwa index ha, mgbe ahụ ọ ga-achọrọ O (n) oge imelite indexes niile ọnụ mgbe ọ bụla mgbanwe na osisi.
Ka anyị gaa n'ihu na ihe ngosi anya. Osisi anyị tọgbọ chakoo, ka anyị tinye ọnụ nke mbụ na ya:

Ọnụ ụzọ mbụ nwere ndeksi 0, ma ugbu a, ikpe 2 ga-ekwe omume. Na nke mbụ, index nke ihe mgbọrọgwụ ga-agbanwe, na nke abụọ ọ gaghị agbanwe.

Na mgbọrọgwụ, akụkụ aka ekpe na-eru 1.

Ikpe nke abụọ:

Ndekọ nke mgbọrọgwụ agbanweghị n'ihi na ịdị arọ nke osisi aka ekpe ya ka dị 0.

A na-agbakọ index nke ọnụ ọnụ dị ka ịdị arọ nke obere osisi aka ekpe ya + ọnụọgụ ndị nne na nna gafere. Gịnị bụ nọmba a?, Nke a bụ index counter, na mbụ ọ hà nhata 0, n'ihi na mgbọrọgwụ enweghị nne na nna. Mgbe ahụ, ihe niile dabere na ebe anyị na-agbada nwa aka ekpe ma ọ bụ aka nri. Ọ bụrụ n'aka ekpe, mgbe ahụ ọ dịghị ihe ọ bụla agbakwunyere na counter. Ọ bụrụ na anyị gbakwunye index nke ọnụ ugbu a n'aka nri.

Dịka ọmụmaatụ, ka esi agbakọọ index nke ihe mmewere nwere igodo 8 (nwa kwesịrị ekwesị nke mgbọrọgwụ). Nke a bụ "Mkpọrọgwụ Index" + "Arọ nke akụkụ aka ekpe nke ọnụ nwere igodo 8" + "1" == 3 + 2 + 1 == 6
Ndekọ nke mmewere nwere igodo 6 ga-abụ "Root Index" + 1 == 3 + 1 == 4

N'ihi nke a, ọ na-ewe oge iji nweta ma hichapụ otu mmewere site na ndeksi O (log n), n'ihi na iji nweta ihe a chọrọ, anyị ga-ebu ụzọ chọta ya (site na mgbọrọgwụ gaa na nke a).

Omimi

Dabere na ịdị arọ, ị nwekwara ike gbakọọ omimi nke osisi ahụ. Dị mkpa maka itule.
Iji mee nke a, a ghaghị ịgbanye arọ nke ọnụ ọnụ ugbu a na nọmba mbụ na ike nke 2 nke dị ukwuu karịa ma ọ bụ hà nhata nke enyere ma were ọnụọgụ abụọ logarithm na ya. Nke a ga-enye anyị omimi nke osisi ahụ, na-eche na ọ dabara adaba. Osisi ahụ na-edozi ahụ mgbe ịtinye ihe ọhụrụ. Agaghị m enye echiche banyere otu esi edozi osisi. Koodu isi mmalite na-enye ọrụ nhazi.

Koodu maka ịtụgharị ibu ka ọ dị omimi.

/*
 * Возвращает первое число в степени 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));
}

Nsonaazụ

ntinye nke ihe ọhụrụ pụtara na O (log n)
ihichapụ ihe mmewere site na nọmba serial na-apụta na O (log n)
inweta mmewere site na nọmba serial na-apụta na O (log n)

Ọsọ O (log n) Anyị na-akwụ ụgwọ maka eziokwu ahụ bụ na echekwara data niile n'ụdị edoziri.

Amaghị m ebe usoro dị otú ahụ nwere ike ịba uru. Naanị ihe mgbagwoju anya iji ghọta ọzọ ka osisi si arụ ọrụ. Daalụ maka itinye uche gị.

zoro

Koodu isi osisi

Ọrụ ahụ nwere data nnwale iji lelee ọsọ nke ọrụ. Osisi na-ejuputa 1000000 ihe. Ma enwere ihichapụ, ntinye na iweghachi ihe n'usoro 1000000 otu ugboro. Ya bụ 3000000 arụmọrụ. Nsonaazụ ahụ wee bụrụ ezigbo mma ~ 8 sekọnd.

isi: www.habr.com

Osisi ọnụọgụ abụọ edepụtara

Ibu ibu

Ndekọ

Omimi

Nsonaazụ

zoro

Tinye a comment Отменить ответ