ഇൻഡക്‌സ് ചെയ്‌ത ബൈനറി ട്രീ

ഇനിപ്പറയുന്ന തരത്തിലുള്ള ഒരു പ്രശ്നം ഞാൻ നേരിട്ടു. ഇനിപ്പറയുന്ന പ്രവർത്തനങ്ങൾ നൽകുന്ന ഒരു ഡാറ്റ സ്റ്റോറേജ് കണ്ടെയ്നർ നടപ്പിലാക്കേണ്ടത് ആവശ്യമാണ്:

• പുതിയ ഘടകം ചേർക്കുക
• സീരിയൽ നമ്പർ പ്രകാരം ഘടകം നീക്കം ചെയ്യുക
• ഓർഡിനൽ നമ്പർ പ്രകാരം ഘടകം നേടുക
• ഡാറ്റ അടുക്കിയ രൂപത്തിൽ സംഭരിച്ചിരിക്കുന്നു

ഡാറ്റ നിരന്തരം ചേർക്കുകയും നീക്കം ചെയ്യുകയും ചെയ്യുന്നു, ഘടന വേഗത്തിലുള്ള പ്രവർത്തന വേഗത ഉറപ്പാക്കണം. ആദ്യം ഞാൻ സ്റ്റാൻഡേർഡ് കണ്ടെയ്നറുകൾ ഉപയോഗിച്ച് അത്തരമൊരു കാര്യം നടപ്പിലാക്കാൻ ശ്രമിച്ചു ക്ലാസ്. ഈ പാത വിജയിച്ചില്ല, എനിക്ക് സ്വയം എന്തെങ്കിലും നടപ്പിലാക്കണം എന്ന ധാരണ വന്നു. ഒരു ബൈനറി സെർച്ച് ട്രീ ഉപയോഗിക്കുക എന്നത് മാത്രമാണ് മനസ്സിൽ വന്നത്. കാരണം, വേഗത്തിൽ ചേർക്കൽ, ഇല്ലാതാക്കൽ, അടുക്കിയ രൂപത്തിൽ ഡാറ്റ സംഭരണം എന്നിവയുടെ ആവശ്യകത ഇത് നിറവേറ്റുന്നു. എല്ലാ ഘടകങ്ങളും എങ്ങനെ സൂചികയിലാക്കാമെന്നും മരം മാറുമ്പോൾ സൂചികകൾ വീണ്ടും കണക്കാക്കാമെന്നും കണ്ടെത്തുക മാത്രമാണ് അവശേഷിക്കുന്നത്.

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) ട്രീയിലെ ഓരോ മാറ്റത്തിനും ശേഷം എല്ലാ നോഡുകളുടെയും സൂചികകൾ അപ്ഡേറ്റ് ചെയ്യാനുള്ള സമയം.
നമുക്ക് ഒരു വിഷ്വൽ പ്രാതിനിധ്യത്തിലേക്ക് പോകാം. ഞങ്ങളുടെ മരം ശൂന്യമാണ്, അതിലേക്ക് ആദ്യ നോഡ് ചേർക്കാം:

ആദ്യ നോഡിന് ഒരു സൂചികയുണ്ട് 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 സെക്കൻഡ്.

അവലംബം: www.habr.com