ترتيب ڏنل بائنري وڻ

مون کي هيٺين قسم جي مسئلي ۾ آيو. اهو ضروري آهي ته ڊيٽا اسٽوريج ڪنٽينر کي لاڳو ڪرڻ لاء جيڪو هيٺين ڪارڪردگي مهيا ڪري ٿو:

• نئون عنصر داخل ڪريو
• سيريل نمبر ذريعي عنصر کي هٽايو
• آرڊينل نمبر ذريعي عنصر حاصل ڪريو
• ڊيٽا ترتيب ڏنل شڪل ۾ محفوظ ڪئي وئي آهي

ڊيٽا مسلسل شامل ڪيو وڃي ٿو ۽ هٽايو وڃي ٿو، ساخت کي تيز رفتار آپريشن جي رفتار کي يقيني بڻائڻ گهرجي. پهرين ۾، مان معياري ڪنٽينرز استعمال ڪندي اهڙي شيء کي لاڳو ڪرڻ جي ڪوشش ڪئي اسٽينڊ. اهو رستو ڪاميابي سان تاج نه ڪيو ويو ۽ سمجهه ۾ آيو ته مون کي پاڻ تي عمل ڪرڻ جي ضرورت آهي. صرف هڪ شيء جيڪا ذهن ۾ آئي هڪ بائنري ڳولا جو وڻ استعمال ڪرڻ هو. ڇاڪاڻ ته اهو ترتيب ڏنل فارم ۾ ڊيٽا جي تيز داخل ڪرڻ، حذف ڪرڻ ۽ اسٽوريج جي گهرج کي پورو ڪري ٿو. باقي اهو آهي ته اهو معلوم ڪرڻ ته ڪيئن سڀني عنصرن کي انڊيڪس ڪجي ۽ انڊيڪس کي ٻيهر ڳڻپ ڪجي جڏهن وڻ بدلجي وڃي.

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. جيڪڏهن اهڙي ڪيئي سان ڪو نوڊ اڳ ۾ ئي موجود آهي، ته پوءِ اسان قيمت کي اوور رائٽ ڪنداسين ۽ روٽ ڏانهن واپس وڃون ٿا، سڀني نوڊس جي وزن ۾ تبديلين کي رد ڪندي جيڪي اسان گذري چڪا آهيون.
جيڪڏهن هڪ نوڊ هٽايو وڃي ٿو، پوء اسان هيٺ وڃون ٿا ۽ پاس ٿيل نوڊس جي وزن کي گھٽائي ٿو.

انڊيڪس

ھاڻي اچو ته انڊيڪس نوڊس ڏانھن وڃو. نوڊس واضح طور تي پنھنجي انڊيڪس کي محفوظ نه ڪندا آھن، اھو حساب ڪيو ويندو آھي نوڊس جي وزن جي بنياد تي. جيڪڏھن اھي پنھنجي انڊيڪس کي محفوظ ڪن، پوء اھو گھربل ھوندو اي (ن) وڻ ۾ هر تبديلي کان پوء سڀني نوڊس جي انڊيڪس کي اپڊيٽ ڪرڻ جو وقت.
اچو ته هڪ بصري نمائندگي ڏانهن وڃو. اسان جو وڻ خالي آهي، اچو ته ان ۾ پهريون نوڊ شامل ڪريون:

پهرين نوڊ هڪ انڊيڪس آهي 0، ۽ هاڻي 2 ڪيس ممڪن آهن. پهرين ۾، روٽ عنصر جي انڊيڪس تبديل ٿي ويندي، ٻئي ۾ اهو تبديل نه ٿيندو.

روٽ ۾، کاٻي ذيلي وڻ جو وزن 1 آهي.

ٻيو ڪيس:

روٽ جو انڊيڪس تبديل نه ٿيو ڇاڪاڻ ته ان جي کاٻي ذيلي وڻ جو وزن 0 رهيو.

نوڊ جي انڊيڪس ان جي کاٻي ذيلي وڻ جي وزن جي حساب سان ڳڻيو ويندو آهي + والدين کان منظور ٿيل نمبر. هي نمبر ڇا آهي؟، هي انڊيڪس ڪائونٽر آهي، شروعات ۾ ان جي برابر آهي 0، ڇاڪاڻ ته روٽ جو ڪوبه والدين ناهي. پوءِ اهو سڀ ان تي منحصر آهي جتي اسان هيٺ وڃون ٿا کاٻي ٻار يا ساڄي هڪ. جيڪڏهن کاٻي پاسي، پوء ڪائونٽر ۾ ڪجھ به شامل نه ڪيو ويو آهي. جيڪڏهن اسان موجوده نوڊ جي انڊيڪس کي ساڄي طرف شامل ڪيو.

مثال طور، ڪيئن هڪ عنصر جي انڊيڪس ڪيئي 8 سان (روٽ جو ساڄي ٻار) حساب ڪيو ويندو آهي. هي آهي "روٽ انڊيڪس" + "ڪٻي 8 سان نوڊ جي کاٻي ذيلي وڻ جو وزن" + "1" == 3 + 2 + 1 == 6
عنصر جو انڊيڪس ڪي 6 سان ٿيندو "روٽ انڊيڪس" + 1 == 3 + 1 == 4

ان جي مطابق، انڊيڪس ذريعي هڪ عنصر حاصل ڪرڻ ۽ ختم ڪرڻ لاء وقت وٺندو آهي اي (لاگ اين)، ڇاڪاڻ ته مطلوب عنصر حاصل ڪرڻ لاءِ اسان کي پهريان ان کي ڳولڻ گهرجي (روٽ کان هيٺ وڃو هن عنصر ڏانهن).

گدائي

وزن جي بنياد تي، توهان پڻ حساب ڪري سگهو ٿا وڻ جي کوٽائي. توازن لاء ضروري آهي.
هن کي ڪرڻ لاء، موجوده نوڊ جو وزن 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));
}

نتيجو

• نئين عنصر جي داخل ٿيڻ ۾ ٿيندي آهي اي (لاگ اين)
• سيريل نمبر ذريعي هڪ عنصر کي ختم ڪرڻ ۾ ٿيندي آهي اي (لاگ اين)
• سيريل نمبر ذريعي هڪ عنصر حاصل ڪرڻ ۾ ٿئي ٿي اي (لاگ اين)

رفتار اي (لاگ اين) اسان ان حقيقت لاءِ ادا ڪيون ٿا ته سڀئي ڊيٽا ترتيب ڏنل شڪل ۾ محفوظ ٿيل آهن.

مون کي خبر ناهي ته اهڙي جوڙجڪ ڪٿي مفيد ٿي سگهي ٿي. صرف هڪ پہیلی هڪ ڀيرو ٻيهر سمجهڻ لاءِ ته وڻ ڪيئن ڪم ڪن ٿا. توهان جي توجه لاء مهرباني.

حوالن

• وڻ جو ذريعو ڪوڊ

پروجيڪٽ آپريشن جي رفتار کي جانچڻ لاءِ ٽيسٽ ڊيٽا تي مشتمل آهي. وڻ ڀرجي پيو آهي 1000000 عناصر. ۽ اتي هڪ ترتيب وار ختم ڪرڻ، داخل ڪرڻ ۽ عناصر جي ٻيهر حاصل ڪرڻ آهي 1000000 هڪ دفعو. اهو آهي 3000000 آپريشن نتيجو نڪتو تمام سٺو ~ 8 سيڪنڊ.

جو ذريعو: www.habr.com