የተጠቆመ ሁለትዮሽ ዛፍ

የሚከተለው ዓይነት ችግር አጋጥሞኛል. የሚከተሉትን ተግባራት የሚያቀርብ የውሂብ ማከማቻ መያዣን መተግበር አስፈላጊ ነው.

• አዲስ ንጥረ ነገር አስገባ
• ኤለመንቱን በተከታታይ ቁጥር ያስወግዱ
• ኤለመንቱን በመደበኛ ቁጥር ያግኙ
• ውሂብ በተደረደረ መልኩ ይከማቻል

ውሂብ ያለማቋረጥ እየተጨመረ እና እየተወገደ ነው, መዋቅሩ ፈጣን የስራ ፍጥነት ማረጋገጥ አለበት. መጀመሪያ ላይ እንደዚህ አይነት ነገር ተግባራዊ ለማድረግ ሞከርኩ መደበኛ መያዣዎች ከ std. ይህ መንገድ በስኬት አልተጫነም እና እኔ ራሴ የሆነ ነገር መተግበር እንዳለብኝ ግንዛቤ መጣ። ወደ አእምሯችን የመጣው ብቸኛው ነገር ሁለትዮሽ ፍለጋ ዛፍ መጠቀም ነበር. ምክንያቱም በፍጥነት የማስገባት ፣ የመሰረዝ እና የማከማቸት ሁኔታን ያሟላል። የቀረው ሁሉ ዛፉ በሚቀየርበት ጊዜ ሁሉንም ንጥረ ነገሮች እንዴት እንደሚጠቁሙ እና ጠቋሚዎቹን እንደገና ማስላት ብቻ ነው።

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. እንደዚህ ያለ ቁልፍ ያለው መስቀለኛ መንገድ ቀድሞውኑ ካለ ፣ እሴቱን እንፅፋለን እና ወደ ሥሩ እንመለሳለን ፣ ያለፍንባቸውን የሁሉም አንጓዎች ክብደት ለውጦችን እንሰርዛለን።
አንድ መስቀለኛ መንገድ እየተወሰደ ከሆነ, ወደ ታች እንወርዳለን እና ያለፈውን አንጓዎች ክብደቶች እንቀንሳለን.

ማውጫዎች

አሁን ወደ ኖዶች እንዴት እንደሚጠቁሙ እንሂድ። አንጓዎች የመረጃ ጠቋሚቸውን በግልፅ አያከማቹም, በኖዶች ክብደት ላይ ተመስርቶ ይሰላል. መረጃ ጠቋሚቸውን ካከማቹ ከዚያ ያስፈልጋል ሆይ (n) በዛፉ ላይ ከእያንዳንዱ ለውጥ በኋላ የሁሉንም አንጓዎች ጠቋሚዎች ለማዘመን ጊዜ.
ወደ ምስላዊ ውክልና እንሂድ። ዛፋችን ባዶ ነው፣ 1ኛውን መስቀለኛ መንገድ እንጨምርበት፡-

የመጀመሪያው አንጓ ጠቋሚ አለው 0እና አሁን 2 ጉዳዮች ሊኖሩ ይችላሉ። በመጀመሪያው ላይ, የስር ኤለመንት ኢንዴክስ ይለወጣል, በሁለተኛው ውስጥ አይለወጥም.

በሥሩ ፣ የግራ ንዑስ ዛፍ 1 ይመዝናል።

ሁለተኛ ጉዳይ፡-

የሥሩ መረጃ ጠቋሚ አልተቀየረም ምክንያቱም የግራ ዛፉ ክብደት 0 ይቀራል።

የመስቀለኛ መንገድ መረጃ ጠቋሚ እንደ ግራው ንዑስ ዛፍ ክብደት + ከወላጅ የተላለፈው ቁጥር ይሰላል። ይህ ቁጥር ምንድን ነው?, ይህ ጠቋሚ ቆጣሪ ነው, መጀመሪያ ላይ እኩል ነው 0, ምክንያቱም ሥሩ ወላጅ የለውም። ከዚያ ሁሉም ወደ ግራ ልጅ ወይም ወደ ቀኝ ወዴት እንደምንወርድ ይወሰናል. ወደ ግራ ከሆነ, ከዚያም ወደ ቆጣሪው ምንም ነገር አይጨመርም. የአሁኑን መስቀለኛ መንገድ ኢንዴክስ ወደ ትክክለኛው ካከልን.

ለምሳሌ ፣ የቁልፍ 8 (የሥሩ ትክክለኛ ልጅ) ያለው የአንድ አካል መረጃ ጠቋሚ እንዴት እንደሚሰላ። ይህ "Root Index" + "የግራ ንኡስ ዛፍ ክብደት ከቁልፍ 8" + "1" == 3 + 2 + 1 == 6
ቁልፍ 6 ያለው የንጥሉ መረጃ ጠቋሚ "Root Index" + 1 == 3 + 1 == ይሆናል. 4

በዚህ መሠረት አንድን ንጥረ ነገር በመረጃ ጠቋሚ ለማግኘት እና ለመሰረዝ ጊዜ ይወስዳል ኦ (ምዝግብ ማስታወሻ 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));
}

ውጤቶች

• አዲስ ኤለመንት ማስገባት በ ውስጥ ይከሰታል ኦ (ምዝግብ ማስታወሻ n)
• አንድን ንጥረ ነገር በተከታታይ ቁጥር መሰረዝ በ ውስጥ ይከሰታል ኦ (ምዝግብ ማስታወሻ n)
• አንድን ንጥረ ነገር በተከታታይ ቁጥር ማግኘት በ ውስጥ ይከሰታል ኦ (ምዝግብ ማስታወሻ n)

ፍጥነት ኦ (ምዝግብ ማስታወሻ n) ሁሉም መረጃዎች በተደረደሩ መልክ የተከማቹ የመሆኑን እውነታ እንከፍላለን.

እንዲህ ዓይነቱ መዋቅር የት እንደሚጠቅም አላውቅም. ዛፎች እንዴት እንደሚሠሩ እንደገና ለመረዳት እንቆቅልሽ ብቻ ነው። ለሰጠህው አትኩሮት እናመሰግናለን.

ማጣቀሻዎች

• የዛፍ ምንጭ ኮድ

ፕሮጀክቱ የሥራውን ፍጥነት ለመፈተሽ የሙከራ ውሂብ ይዟል. ዛፉ እየሞላ ነው 1000000 ንጥረ ነገሮች. እና የንጥረ ነገሮችን በቅደም ተከተል መሰረዝ፣ ማስገባት እና ማውጣት አለ። 1000000 አንድ ጊዜ. ያውና 3000000 ስራዎች. ውጤቱ በጣም ጥሩ ሆኖ ተገኝቷል ~ 8 ሰከንድ።

ምንጭ: hab.com