شاخص شوی بائنری ونه

زه د لاندې ډول ستونزې سره مخ شوم. دا اړینه ده چې د معلوماتو ذخیره کولو کانټینر پلي کړئ چې لاندې فعالیت چمتو کوي:

• نوی عنصر داخل کړئ
• د سیریل نمبر په واسطه عنصر لرې کړئ
• عنصر د منظم شمیرې په واسطه ترلاسه کړئ
• معلومات په ترتیب شوي شکل کې ساتل کیږي

ډاټا په دوامداره توګه اضافه کیږي او لیرې کیږي، جوړښت باید د چټک عملیات سرعت ډاډمن کړي. په لومړي سر کې ما هڅه وکړه چې د معیاري کانټینرونو په کارولو سره داسې شی پلي کړم سټډ. دا لاره د بریا سره تاج نه وه او پوهه راغله چې زه پخپله یو څه پلي کولو ته اړتیا لرم. یوازینی شی چې ذهن ته راغلی و د بائنری لټون ونې کارول و. ځکه چې دا په ترتیب شوي شکل کې د معلوماتو د ګړندي ننوتلو ، حذف کولو او ذخیره کولو اړتیا پوره کوي. ټول هغه څه چې پاتې دي د دې معلومول دي چې څنګه ټول عناصر شاخص کړئ او شاخصونه بیا محاسبه کړئ کله چې ونه بدلیږي.

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) په ونه کې د هر بدلون وروسته د ټولو نوډونو شاخصونو تازه کولو وخت.
راځئ چې یو بصری استازیتوب ته لاړ شو. زموږ ونه خالي ده، راځئ چې لومړی نوډ پکې اضافه کړو:

لومړی نوډ یو شاخص لري 0، او اوس 2 قضیې ممکن دي. په لومړي کې، د ریښې عنصر شاخص به بدل شي، په دویم کې به بدلون ونلري.

په ریښه کې، کیڼ فرعي ونه 1 وزن لري.

دویمه قضیه:

د ریښې شاخص بدل نه شو ځکه چې د هغې د کیڼ فرعي ونې وزن 0 پاتې شو.

د نوډ شاخص د هغې د کیڼ فرعي ونې وزن + هغه شمیره محاسبه کیږي چې د مور او پلار څخه تیریږي. دا شمیره څه ده؟، دا د شاخص کاونټر دی، په پیل کې دا مساوي دی 0ځکه ريښه مور او پلار نه لري. بیا دا ټول پدې پورې اړه لري چې چیرې موږ کیڼ ماشوم یا ښي لور ته ځو. که کیڼ اړخ ته، بیا په کاونټر کې هیڅ شی نه اضافه کیږي. که موږ د اوسني نوډ شاخص ښي ته اضافه کړو.

د مثال په توګه، د کیلي 8 سره د عنصر شاخص څنګه محاسبه کیږي (د ریښې ښی ماشوم). دا د "روټ انډیکس" + "د نوډ د کیڼ فرعي ونې وزن 8" + "1" == 3 + 2 + 1 == 6
د کیلي 6 سره د عنصر شاخص به د "روټ شاخص" + 1 == 3 + 1 == وي 4

په دې اساس، دا د شاخص په واسطه د عنصر ترلاسه کولو او حذف کولو وخت نیسي O (log 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 (log n)
• د سیریل نمبر په واسطه د عنصر حذف کول واقع کیږي O (log n)
• د سیریل نمبر په واسطه د عنصر ترلاسه کول واقع کیږي O (log n)

سرعت O (log n) موږ د دې حقیقت لپاره تادیه کوو چې ټول معلومات په ترتیب شوي شکل کې زیرمه شوي.

زه نه پوهیږم چې دا ډول جوړښت به چیرې ګټور وي. یوازې یو معما یوځل بیا پوهیدل چې ونې څنګه کار کوي. له پاملرنې څخه مو مننه.

مرجع

• د ونې سرچینې کوډ

پروژه د ازموینې ډیټا لري ترڅو د عملیاتو سرعت وګوري. ونه ډکیږي 1000000 عناصر او د عناصرو په ترتیب سره له مینځه وړل ، داخلول او ترلاسه کول شتون لري 1000000 یوځل. هغه دی 3000000 عملیات پایله خورا ښه وه ~ 8 ثانیې.

سرچینه: www.habr.com