Ինդեքսավորված երկուական ծառ

Ես հանդիպեցի հետևյալ տեսակի խնդրին. Անհրաժեշտ է իրականացնել տվյալների պահպանման կոնտեյներ, որն ապահովում է հետևյալ ֆունկցիոնալությունը.

• տեղադրել նոր տարր
• հեռացնել տարրը ըստ սերիական համարի
• տարր ստանալ ըստ հերթական թվի
• տվյալները պահվում են տեսակավորված ձևով

Տվյալներն անընդհատ ավելացվում և հեռացվում են, կառուցվածքը պետք է ապահովի արագ շահագործման արագություն։ Սկզբում ես փորձեցի նման բան իրականացնել՝ օգտագործելով ստանդարտ կոնտեյներներ ստ. Այս ճանապարհը հաջողությամբ չպսակվեց և հասկացավ, որ ես ինքս ինչ-որ բան պետք է իրականացնեմ։ Միակ բանը, որ մտքովս անցավ, երկուական որոնման ծառ օգտագործելն էր: Քանի որ այն համապատասխանում է տվյալների արագ տեղադրման, ջնջման և տեսակավորված ձևով պահպանման պահանջին: Մնում է միայն պարզել, թե ինչպես կարելի է ինդեքսավորել բոլոր տարրերը և վերահաշվարկել ինդեքսները, երբ ծառը փոխվի:

struct node_s {    
    data_t data;

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

    node_t *left;
    node_t *right;

    node_t *parent;
};

Հոդվածը կպարունակի ավելի շատ նկարներ և տեսություն, քան կոդ: Կոդը կարելի է դիտել ստորև նշված հղումով։

Քաշ

Դրան հասնելու համար ծառը ենթարկվել է մի փոքր փոփոխության, դրա մասին հավելյալ տեղեկություն է ավելացվել քաշը հանգույց. Հանգույցի քաշն է այս հանգույցի ժառանգների թիվը + 1 (մեկ տարրի քաշը):

Հանգույցի քաշը ստանալու գործառույթ.

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

    return 0;
}

Թերթի քաշը համապատասխանաբար հավասար է 0.

Հաջորդը, եկեք անցնենք նման ծառի օրինակի տեսողական ներկայացմանը: Սեւ հանգույցի ստեղնը կցուցադրվի գունավոր (արժեքը չի ցուցադրվի, քանի որ դա անհրաժեշտ չէ), կարմիր - հանգույցի քաշը, կանաչ - հանգույցի ինդեքս:

Երբ մեր ծառը դատարկ է, նրա քաշը 0 է: Եկեք դրան ավելացնենք արմատային տարր.

Ծառի քաշը դառնում է 1, արմատային տարրի քաշը՝ 1։ Արմատային տարրի կշիռը ծառի կշիռն է։

Ավելացնենք ևս մի քանի տարրեր.

Ամեն անգամ, երբ նոր տարր ավելացվում է, մենք իջնում ​​ենք հանգույցները և ավելացնում յուրաքանչյուր անցած հանգույցի քաշի հաշվիչը: Երբ ստեղծվում է նոր հանգույց, դրան նշանակվում է կշիռ 1. Եթե ​​նման բանալիով հանգույց արդեն գոյություն ունի, ապա մենք կվերագրենք արժեքը և կվերադառնանք դեպի արմատ՝ չեղյալ համարելով մեր անցած բոլոր հանգույցների կշիռների փոփոխությունները։
Եթե ​​հանգույցը հեռացվում է, ապա մենք իջնում ​​ենք և նվազեցնում անցած հանգույցների կշիռները:

Ցուցանիշները

Այժմ եկեք անցնենք, թե ինչպես կարելի է ինդեքսավորել հանգույցները: Հանգույցները հստակորեն չեն պահպանում իրենց ինդեքսը, այն հաշվարկվում է հանգույցների քաշի հիման վրա: Եթե ​​նրանք պահեին իրենց ինդեքսը, ապա դա կպահանջվեր O (n) ծառի յուրաքանչյուր փոփոխությունից հետո բոլոր հանգույցների ինդեքսները թարմացնելու ժամանակը:
Եկեք անցնենք տեսողական ներկայացմանը: Մեր ծառը դատարկ է, եկեք դրան ավելացնենք 1-ին հանգույցը.

