انڈیکسڈ بائنری درخت

مجھے مندرجہ ذیل قسم کی پریشانی کا سامنا کرنا پڑا۔ ڈیٹا اسٹوریج کنٹینر کو لاگو کرنا ضروری ہے جو درج ذیل فعالیت فراہم کرتا ہے:

• نیا عنصر داخل کریں
• سیریل نمبر کے ذریعہ عنصر کو ہٹا دیں۔
• آرڈینل نمبر کے ذریعہ عنصر حاصل کریں۔
• ڈیٹا کو ترتیب شدہ شکل میں محفوظ کیا جاتا ہے۔

ڈیٹا کو مسلسل شامل اور ہٹایا جا رہا ہے، ساخت کو تیز رفتار آپریشن کی رفتار کو یقینی بنانا چاہیے۔ پہلے میں نے معیاری کنٹینرز کا استعمال کرتے ہوئے ایسی چیز کو نافذ کرنے کی کوشش کی۔ 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. اگر ایسی کلید والا نوڈ پہلے سے موجود ہے، تو ہم قدر کو اوور رائٹ کر دیں گے اور روٹ تک واپس جائیں گے، تمام نوڈس کے وزن میں ہونے والی تبدیلیوں کو منسوخ کر دیں گے جو ہم پاس کر چکے ہیں۔
اگر ایک نوڈ کو ہٹایا جا رہا ہے، تو ہم نیچے جاتے ہیں اور پاس شدہ نوڈس کے وزن کو کم کرتے ہیں۔

سوچکانک

اب آئیے اس طرف چلتے ہیں کہ نوڈس کو کیسے انڈیکس کیا جائے۔ نوڈس واضح طور پر اپنے انڈیکس کو محفوظ نہیں کرتے ہیں، اس کا حساب نوڈس کے وزن کی بنیاد پر کیا جاتا ہے۔ اگر انہوں نے اپنا انڈیکس ذخیرہ کیا تو اس کی ضرورت ہوگی۔ اے (ن) درخت میں ہر تبدیلی کے بعد تمام نوڈس کے اشاریہ جات کو اپ ڈیٹ کرنے کا وقت۔
آئیے ایک بصری نمائندگی کی طرف چلتے ہیں۔ ہمارا درخت خالی ہے، آئیے اس میں پہلا نوڈ شامل کریں:

پہلے نوڈ میں انڈیکس ہوتا ہے۔ 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