មែកធាងគោលពីរដែលបានធ្វើលិបិក្រម

ខ្ញុំបានឆ្លងកាត់ប្រភេទនៃបញ្ហាដូចខាងក្រោម។ វាចាំបាច់ក្នុងការអនុវត្តធុងផ្ទុកទិន្នន័យដែលផ្តល់នូវមុខងារដូចខាងក្រោមៈ

• បញ្ចូលធាតុថ្មី។
• យកធាតុចេញដោយលេខសៀរៀល
• ទទួលបានធាតុដោយលេខធម្មតា។
• ទិន្នន័យត្រូវបានរក្សាទុកក្នុងទម្រង់តម្រៀប

ទិន្នន័យត្រូវបានបន្ថែម និងដកចេញឥតឈប់ឈរ រចនាសម្ព័ន្ធត្រូវតែធានាបាននូវល្បឿនប្រតិបត្តិការលឿន។ ដំបូងខ្ញុំបានព្យាយាមអនុវត្តរឿងបែបនេះដោយប្រើធុងស្តង់ដារពី 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.

បន្ទាប់មក យើងបន្តទៅការតំណាងដែលមើលឃើញនៃឧទាហរណ៍នៃដើមឈើបែបនេះ។ ខ្មៅ គ្រាប់ចុចថ្នាំងនឹងត្រូវបានបង្ហាញជាពណ៌ (តម្លៃនឹងមិនត្រូវបានបង្ហាញទេព្រោះនេះមិនចាំបាច់ទេ) ក្រហម - ទំងន់ knot, បៃតង។ - សន្ទស្សន៍ថ្នាំង។

នៅពេលដែលដើមឈើរបស់យើងទទេ ទម្ងន់របស់វាគឺ 0។ ចូរបន្ថែមធាតុឫសទៅវា៖

ទំងន់របស់មែកធាងក្លាយជា 1 ទំងន់នៃធាតុឫសក្លាយជា 1. ទំងន់នៃធាតុឫសគឺជាទំងន់នៃដើមឈើ។

តោះបន្ថែមធាតុមួយចំនួនទៀត៖

រាល់ពេលដែលធាតុថ្មីត្រូវបានបន្ថែម យើងចុះក្រោមថ្នាំង និងបង្កើនទម្ងន់នៃថ្នាំងនីមួយៗដែលបានឆ្លងកាត់។ នៅពេលដែលថ្នាំងថ្មីត្រូវបានបង្កើត ទម្ងន់មួយត្រូវបានផ្តល់ទៅឱ្យវា។ 1. ប្រសិនបើថ្នាំងដែលមានកូនសោបែបនេះមានរួចហើយ នោះយើងនឹងសរសេរជាន់ពីលើតម្លៃ ហើយត្រលប់ទៅឫសវិញ ដោយលុបចោលការផ្លាស់ប្តូរទម្ងន់នៃថ្នាំងទាំងអស់ដែលយើងបានឆ្លងកាត់។
ប្រសិនបើថ្នាំងមួយកំពុងត្រូវបានដកចេញ នោះយើងចុះក្រោម ហើយបន្ថយទម្ងន់នៃថ្នាំងដែលបានឆ្លងកាត់។

សន្ទស្សន៍

ឥឡូវនេះសូមបន្តទៅរបៀបធ្វើលិបិក្រមថ្នាំង។ ថ្នាំងមិនរក្សាទុកលិបិក្រមរបស់ពួកគេច្បាស់លាស់ទេ វាត្រូវបានគណនាដោយផ្អែកលើទម្ងន់នៃថ្នាំង។ ប្រសិនបើពួកគេរក្សាទុកសន្ទស្សន៍របស់ពួកគេ នោះវានឹងត្រូវបានទាមទារ អូរ (n) ពេលវេលាដើម្បីធ្វើបច្ចុប្បន្នភាពលិបិក្រមនៃថ្នាំងទាំងអស់បន្ទាប់ពីការផ្លាស់ប្តូរនីមួយៗនៅក្នុងមែកធាង។
ចូរបន្តទៅការតំណាងដែលមើលឃើញ។ មែកធាងរបស់យើងទទេ តោះបន្ថែមថ្នាំងទី 1 ទៅវា៖

ថ្នាំងទីមួយមានលិបិក្រម 0ហើយឥឡូវនេះ 2 ករណីអាចធ្វើទៅបាន។ នៅក្នុងទីមួយ លិបិក្រមនៃធាតុឫសនឹងផ្លាស់ប្តូរ ទីពីរវានឹងមិនផ្លាស់ប្តូរទេ។