Առաջին հանգույցն ունի ինդեքս 0, իսկ այժմ հնարավոր է 2 դեպք։ Առաջինում արմատային տարրի ինդեքսը կփոխվի, երկրորդում՝ չի փոխվի։

Արմատում ձախ ենթածառը կշռում է 1:

Երկրորդ դեպք.

Արմատի ինդեքսը չի փոխվել, քանի որ նրա ձախ ենթածառի քաշը մնացել է 0։

Հանգույցի ինդեքսը հաշվարկվում է որպես նրա ձախ ենթածառի կշիռ + ծնողից փոխանցված թիվը: Ո՞րն է այս թիվը: Սա ցուցիչի հաշվիչն է, սկզբում այն ​​հավասար է 0, որովհետեւ արմատը չունի ծնող: Հետո ամեն ինչ կախված է նրանից, թե որտեղ ենք իջնում ​​ձախ երեխային, թե աջին: Եթե ​​դեպի ձախ, ապա ոչինչ չի ավելացվում հաշվիչին: Եթե ​​աջին ավելացնենք ընթացիկ հանգույցի ինդեքսը.

Օրինակ՝ ինչպես է հաշվարկվում 8 բանալիով տարրի ինդեքսը (արմատի ճիշտ զավակ): Սա «Արմատային ինդեքս» + «8 բանալիով հանգույցի ձախ ենթածառի կշիռն է» + «1» == 3 + 2 + 1 == 6
6 բանալիով տարրի ինդեքսը կլինի «Արմատային ինդեքս» + 1 == 3 + 1 == 4

Համապատասխանաբար, ժամանակ է պահանջվում տարրը ըստ ինդեքսների ստանալու և ջնջելու համար O (տեղեկամատյան n), քանի որ ցանկալի տարրը ստանալու համար նախ պետք է գտնել այն (արմատից իջնել այս տարրը)։

Խորությունը

Ելնելով քաշից՝ կարող եք նաև հաշվարկել ծառի խորությունը։ Հավասարակշռելու համար անհրաժեշտ է.
Դա անելու համար ընթացիկ հանգույցի կշիռը պետք է կլորացվի առաջին թվին մինչև 2-ի հզորությունը, որը մեծ է կամ հավասար է տվյալ կշռին և դրանից վերցնել երկուական լոգարիթմը։ Սա մեզ կտա ծառի խորությունը՝ ենթադրելով, որ այն հավասարակշռված է: Ծառը հավասարակշռված է նոր տարր մտցնելուց հետո: Ես տեսություն չեմ տա այն մասին, թե ինչպես հավասարակշռել ծառերը: Աղբյուրի կոդերը ապահովում են հավասարակշռման գործառույթ:

Քաշը խորության փոխակերպման կոդը:

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

Արդյունքները

• նոր տարրի տեղադրումը տեղի է ունենում O (տեղեկամատյան n)
• տարրը սերիական համարով ջնջելը տեղի է ունենում O (տեղեկամատյան n)
• սերիական համարով տարր ստանալը տեղի է ունենում O (տեղեկամատյան n)

Արագություն O (տեղեկամատյան n) Մենք վճարում ենք այն փաստի համար, որ բոլոր տվյալները պահվում են տեսակավորված ձևով:

Ես չգիտեմ, թե որտեղ կարող է օգտակար լինել նման կառույցը։ Պարզապես գլուխկոտրուկ՝ ևս մեկ անգամ հասկանալու համար, թե ինչպես են աշխատում ծառերը: Շնորհակալություն ուշադրության համար.

Սայլակ

• Ծառի սկզբնական կոդը

Նախագիծը պարունակում է թեստային տվյալներ՝ աշխատանքի արագությունը ստուգելու համար: Ծառը լցվում է 1000000 տարրեր. Եվ տեղի է ունենում տարրերի հաջորդական ջնջում, տեղադրում և առբերում 1000000 մեկ անգամ. Այն է 3000000 գործառնություններ. Արդյունքը բավականին լավ է ստացվել ~ 8 վայրկյան։

Source: www.habr.com