ဒွိသစ်ပင်အညွှန်း

အောက်ဖော်ပြပါ ပြဿနာအမျိုးအစားကို ကြုံတွေ့ခဲ့ရပါသည်။ အောက်ပါလုပ်ဆောင်ချက်များကို ပံ့ပိုးပေးသည့် ဒေတာသိုလှောင်မှုကွန်တိန်နာကို အကောင်အထည်ဖော်ရန် လိုအပ်သည်-

• အစိတ်အပိုင်းအသစ်ထည့်ပါ။
• အမှတ်စဉ်နံပါတ်ဖြင့် element ကိုဖယ်ရှားပါ။
• ပုံမှန်နံပါတ်ဖြင့် element ကိုရယူပါ။
• ဒေတာကို အမျိုးအစားခွဲထားသည့်ပုံစံဖြင့် သိမ်းဆည်းထားသည်။

ဒေတာကို အဆက်မပြတ် ထည့်သွင်းနေပြီး ဖယ်ရှားနေသည်၊ ဖွဲ့စည်းပုံသည် မြန်ဆန်သော လည်ပတ်နှုန်းကို သေချာစေရမည်။ အစပိုင်းမှာတော့ standard containers တွေသုံးပြီး အဲဒီအရာကို အကောင်အထည်ဖော်ဖို့ ကြိုးစားခဲ့တယ်။ စံ. ဒီလမ်းဟာ အောင်မြင်မှုသရဖူမဆောင်းဘဲ တစ်ခုခုကို အကောင်အထည်ဖော်ဖို့ ငါကိုယ်တိုင်လိုအပ်တဲ့ နားလည်မှုရောက်လာတယ်။ စိတ်ထဲတွင် တစ်ခုတည်းသောအရာမှာ binary ရှာဖွေရေးသစ်ပင်ကို အသုံးပြုရန်ဖြစ်သည်။ အဘယ်ကြောင့်ဆိုသော် ၎င်းသည် အမျိုးအစားခွဲထားသည့်ပုံစံဖြင့် ဒေတာများကို အမြန်ထည့်သွင်းခြင်း၊ ဖျက်ခြင်းနှင့် သိမ်းဆည်းခြင်း၏ လိုအပ်ချက်နှင့် ကိုက်ညီသောကြောင့်ဖြစ်သည်။ ကျန်တာအားလုံးက ဒြပ်စင်အားလုံးကို အညွှန်းကိန်းဘယ်လိုရှာရမလဲဆိုတာနဲ့ သစ်ပင်ပြောင်းတဲ့အခါ အညွှန်းကိန်းတွေကို ပြန်လည်တွက်ချက်ဖို့ပါပဲ။

struct node_s {    
    data_t data;

    uint64_t weight; // вес узла

    node_t *left;
    node_t *right;

    node_t *parent;
};

ဆောင်းပါးတွင် ကုဒ်ထက် ရုပ်ပုံများနှင့် သီအိုရီ ပိုများပါမည်။ ကုဒ်ကို အောက်ပါ link တွင် ကြည့်ရှုနိုင်ပါသည်။

အလေးချိန်

ယင်းကိုအောင်မြင်ရန်၊ သစ်ပင်သည် အနည်းငယ်ပြုပြင်မွမ်းမံမှုပြုလုပ်ခဲ့ပြီး၊ အပိုဆောင်းအချက်အလက်များကို ထည့်သွင်းခဲ့သည်။ ကိုယ်အလေးချိန် node ။ node weight က ဤ node ၏သားစဉ်မြေးဆက်အရေအတွက် + 1 (ဒြပ်စင်တစ်ခု၏အလေးချိန်)။

node အလေးချိန်ကို ရယူရန် လုပ်ဆောင်ချက်

uint64_t bntree::get_child_weight(node_t *node) {
    if (node) {
        return node->weight;
    }

    return 0;
}

စာရွက်၏ အလေးချိန်သည် တူညီသည်။ 0.

ထို့နောက်၊ ထိုကဲ့သို့သော သစ်ပင်၏ သာဓကတစ်ခု၏ အမြင်အာရုံကို ကိုယ်စားပြုခြင်းသို့ ဆက်သွားကြပါစို့။ အနက်ရောင် node သော့ကို အရောင်ဖြင့် ပြပါမည် (တန်ဖိုးကို ပြမည်မဟုတ်ပါ၊ ၎င်းသည် မလိုအပ်သောကြောင့်)၊ နီသော - ထုံးအလေးချိန်၊ စိမ်းလန်းသော - node အညွှန်း

ကျွန်ုပ်တို့၏အပင်သည် ဗလာဖြစ်နေသောအခါ ၎င်း၏အလေးချိန်မှာ 0 ဖြစ်သည်။ ၎င်းတွင် အမြစ်ဒြပ်စင်တစ်ခုကို ထည့်ကြပါစို့။

