અનુક્રમિત બાઈનરી વૃક્ષ

મને નીચેની પ્રકારની સમસ્યા આવી. ડેટા સ્ટોરેજ કન્ટેનર લાગુ કરવું જરૂરી છે જે નીચેની કાર્યક્ષમતા પ્રદાન કરે છે:

• નવું તત્વ દાખલ કરો
• સીરીયલ નંબર દ્વારા તત્વ દૂર કરો
• ઓર્ડિનલ નંબર દ્વારા તત્વ મેળવો
• માહિતી સૉર્ટ સ્વરૂપમાં સંગ્રહિત થાય છે

ડેટા સતત ઉમેરવામાં આવે છે અને દૂર કરવામાં આવે છે, રચનાએ ઝડપી કામગીરીની ગતિને સુનિશ્ચિત કરવી જોઈએ. પહેલા મેં પ્રમાણભૂત કન્ટેનરનો ઉપયોગ કરીને આવી વસ્તુને અમલમાં મૂકવાનો પ્રયાસ કર્યો ધો. આ માર્ગ સફળતાનો તાજ પહેર્યો ન હતો અને સમજણ આવી કે મારે જાતે કંઈક અમલમાં મૂકવાની જરૂર છે. એક જ વસ્તુ જે ધ્યાનમાં આવી તે દ્વિસંગી શોધ વૃક્ષનો ઉપયોગ કરવાનો હતો. કારણ કે તે સૉર્ટ કરેલા સ્વરૂપમાં ડેટાના ઝડપી નિવેશ, કાઢી નાખવા અને સંગ્રહની જરૂરિયાતને પૂર્ણ કરે છે. બધા તત્વોને કેવી રીતે અનુક્રમિત કરવું અને જ્યારે વૃક્ષ બદલાય ત્યારે સૂચકાંકોની પુન: ગણતરી કેવી રીતે કરવી તે શોધવાનું બાકી છે.

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. જો આવી કી સાથેનો નોડ પહેલેથી જ અસ્તિત્વમાં છે, તો પછી આપણે મૂલ્યને ઓવરરાઈટ કરીશું અને રુટ પર પાછા જઈશું, અમે પસાર કરેલા તમામ નોડ્સના વજનમાંના ફેરફારોને રદ કરીશું.
જો કોઈ નોડ દૂર કરવામાં આવી રહ્યો હોય, તો અમે નીચે જઈએ છીએ અને પસાર થયેલા ગાંઠોના વજનમાં ઘટાડો કરીએ છીએ.

સૂચકાંકો

હવે ચાલો નોડ્સ કેવી રીતે ઇન્ડેક્સ કરવા તે તરફ આગળ વધીએ. નોડ્સ સ્પષ્ટપણે તેમના અનુક્રમણિકાને સંગ્રહિત કરતા નથી, તે ગાંઠોના વજનના આધારે ગણવામાં આવે છે. જો તેઓ તેમની અનુક્રમણિકા સંગ્રહિત કરે છે, તો તે જરૂરી રહેશે ઓ (એન) વૃક્ષમાં દરેક ફેરફાર પછી તમામ ગાંઠોના ઇન્ડેક્સને અપડેટ કરવાનો સમય.
ચાલો દ્રશ્ય રજૂઆત તરફ આગળ વધીએ. અમારું વૃક્ષ ખાલી છે, ચાલો તેમાં 1 લી નોડ ઉમેરીએ:

પ્રથમ નોડમાં ઇન્ડેક્સ હોય છે 0, અને હવે 2 કેસ શક્ય છે. પ્રથમમાં, મૂળ તત્વની અનુક્રમણિકા બદલાશે, બીજામાં તે બદલાશે નહીં.

મૂળમાં, ડાબા સબટ્રીનું વજન 1 છે.

બીજો કેસ:

મૂળની અનુક્રમણિકા બદલાઈ નથી કારણ કે તેના ડાબા સબટ્રીનું વજન 0 રહ્યું છે.

નોડના અનુક્રમણિકાની ગણતરી તેના ડાબા સબટ્રીના વજન + માતાપિતા પાસેથી પસાર કરાયેલ સંખ્યા તરીકે કરવામાં આવે છે. આ સંખ્યા શું છે?, આ ઇન્ડેક્સ કાઉન્ટર છે, શરૂઆતમાં તે બરાબર છે 0, કારણ કે મૂળને કોઈ પિતૃ નથી. પછી તે બધું તેના પર નિર્ભર કરે છે કે આપણે ડાબી બાજુના બાળક અથવા જમણી તરફ ક્યાં જઈએ છીએ. જો ડાબી બાજુએ, તો પછી કાઉન્ટરમાં કંઈ ઉમેરવામાં આવતું નથી. જો આપણે વર્તમાન નોડની અનુક્રમણિકાને જમણી બાજુએ ઉમેરીએ.

ઉદાહરણ તરીકે, કી 8 (રુટનું જમણું બાળક) સાથેના તત્વની અનુક્રમણિકા કેવી રીતે ગણવામાં આવે છે. આ છે "રુટ ઇન્ડેક્સ" + "કી 8 સાથે નોડના ડાબા સબટ્રીનું વજન" + "1" == 3 + 2 + 1 == 6
કી 6 સાથેના તત્વની અનુક્રમણિકા "રુટ ઇન્ડેક્સ" + 1 == 3 + 1 == હશે. 4

તદનુસાર, અનુક્રમણિકા દ્વારા તત્વ મેળવવા અને કાઢી નાખવામાં સમય લાગે છે ઓ (લોગ એન), કારણ કે ઇચ્છિત તત્વ મેળવવા માટે આપણે પહેલા તેને શોધવું પડશે (મૂળથી નીચે આ તત્વ પર જવું).

ઊંડાઈ

વજનના આધારે, તમે વૃક્ષની ઊંડાઈની પણ ગણતરી કરી શકો છો. સંતુલન માટે જરૂરી.
આ કરવા માટે, વર્તમાન નોડનું વજન પ્રથમ નંબરથી 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));
}

પરિણામો

• નવા તત્વનું નિવેશ થાય છે ઓ (લોગ એન)
• સીરીયલ નંબર દ્વારા તત્વ કાઢી નાખવામાં આવે છે ઓ (લોગ એન)
• સીરીયલ નંબર દ્વારા તત્વ મેળવવામાં થાય છે ઓ (લોગ એન)

ઝડપ ઓ (લોગ એન) અમે એ હકીકત માટે ચૂકવણી કરીએ છીએ કે તમામ ડેટા સૉર્ટ સ્વરૂપમાં સંગ્રહિત છે.

મને ખબર નથી કે આવી રચના ક્યાં ઉપયોગી થઈ શકે. વૃક્ષો કેવી રીતે કાર્ય કરે છે તે સમજવા માટે માત્ર એક કોયડો. તમારા ધ્યાન બદલ આભાર.

સંદર્ભો

• વૃક્ષ સ્ત્રોત કોડ

પ્રોજેક્ટમાં કામગીરીની ઝડપ ચકાસવા માટે ટેસ્ટ ડેટા છે. વૃક્ષ ભરાઈ રહ્યું છે 1000000 તત્વો અને તત્વોનું ક્રમિક કાઢી નાખવા, નિવેશ અને પુનઃપ્રાપ્તિ છે 1000000 એકવાર તે જ 3000000 કામગીરી પરિણામ ખૂબ સારું ~ 8 સેકન્ડમાં બહાર આવ્યું.

સોર્સ: www.habr.com