अनुक्रमित बाइनरी ट्री

मुझे निम्न प्रकार की समस्या का सामना करना पड़ा। एक डेटा भंडारण कंटेनर को कार्यान्वित करना आवश्यक है जो निम्नलिखित कार्यक्षमता प्रदान करता है:

• नया तत्व डालें
• क्रम संख्या द्वारा तत्व हटाएँ
• क्रमिक संख्या द्वारा तत्व प्राप्त करें
• डेटा को क्रमबद्ध रूप में संग्रहीत किया जाता है

डेटा लगातार जोड़ा और हटाया जा रहा है, संरचना को तेज़ संचालन गति सुनिश्चित करनी चाहिए। सबसे पहले मैंने मानक कंटेनरों का उपयोग करके ऐसी चीज़ को लागू करने का प्रयास किया एसटीडी. इस पथ को सफलता नहीं मिली और यह समझ आई कि मुझे स्वयं कुछ लागू करने की आवश्यकता है। एकमात्र बात जो दिमाग में आई वह थी बाइनरी सर्च ट्री का उपयोग करना। क्योंकि यह क्रमबद्ध रूप में डेटा के तेजी से सम्मिलन, विलोपन और भंडारण की आवश्यकता को पूरा करता है। जो कुछ बचा है वह यह पता लगाना है कि सभी तत्वों को कैसे अनुक्रमित किया जाए और पेड़ बदलने पर सूचकांकों की पुनर्गणना कैसे की जाए।

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 (लॉग एन), क्योंकि वांछित तत्व प्राप्त करने के लिए हमें पहले उसे खोजना होगा (मूल से इस तत्व तक नीचे जाएं)।

गहराई

वजन के आधार पर आप पेड़ की गहराई की गणना भी कर सकते हैं। संतुलन के लिए आवश्यक.
ऐसा करने के लिए, वर्तमान नोड के वजन को पहले नंबर पर 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 (लॉग एन)
• क्रम संख्या द्वारा किसी तत्व को हटाना घटित होता है O (लॉग एन)
• क्रम संख्या द्वारा एक तत्व प्राप्त करना होता है O (लॉग एन)

रफ़्तार O (लॉग एन) हम इस तथ्य के लिए भुगतान करते हैं कि सारा डेटा क्रमबद्ध रूप में संग्रहीत है।

मैं नहीं जानता कि ऐसी संरचना कहाँ उपयोगी हो सकती है। एक बार फिर यह समझना एक पहेली है कि पेड़ कैसे काम करते हैं। आपके ध्यान देने के लिए धन्यवाद!

संदर्भों

• वृक्ष स्रोत कोड

परियोजना में संचालन की गति की जांच करने के लिए परीक्षण डेटा शामिल है। पेड़ भर रहा है 1000000 तत्व. और तत्वों का क्रमिक विलोपन, सम्मिलन और पुनर्प्राप्ति होती है 1000000 एक बार। वह है 3000000 परिचालन. नतीजा ~8 सेकंड में काफी अच्छा निकला।

स्रोत: www.habr.com