သစ်ပင်၏အလေးချိန်သည် 1 ဖြစ်လာသည်၊ အမြစ်ဒြပ်စင်၏အလေးချိန်သည် 1 ဖြစ်လာသည်။ အမြစ်ဒြပ်စင်၏အလေးချိန်သည် သစ်ပင်၏အလေးချိန်ဖြစ်သည်။

နောက်ထပ်ဒြပ်စင်အနည်းငယ် ထပ်ထည့်ကြပါစို့။

ဒြပ်စင်အသစ်တစ်ခုထည့်လိုက်တိုင်း၊ ကျွန်ုပ်တို့သည် node များကိုဆင်းသွားပြီး node တစ်ခုစီ၏အလေးချိန်တန်ပြန်ကိုတိုးစေသည်။ node အသစ်တစ်ခုဖန်တီးသောအခါ၊ အလေးချိန်တစ်ခုသတ်မှတ်ပေးသည်။ 1. ထိုသို့သောသော့ပါသော node တစ်ခုရှိနှင့်ပြီးဖြစ်ပါက၊ ကျွန်ုပ်တို့သည် တန်ဖိုးကို ထပ်ရေးပြီး ကျွန်ုပ်တို့ဖြတ်သန်းပြီးသော node များအားလုံး၏ အလေးချိန်ပြောင်းလဲမှုများကို ပယ်ဖျက်ကာ root အထိ ပြန်သွားပါမည်။
အကယ်၍ node တစ်ခုကို ဖယ်ရှားနေပါက၊ ကျွန်ုပ်တို့သည် အောက်သို့ဆင်းပြီး ဖြတ်သန်းသွားသော node များ၏ အလေးချိန်များကို လျှော့ချပါ။

အညွှန်းကိန်း

အခု index node လုပ်နည်းကို ဆက်ကြည့်ရအောင်။ Node များသည် ၎င်းတို့၏ အညွှန်းကိန်းကို ပြတ်သားစွာ သိမ်းဆည်းမထားပါ၊ ၎င်းကို node များ၏ အလေးချိန်ပေါ်အခြေခံ၍ တွက်ချက်သည်။ အကယ်၍ ၎င်းတို့သည် ၎င်းတို့၏ အညွှန်းကိန်းကို သိမ်းဆည်းထားပါက ၎င်းကို လိုအပ်မည်ဖြစ်သည်။ အို (ဎ) သစ်ပင်တွင်ပြောင်းလဲမှုတစ်ခုစီပြီးနောက် node များအားလုံး၏အညွှန်းကိန်းများကိုမွမ်းမံရန်အချိန်။
အမြင်အာရုံကို ကိုယ်စားပြုခြင်းသို့ ဆက်သွားကြပါစို့။ ကျွန်ုပ်တို့၏သစ်ပင်သည် ဗလာဖြစ်နေသည်၊ ၎င်းတွင် 1st node ကိုထည့်ကြပါစို့။

ပထမ Node တွင် အညွှန်းတစ်ခုရှိသည်။ 0ပြီးတော့ အခု ၂ ယောက် ဖြစ်နိုင်တယ်။ ပထမတွင်၊ အမြစ်ဒြပ်စင်၏အညွှန်းကိန်းသည် ပြောင်းလဲမည်ဖြစ်ပြီး၊ ဒုတိယတွင် ၎င်းသည် ပြောင်းလဲမည်မဟုတ်ပါ။

အမြစ်တွင်၊ ဘယ်ဘက်အပင်၏ အလေးချိန်မှာ ၁။

ဒုတိယကိစ္စ-

၎င်း၏ဘယ်ဘက်အပင်၏အလေးချိန်သည် ၀ ကျန်နေသောကြောင့် အမြစ်၏အညွှန်းကိန်းမပြောင်းလဲပါ။

node တစ်ခု၏ အညွှန်းကိန်းကို ၎င်း၏ ဘယ်ဘက်ပင်မအခွဲ၏ အလေးချိန် + ပင်မထံမှ ပေးပို့သော နံပါတ်အဖြစ် တွက်ချက်သည်။ ဤကိန်းဂဏန်းသည် အဘယ်နည်း၊ ဤသည်မှာ အညွှန်းကိန်းကောင်တာဖြစ်ပြီး အစပိုင်းတွင် ၎င်းနှင့် ညီမျှသည်။ 0, ဘာဖြစ်လို့လဲဆိုတော့ root မှာ မိဘမရှိပါဘူး။ အဲဒီအခါကျရင် ဘယ်ဘက်ကလေးက ဘယ်ကိုဆင်းသွားမလဲဆိုတဲ့အပေါ်မှာ မူတည်တယ်။ ဘယ်ဘက်မှာဆိုရင် ကောင်တာမှာ ဘာမှထည့်မထားဘူး။ အကယ်၍ ကျွန်ုပ်တို့သည် လက်ရှိ node ၏ အညွှန်းကို ညာဘက်သို့ ပေါင်းထည့်ပါက၊