នៅឫស មែកធាងរងខាងឆ្វេងមានទម្ងន់ ១.

ករណីទីពីរ៖

លិបិក្រមនៃឫសមិនផ្លាស់ប្តូរទេ ដោយសារទម្ងន់នៃមែកធាងរងខាងឆ្វេងរបស់វានៅតែ 0។

សន្ទស្សន៍​នៃ​ថ្នាំង​ត្រូវ​បាន​គណនា​ជា​ទម្ងន់​នៃ​អនុមែកធាង​ខាង​ឆ្វេង​របស់​វា + លេខ​ដែល​បាន​ឆ្លង​ពី​មេ។ តើ​លេខ​នេះ​ជា​លេខ​អ្វី?, នេះ​ជា​សន្ទស្សន៍​រាប់, ដំបូង​វា​ស្មើ​នឹង 0, ដោយសារតែ ឫសមិនមានមេ។ បន្ទាប់មកវាទាំងអស់គឺអាស្រ័យលើកន្លែងដែលយើងចុះទៅកូនខាងឆ្វេងឬខាងស្តាំ។ ប្រសិនបើនៅខាងឆ្វេង នោះគ្មានអ្វីត្រូវបានបន្ថែមទៅបញ្ជរទេ។ ប្រសិនបើយើងបន្ថែមសន្ទស្សន៍នៃថ្នាំងបច្ចុប្បន្នទៅខាងស្តាំ។

ឧទាហរណ៍ របៀប​ដែល​សន្ទស្សន៍​នៃ​ធាតុ​ដែល​មាន​គន្លឹះ 8 (កូន​ត្រឹមត្រូវ​នៃ​ឫស) ត្រូវ​បាន​គណនា។ នេះគឺជា "សន្ទស្សន៍ឫស" + "ទម្ងន់នៃមែកធាងរងខាងឆ្វេងនៃថ្នាំងដែលមានគន្លឹះ 8" + "1" == 3 + 2 + 1 == 6
លិបិក្រមនៃធាតុដែលមានគន្លឹះ 6 នឹងជា "សន្ទស្សន៍ឫស" + 1 == 3 + 1 == 4

ដូច្នោះហើយ វាត្រូវការពេលវេលាដើម្បីទទួលបាន និងលុបធាតុដោយលិបិក្រម O (log n)ដោយ​សារ​តែ​ដើម្បី​ទទួល​បាន​ធាតុ​ដែល​ចង់​បាន​យើង​ត្រូវ​តែ​ស្វែង​រក​វា​ជា​ដំបូង (ចុះ​ពី root ទៅ​ធាតុ​នេះ​) ។

ជម្រៅ

ដោយផ្អែកលើទម្ងន់អ្នកក៏អាចគណនាជម្រៅនៃដើមឈើផងដែរ។ ចាំបាច់សម្រាប់តុល្យភាព។
ដើម្បីធ្វើដូចនេះទម្ងន់នៃថ្នាំងបច្ចុប្បន្នត្រូវតែបង្គត់ទៅលេខទីមួយទៅថាមពលនៃ 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 (log n)
• ការលុបធាតុដោយលេខសៀរៀលកើតឡើងនៅក្នុង O (log n)
• ការទទួលបានធាតុដោយលេខសៀរៀលកើតឡើងនៅក្នុង O (log n)

ល្បឿន O (log n) យើងចំណាយលើការពិតដែលថាទិន្នន័យទាំងអស់ត្រូវបានរក្សាទុកក្នុងទម្រង់តម្រៀប។

ខ្ញុំមិនដឹងថាកន្លែងណាដែលរចនាសម្ព័ន្ធបែបនេះអាចមានប្រយោជន៍នោះទេ។ គ្រាន់តែជាល្បែងផ្គុំរូបដើម្បីយល់ពីរបៀបដែលដើមឈើធ្វើការ។ សូម​អរគុណ​ចំពោះ​ការ​យកចិត្ត​ទុកដាក់​របស់​លោកអ្នក។

សេចក្តីយោង

• កូដប្រភពដើមឈើ

គម្រោងនេះមានទិន្នន័យសាកល្បង ដើម្បីពិនិត្យមើលល្បឿនប្រតិបត្តិការ។ ដើមឈើកំពុងបំពេញ 1000000 ធាតុ។ ហើយមានការលុបជាបន្តបន្ទាប់ ការបញ្ចូល និងការទាញយកធាតុ 1000000 ម្តង។ នោះគឺជា 3000000 ប្រតិបត្តិការ។ លទ្ធផលបានប្រែទៅជាល្អណាស់ ~ 8 វិនាទី។

ប្រភព: www.habr.com