Coeden ddeuaidd wedi'i mynegeio

Deuthum ar draws y math canlynol o broblem. Mae angen gweithredu cynhwysydd storio data sy'n darparu'r swyddogaethau canlynol:

• mewnosod elfen newydd
• dileu elfen yn ôl rhif cyfresol
• cael elfen yn ôl trefnolyn
• data yn cael ei storio ar ffurf didoli

Mae data yn cael ei ychwanegu a'i ddileu yn gyson, rhaid i'r strwythur sicrhau cyflymder gweithredu cyflym. Ar y dechrau ceisiais weithredu'r fath beth gan ddefnyddio cynwysyddion safonol o oriau. Ni choronwyd y llwybr hwn â llwyddiant a daeth y ddealltwriaeth bod angen i mi weithredu rhywbeth fy hun. Yr unig beth a ddaeth i'r meddwl oedd defnyddio coeden chwilio ddeuaidd. Oherwydd ei fod yn bodloni'r gofyniad o fewnosod, dileu a storio data yn gyflym ar ffurf didoli. Y cyfan sydd ar ôl yw darganfod sut i fynegeio'r holl elfennau ac ailgyfrifo'r mynegeion pan fydd y goeden yn newid.

struct node_s {    
    data_t data;

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

    node_t *left;
    node_t *right;

    node_t *parent;
};

Bydd yr erthygl yn cynnwys mwy o luniau a theori na chod. Gellir gweld y cod yn y ddolen isod.

Pwysau

I gyflawni hyn, cafodd y goeden ychydig o addasiad, ychwanegwyd gwybodaeth ychwanegol amdano pwysau nôd. Pwysau'r nod yw nifer o ddisgynyddion y nod hwn + 1 (pwysau un elfen).

Swyddogaeth ar gyfer cael pwysau nod:

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

    return 0;
}

Mae pwysau'r daflen yn gyfatebol gyfartal i 0.

Nesaf, gadewch i ni symud ymlaen at gynrychiolaeth weledol o enghraifft o goeden o'r fath. Du bydd yr allwedd nod yn cael ei ddangos mewn lliw (ni fydd y gwerth yn cael ei ddangos, gan nad yw hyn yn angenrheidiol), mewn coch - pwysau cwlwm, gwyrdd - mynegai nodau.

Pan fydd ein coeden yn wag, ei phwysau yw 0. Gadewch i ni ychwanegu elfen wraidd ati:

Mae pwysau'r goeden yn dod yn 1, mae pwysau'r elfen wreiddiau yn dod yn 1. Pwysau'r elfen wreiddiau yw pwysau'r goeden.

Gadewch i ni ychwanegu ychydig mwy o elfennau:

Bob tro yr ychwanegir elfen newydd, rydym yn mynd i lawr y nodau ac yn cynyddu rhifydd pwysau pob nod a basiwyd. Pan fydd nod newydd yn cael ei greu, rhoddir pwysau iddo 1. Os oes nod ag allwedd o'r fath eisoes yn bodoli, yna byddwn yn trosysgrifo'r gwerth ac yn mynd yn ôl i fyny at y gwraidd, gan ganslo'r newidiadau ym mhwysau'r holl nodau yr ydym wedi'u pasio.
Os yw nod yn cael ei dynnu, yna rydyn ni'n mynd i lawr ac yn lleihau pwysau'r nodau sydd wedi'u pasio.

Mynegeion

Nawr, gadewch i ni symud ymlaen at sut i fynegeio nodau. Nid yw nodau'n storio eu mynegai yn benodol, fe'i cyfrifir yn seiliedig ar bwysau'r nodau. Pe byddent yn storio eu mynegai, yna byddai ei angen O (n) amser i ddiweddaru mynegeion yr holl nodau ar ôl pob newid yn y goeden.
Gadewch i ni symud ymlaen at gynrychiolaeth weledol. Mae ein coeden yn wag, gadewch i ni ychwanegu'r nod 1af ati:

Mae gan y nod cyntaf fynegai 0, ac yn awr mae 2 achos yn bosibl. Yn y cyntaf, bydd mynegai'r elfen wraidd yn newid, yn yr ail ni fydd yn newid.

Wrth y gwraidd, mae'r is-goeden chwith yn pwyso 1.

Ail achos:

Ni newidiodd mynegai'r gwreiddyn oherwydd arhosodd pwysau ei is-goeden chwith yn 0.

Mae mynegai nod yn cael ei gyfrifo fel pwysau ei is-goeden chwith + y nifer sy'n cael ei basio o'r rhiant. Beth yw'r rhif hwn?, Dyma'r rhifydd mynegai, i ddechrau mae'n hafal i 0, achos nid oes gan y gwraidd riant. Yna mae'r cyfan yn dibynnu ar ble rydyn ni'n mynd i lawr at y plentyn chwith neu'r un iawn. Os i'r chwith, yna ni chaiff unrhyw beth ei ychwanegu at y cownter. Os byddwn yn ychwanegu mynegai'r nod cyfredol i'r un cywir.

Er enghraifft, sut mae mynegai elfen ag allwedd 8 (plentyn cywir y gwreiddyn) yn cael ei gyfrifo. Dyma "Mynegai Gwraidd" + "pwysau is-goeden chwith y nod gydag allwedd 8" + "1" == 3 + 2 + 1 == 6
Mynegai'r elfen ag allwedd 6 fydd "Mynegai Gwraidd" + 1 == 3 + 1 == 4

Yn unol â hynny, mae'n cymryd amser i gael a dileu elfen yn ôl mynegai O (log n), oherwydd er mwyn cael yr elfen ddymunol mae'n rhaid i ni ddod o hyd iddi yn gyntaf (ewch i lawr o'r gwraidd i'r elfen hon).

Dyfnder

Yn seiliedig ar y pwysau, gallwch hefyd gyfrifo dyfnder y goeden. Angenrheidiol ar gyfer cydbwyso.
I wneud hyn, rhaid i bwysau'r nod cerrynt gael ei dalgrynnu i'r rhif cyntaf i bŵer 2 sy'n fwy na neu'n hafal i'r pwysau a roddwyd a chymryd y logarithm deuaidd ohono. Bydd hyn yn rhoi dyfnder y goeden i ni, gan dybio ei bod yn gytbwys. Mae'r goeden yn gytbwys ar ôl mewnosod elfen newydd. Ni fyddaf yn rhoi theori am sut i gydbwyso coed. Mae'r codau ffynhonnell yn darparu swyddogaeth gydbwyso.

Cod ar gyfer trosi pwysau i ddyfnder.

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

Canlyniadau

• mewnosod elfen newydd yn digwydd yn O (log n)
• mae dileu elfen yn ôl rhif cyfresol yn digwydd yn O (log n)
• mae cael elfen trwy rif cyfresol yn digwydd yn O (log n)

Cyflymder O (log n) Rydym yn talu am y ffaith bod yr holl ddata yn cael ei storio ar ffurf didoli.

Nid wyf yn gwybod lle gallai strwythur o'r fath fod yn ddefnyddiol. Dim ond pos i ddeall sut mae coed yn gweithio unwaith eto. Diolch am eich sylw.

cyfeiriadau

• Cod ffynhonnell coed

Mae'r prosiect yn cynnwys data prawf i wirio cyflymder gweithredu. Mae'r goeden yn llenwi 1000000 elfennau. Ac mae yna ddileu, mewnosod ac adalw dilyniannol o elfennau 1000000 unwaith. Hynny yw 3000000 gweithrediadau. Roedd y canlyniad yn eithaf da ~ 8 eiliad.

Ffynhonnell: hab.com