Hazo binary indexed

Nahita ity karazana olana manaraka ity aho. Ilaina ny mametraka fitahirizana angon-drakitra izay manome ireto fiasa manaraka ireto:

• mampiditra singa vaovao
• esory ny singa amin'ny laharana serial
• mahazo singa amin'ny laharana ordinal
• angona dia voatahiry amin'ny endrika voafantina

Ny angon-drakitra dia ampiana sy esorina tsy tapaka, ny rafitra dia tsy maintsy miantoka ny hafainganam-pandeha haingana. Tamin'ny voalohany dia nanandrana nampihatra zavatra toy izany aho tamin'ny fampiasana kaontenera mahazatra avy amin'ny STD. Tsy voasatroka fahombiazana io lalana io ary tonga ny fahatakarana fa mila mampihatra zavatra aho. Ny hany tonga tao an-tsaina dia ny fampiasana hazo fikarohana binary. Satria mahafeno ny fepetra takiana amin'ny fampidirana haingana, famafana ary fitehirizana angon-drakitra amin'ny endrika voafantina. Ny hany sisa tavela dia ny mamantatra ny fomba fanondroana ny singa rehetra sy ny famerenana ny indices rehefa miova ny hazo.

struct node_s {    
    data_t data;

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

    node_t *left;
    node_t *right;

    node_t *parent;
};

Ny lahatsoratra dia ahitana sary sy teoria bebe kokoa noho ny kaody. Ny kaody dia azo jerena amin'ny rohy etsy ambany.

lanja

Mba hahatratrarana izany, dia nandalo fanovana kely ny hazo, nampiana fampahalalana fanampiny momba izany lanja node. Ny lanjan'ny node dia isan'ny taranak'ity node ity + 1 (lanjan'ny singa tokana).

Function hahazoana lanja node:

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

    return 0;
}

Mitovy amin'izany ny lanjan'ny takelaka 0.

Manaraka, andeha isika hiroso amin'ny fanehoana an-tsary ny ohatra iray amin'ny hazo toy izany. mainty ny lakile node dia haseho amin'ny loko (tsy haseho ny sanda, satria tsy ilaina izany), mena - lanjan'ny knot, maitso - fanondroana node.

Rehefa foana ny hazontsika, dia 0 ny lanjany. Andeha asiana singa fototra ao aminy:

Ny lanjan'ny hazo dia lasa 1, ny lanjan'ny singa fototra dia lasa 1. Ny lanjan'ny singa fototra dia ny lanjan'ny hazo.

Andeha isika hanampy singa vitsivitsy:

Isaky ny ampiana singa vaovao dia midina ny node ary mampitombo ny lanjan'ny node tsirairay mandalo. Rehefa voaforona ny node vaovao dia misy lanja omena azy 1. Raha efa misy ny node misy fanalahidy toy izany, dia hosoratantsika ny sandany ary hiverina any amin'ny fotony, hanafoana ny fiovan'ny lanjan'ny nodes rehetra nandalovanay.
Raha esorina ny node, dia midina isika ary mampihena ny lanjan'ireo node nandalo.

fanondroana

Andeha isika izao hiroso amin'ny fomba index nodes. Ny nodes dia tsy mitahiry mazava ny mari-pamantarana, kajy mifototra amin'ny lanjan'ny nodes. Raha nitahiry ny indeksany izy ireo dia tsy maintsy ilaina izany izy) fotoana hanavaozana ny tondron'ny nodes rehetra aorian'ny fiovan'ny hazo.
Andao hiroso amin'ny fanehoana hita maso. Foana ny hazontsika, andao ampiana ny node voalohany amin'izany:

Ny node voalohany dia manana index 0, ary tranga 2 izao no azo atao. Amin'ny voalohany dia hiova ny mari-pamantarana ny singa fototra, amin'ny faharoa dia tsy hiova izany.

Eo amin'ny fakany, milanja 1 ny zana-kazo havia.

Tranga faharoa:

Tsy niova ny tondron'ny fakany satria nijanona 0 ny lanjan'ny zana-kazo havia.

Ny fanondroan'ny node dia kajy araka ny lanjan'ny zana-kazo ankavia + ny isa nandalovan'ny ray aman-dreny. Inona io isa io?, Ity no index counter, amin'ny voalohany dia mitovy amin'ny 0, satria tsy misy ray aman-dreny ny fakany. Avy eo dia miankina amin'ny toerana hidinantsika amin'ny zaza ankavia na ny havanana. Raha miankavia, dia tsy misy ampiana ny kaontera. Raha ampidirintsika amin'ny havanana ny fanondroan'ny node ankehitriny.

Ohatra, ny fomba kajy ny fanondroan'ny singa misy fanalahidy 8 (zanaka havanana amin'ny fototeny). Ity dia "Root Index" + "lanjan'ny zana-kazo havia amin'ny node misy fanalahidy 8" + "1" == 3 + 2 + 1 == 6
Ny fanondroan'ny singa misy fanalahidy 6 dia ny "Root Index" + 1 == 3 + 1 == 4

Noho izany dia mila fotoana ny fahazoana sy famafana singa iray amin'ny alàlan'ny index O (log n), satria raha te hahazo ny singa irina dia tsy maintsy mahita azy aloha isika (midina avy amin'ny fotony mankany amin'ity singa ity).

lalina

Miorina amin'ny lanjany, azonao atao koa ny manisa ny halalin'ny hazo. Ilaina amin'ny fifandanjana.
Mba hanaovana izany, ny lanjan'ny node amin'izao fotoana izao dia tsy maintsy atao boribory amin'ny isa voalohany amin'ny herin'ny 2 izay lehibe kokoa na mitovy amin'ny lanja nomena ary maka ny logaritma binary avy aminy. Izany dia hanome antsika ny halalin'ny hazo, raha heverina fa voalanjalanja. Ny hazo dia voalanjalanja rehefa avy nampiditra singa vaovao. Tsy hanome teoria momba ny fomba handanjalanjana hazo aho. Ny kaody loharano dia manome asa fampifandanjana.

Kaody hanovana lanja ho lalina.

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

vokatra

• misy fampidirana singa vaovao ao O (log n)
• Ny famafana singa iray amin'ny laharan-tariby dia mitranga ao O (log n)
• ny fahazoana singa iray amin'ny laharan-tariby dia miseho ao O (log n)

Haingana O (log n) Mandoa vola izahay satria voatahiry amin'ny endrika voalamina ny angon-drakitra rehetra.

Tsy fantatro hoe aiza no mety hahasoa ny rafitra toy izany. Puzzle fotsiny mba hahatakarana indray ny fomba fiasan'ny hazo. Misaotra anao noho ny fifantohanao.

soratra masina

• Kaody loharanon'ny hazo

Ny tetikasa dia mirakitra angona fitsapana mba hijerena ny hafainganam-pandehan'ny asa. Feno ny hazo 1000000 singa. Ary misy ny famafana misesy, ny fampidirana ary ny fakana ireo singa 1000000 indray mandeha. Izany hoe 3000000 asa. Ny vokatra dia hita fa tena tsara ~ 8 segondra.

Source: www.habr.com