ဥပမာအားဖြင့်၊ သော့ 8 ပါသော ဒြပ်စင်တစ်ခု၏ အညွှန်းကိန်း (အမြစ်၏ ညာဘက်ကလေး) ကို မည်သို့ တွက်ချက်သနည်း။ ဤသည်မှာ "Root Index" + "သော့ 8" ပါသော ဘယ်ဘက်အခွဲ၏ အလေးချိန်" + "1" == 3 + 2 + 1 == 6
သော့ 6 ပါသော ဒြပ်စင်၏ အညွှန်းကိန်းသည် "အမြစ်ညွှန်းကိန်း" + 1 == 3 + 1 == ဖြစ်လိမ့်မည်။ 4

ထို့ကြောင့်၊ အညွှန်းအားဖြင့် ဒြပ်စင်တစ်ခုကို ရယူရန်နှင့် ဖျက်ရန် အချိန်ယူရသည်။ အို (log n)အဘယ်ကြောင့်ဆိုသော် လိုချင်သောဒြပ်စင်ကိုရရန်အတွက် ၎င်းကို ဦးစွာရှာဖွေရမည်ဖြစ်သောကြောင့် (အမြစ်မှ ဤဒြပ်စင်သို့ဆင်းသွားပါ)။

အနက်

အလေးချိန်ပေါ်မူတည်၍ သစ်ပင်၏အတိမ်အနက်ကိုလည်း တွက်ချက်နိုင်သည်။ ဟန်ချက်ညီဖို့ လိုအပ်ပါတယ်။
၎င်းကိုလုပ်ဆောင်ရန်၊ လက်ရှိ node ၏အလေးချိန်ကို ပေးထားသောအလေးချိန်ထက် ကြီးသော သို့မဟုတ် ညီမျှသည့် ပါဝါ 2 ၏ ပထမနံပါတ်သို့ ဝိုင်းထားရမည်ဖြစ်ပြီး ၎င်းမှ binary logarithm ကိုယူပါ။ ၎င်းသည် ကျွန်ုပ်တို့အား မျှတသည်ဟု ယူဆပါက သစ်ပင်၏အတိမ်အနက်ကို ပေးပါလိမ့်မည်။ ဒြပ်စင်အသစ်ထည့်သွင်းပြီးနောက် သစ်ပင်သည် ဟန်ချက်ညီသည်။ သစ်ပင်တွေကို ဟန်ချက်ညီအောင် ဘယ်လိုထိန်းရမလဲဆိုတဲ့ သီအိုရီကို ကျွန်တော် မပေးပါဘူး။ အရင်းအမြစ်ကုဒ်များသည် ဟန်ချက်ညီသောလုပ်ဆောင်ချက်ကို ပေးဆောင်သည်။

အလေးချိန်ကို အနက်သို့ပြောင်းရန် ကုဒ်။

/*
 * Возвращает первое число в степени 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));
}

ရလဒ်များကို

• ဒြပ်စင်အသစ်တစ်ခုထည့်သွင်းခြင်းတွင် ဖြစ်ပေါ်သည်။ အို (log n)
• နံပါတ်စဉ်အလိုက် အစိတ်အပိုင်းတစ်ခုအား ဖျက်ခြင်းမှာ ဖြစ်ပေါ်ပါသည်။ အို (log n)
• အမှတ်စဉ်နံပါတ်ဖြင့် ဒြပ်စင်တစ်ခုရရှိခြင်းမှာ ဖြစ်ပေါ်ပါသည်။ အို (log n)

အရှိန် အို (log n) ဒေတာအားလုံးကို အမျိုးအစားခွဲထားသည့်ပုံစံဖြင့် သိမ်းဆည်းထားသောကြောင့် ကျွန်ုပ်တို့ ပေးဆောင်ပါသည်။

ဒီလိုဖွဲ့စည်းပုံက ဘယ်နေရာမှာ အသုံးဝင်နိုင်လဲ မသိဘူး။ သစ်ပင်များ မည်သို့အလုပ်လုပ်သည်ကို နားလည်ရန် ပဟေဠိတစ်ခုသာဖြစ်သည်။ ဂရုစိုက်တဲ့အတွက်ကျေးဇူးတင်ပါတယ်။

ကိုးကား

• သစ်ပင်အရင်းအမြစ်ကုဒ်

ပရောဂျက်တွင် လုပ်ဆောင်ချက်အမြန်နှုန်းကို စစ်ဆေးရန် စမ်းသပ်ဒေတာပါရှိသည်။ သစ်ပင်က ပြည့်နေတယ်။ 1000000 ဒြပ်စင်။ ထို့အပြင် အစိတ်အပိုင်းများကို ဆက်တိုက်ဖျက်ခြင်း၊ ထည့်သွင်းခြင်းနှင့် ပြန်လည်ရယူခြင်းများလည်း ရှိပါသည်။ 1000000 တခါ။ အဲဒါပါပဲ။ 3000000 စစ်ဆင်ရေး။ ရလဒ်သည် ~ 8 စက္ကန့်အတော်လေးကောင်းသည်။

source: www.habr.com