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

मैले निम्न प्रकारको समस्या भेट्टाएँ। यो निम्न प्रकार्यता प्रदान गर्ने डाटा भण्डारण कन्टेनर लागू गर्न आवश्यक छ:

• नयाँ तत्व घुसाउनुहोस्
• क्रम संख्या द्वारा तत्व हटाउनुहोस्
• क्रमिक संख्या द्वारा तत्व प्राप्त गर्नुहोस्
• डेटा क्रमबद्ध रूपमा भण्डार गरिएको छ

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

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.

अर्को, यस्तो रूखको उदाहरणको दृश्य प्रतिनिधित्वमा जाऔं। कालो नोड कुञ्जी रंगमा देखाइनेछ (मान देखाइनेछैन, किनकि यो आवश्यक छैन), रातो - गाँठो वजन, हरियो - नोड सूचकांक।

जब हाम्रो रूख खाली हुन्छ, यसको वजन ० हुन्छ। यसमा मूल तत्व थपौं:

रूखको वजन 1 हुन्छ, जरा तत्वको वजन 1 हुन्छ। जरा तत्वको वजन रूखको वजन हो।

केही थप तत्वहरू थपौं:

प्रत्येक पटक नयाँ तत्व थपिएको छ, हामी नोडहरू तल जान्छौं र पास गरिएको प्रत्येक नोडको वजन काउन्टर बढाउँछौं। जब नयाँ नोड बनाइन्छ, त्यसमा तौल तोकिएको हुन्छ 1। यदि यस्तो कुञ्जी भएको नोड पहिले नै अवस्थित छ भने, हामी मान अधिलेखन गर्नेछौं र रूटमा फिर्ता जान्छौं, हामीले पारित गरेका सबै नोडहरूको वजनहरूमा परिवर्तनहरू रद्द गर्दै।
यदि नोड हटाइएको छ भने, हामी तल जान्छौं र पारित नोडहरूको वजन घटाउँछौं।

अनुक्रमणिका

अब नोडहरू कसरी अनुक्रमणिका गर्ने भनेर अगाडि बढौं। नोडहरू स्पष्ट रूपमा तिनीहरूको सूचकांक भण्डार गर्दैनन्, यो नोडहरूको वजनको आधारमा गणना गरिन्छ। यदि तिनीहरूले आफ्नो सूचकांक भण्डारण गरे, त्यसपछि यो आवश्यक हुनेछ ऊ) रूखमा प्रत्येक परिवर्तन पछि सबै नोडहरूको अनुक्रमणिका अद्यावधिक गर्ने समय।
दृश्य प्रतिनिधित्वमा जाऔं। हाम्रो रूख खाली छ, यसमा पहिलो नोड थपौं:

पहिलो नोड एक सूचकांक छ 0, र अब 2 केसहरू सम्भव छन्। पहिलोमा, मूल तत्वको अनुक्रमणिका परिवर्तन हुनेछ, दोस्रोमा यो परिवर्तन हुनेछैन।

जरामा, बायाँ सबट्रीको तौल १ हुन्छ।

दोस्रो मामला:

रूटको अनुक्रमणिका परिवर्तन भएन किनभने यसको बायाँ सबट्रीको वजन ० रह्यो।

नोडको अनुक्रमणिका यसको बायाँ सबट्रीको वजन + अभिभावकबाट पास गरिएको संख्याको रूपमा गणना गरिन्छ। यो संख्या के हो?, यो सूचकांक काउन्टर हो, सुरुमा यो बराबर छ 0, किनभने मूलको कुनै अभिभावक छैन। त्यसपछि यो सबै हामी बायाँ बच्चा वा दायाँ एक तल जान्छौं मा निर्भर गर्दछ। यदि बाँयामा, त्यसपछि काउन्टरमा केहि थपिएको छैन। यदि हामीले हालको नोडको अनुक्रमणिकालाई दायाँमा थप्यौं।

उदाहरणका लागि, कुञ्जी 8 (मूलको दायाँ बच्चा) भएको तत्वको अनुक्रमणिका कसरी गणना गरिन्छ। यो हो "रूट इन्डेक्स" + "कुञ्जी ८" + "१" == ३ + २ + १ == नोडको बायाँ सबट्रीको वजन 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