ఇండెక్స్డ్ బైనరీ ట్రీ

నేను ఈ క్రింది రకమైన సమస్యను ఎదుర్కొన్నాను. కింది కార్యాచరణను అందించే డేటా నిల్వ కంటైనర్‌ను అమలు చేయడం అవసరం:

• కొత్త మూలకాన్ని చొప్పించండి
• క్రమ సంఖ్య ద్వారా మూలకాన్ని తీసివేయండి
• ఆర్డినల్ సంఖ్య ద్వారా మూలకాన్ని పొందండి
• డేటా క్రమబద్ధీకరించబడిన రూపంలో నిల్వ చేయబడుతుంది

డేటా నిరంతరం జోడించబడుతోంది మరియు తీసివేయబడుతుంది, నిర్మాణం వేగవంతమైన ఆపరేషన్ వేగాన్ని నిర్ధారించాలి. మొదట నేను ప్రామాణిక కంటైనర్లను ఉపయోగించి అటువంటి విషయాన్ని అమలు చేయడానికి ప్రయత్నించాను గంటలు. ఈ మార్గం విజయానికి పట్టం కట్టలేదు మరియు నేనే ఏదో ఒకటి అమలు చేయాలనే అవగాహన వచ్చింది. బైనరీ శోధన చెట్టును ఉపయోగించడం మాత్రమే గుర్తుకు వచ్చింది. ఎందుకంటే ఇది క్రమబద్ధీకరించబడిన రూపంలో డేటాను వేగంగా చొప్పించడం, తొలగించడం మరియు నిల్వ చేయడం వంటి అవసరాలను తీరుస్తుంది. చెట్టు మారినప్పుడు అన్ని మూలకాలను ఇండెక్స్ చేయడం మరియు సూచికలను తిరిగి లెక్కించడం ఎలాగో గుర్తించడం మాత్రమే మిగిలి ఉంది.

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

దీని ప్రకారం, ఇండెక్స్ ద్వారా మూలకాన్ని పొందడానికి మరియు తొలగించడానికి సమయం పడుతుంది 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