Isihlahla kanambambili esinenkomba

Ngihlangabezane nalolu hlobo lwenkinga elandelayo. Kuyadingeka ukusebenzisa isitsha sokugcina idatha esihlinzeka ngokusebenza okulandelayo:

• faka isici esisha
• susa isici ngenombolo ye-serial
• thola isici ngenombolo ye-ordinal
• idatha igcinwa ngendlela ehleliwe

Idatha ihlale yengezwa futhi isuswa, isakhiwo kufanele siqinisekise isivinini sokusebenza okusheshayo. Ekuqaleni ngazama ukwenza into enjalo ngisebenzisa iziqukathi ezijwayelekile ezivela amahora. Le ndlela ayizange ithweswe umqhele wempumelelo futhi kwafika ukuqonda ukuthi ngidinga ukwenza okuthile mina ngokwami. Okuwukuphela kwento eyafika emqondweni kwakuwukusebenzisa isihlahla sokucinga kanambambili. Ngoba ihlangabezana nemfuneko yokufakwa ngokushesha, ukususwa nokugcinwa kwedatha ngendlela ehleliwe. Okusele nje ukuthola indlela yokukhomba zonke izakhi nokubala kabusha ama-indices lapho isihlahla sishintsha.

struct node_s {    
    data_t data;

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

    node_t *left;
    node_t *right;

    node_t *parent;
};

I-athikili izoqukatha izithombe eziningi kanye nethiyori kunekhodi. Ikhodi ingabonwa kusixhumanisi esingezansi.

Isisindo

Ukuze kuzuzwe lokhu, isihlahla senziwa ukuguqulwa okuncane, ulwazi olwengeziwe lwengezwe mayelana isisindo indawo. Isisindo se-node si inani lenzalo yale nodi + 1 (isisindo sesici esisodwa).

Umsebenzi wokuthola isisindo se-node:

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

    return 0;
}

Isisindo seshidi silingana ne 0.

Okulandelayo, ake siqhubekele ekuboniseni okubonakalayo kwesibonelo somuthi onjalo. Mnyama ukhiye we-node uzoboniswa ngombala (inani ngeke liboniswe, ngoba lokhu akudingekile), ngokubomvu - isisindo sefindo, luhlaza - Inkomba ye-node.

Uma isihlahla sethu singenalutho, isisindo saso singu-0. Ake sengeze isici sempande kuso:

Isisindo somuthi siba ngu-1, isisindo sesici sempande siba 1. Isisindo sesici sempande yisisindo somuthi.

Ake sengeze ezinye izici ezimbalwa:

Ngaso sonke isikhathi lapho i-elementi entsha yengezwa, sehla ama-node futhi sandise i-counter yesisindo se-node ngayinye edlulisiwe. Lapho kwakhiwa i-node entsha, isisindo sinikezwa kuso 1. Uma i-node enokhiye onjalo isivele ikhona, sizobe sesibhala ngaphezulu inani bese sibuyela emuva empandeni, sikhansela izinguquko ezisindweni zawo wonke ama-node esiwadlulisile.
Uma i-node isuswa, khona-ke siyehla futhi sinciphise izisindo zama-node adlulisiwe.

Izinkomba

Manje ake siqhubekele endleleni yokukhomba amanodi. Ama-Node awagcini ngokucacile inkomba yawo, ibalwa ngokusekelwe kwesisindo samanodi. Uma begcine inkomba yabo, kuyodingeka O (n) isikhathi sokuvuselela izinkomba zawo wonke ama-node ngemva koshintsho ngalunye esihlahleni.
Asiqhubekele esifanekisweni. Isihlahla sethu asinalutho, ake sengeze inodi yoku-1 kuso:

Inodi yokuqala inenkomba 0, futhi manje amacala angu-2 angenzeka. Okokuqala, inkomba yesici sempande izoshintsha, okwesibili ngeke ishintshe.

Ezimpandeni, isihlahla esingaphansi kwesobunxele sinesisindo esingu-1.

Icala lesibili:

Inkomba yempande ayizange ishintshe ngenxa yokuthi isisindo somuthi wayo ongakwesokunxele sahlala singu-0.

Inkomba ye-node ibalwa njengesisindo somuthi ongaphansi waso kwesokunxele + inombolo edluliselwe kumzali. Ithini le nombolo?, Lena ikhawunta yenkomba, ekuqaleni ilingana no 0, ngoba impande ayinamzali. Khona-ke konke kuya ngokuthi sehlela kuphi enganeni yesobunxele noma kwesokudla. Uma ngakwesobunxele, akukho lutho olungeziwe kwikhawunta. Uma sengeza inkomba yenodi yamanje kwelungile.

Isibonelo, ukuthi inkomba yento enokhiye 8 (ingane efanele yempande) ibalwa kanjani. Lena "I-Root Index" + "isisindo somuthi omncane wesokunxele wenodi enokhiye 8" + "1" == 3 + 2 + 1 == 6
Inkomba yesici esinokhiye 6 izoba "I-Root Index" + 1 == 3 + 1 == 4

Ngokufanelekile, kuthatha isikhathi ukuthola nokususa into ngenkomba O (log n), ngoba ukuze sithole into esiyifunayo kufanele siqale siyithole (sehla sisuka empandeni siye kule element).

Ukujula

Ngokusekelwe kwesisindo, ungakwazi futhi ukubala ukujula kwesihlahla. Kudingeka ukulinganisa.
Ukwenza lokhu, isisindo se-node yamanje kufanele sifinyezwe enombolweni yokuqala emandleni angu-2 amakhulu noma alingana nesisindo esinikeziwe futhi kuthathwe i-logarithm kanambambili kuyo. Lokhu kuzosinika ukujula kwesihlahla, sicabange ukuthi sinokulinganisela. Isihlahla siyalingana ngemva kokufaka into entsha. Ngeke nginikeze ithiyori mayelana nendlela yokulinganisa izihlahla. Amakhodi omthombo ahlinzeka ngomsebenzi wokulinganisa.

Ikhodi yokuguqula isisindo sibe ukujula.

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

Imiphumela

• ukufakwa kwe-elementi entsha kwenzeka ku O (log n)
• ukususa i-elementi ngenombolo ye-serial kwenzeka O (log n)
• ukuthola i-elementi ngenombolo ye-serial kwenzeka O (log n)

Isivinini O (log n) Sikhokhela iqiniso lokuthi yonke idatha igcinwa ngendlela ehleliwe.

Angazi ukuthi isakhiwo esinjalo singaba usizo kuphi. Iphazili nje ukuze uqonde futhi ukuthi izihlahla zisebenza kanjani. Ngiyabonga ukulalela kwenu.

izithenjwa

• Ikhodi yomthombo wesihlahla

Iphrojekthi iqukethe idatha yokuhlola ukuhlola isivinini sokusebenza. Isihlahla siyagcwala 1000000 izakhi. Futhi kukhona ukususwa okulandelanayo, ukufakwa nokubuyiswa kwezinto 1000000 kanye. Leyo 3000000 imisebenzi. Umphumela uvele waba muhle impela ~ imizuzwana eyi-8.

Source: www.habr.com