अनुक्रमित बायनरी वृक्ष

मला खालील प्रकारची समस्या आली. खालील कार्यक्षमता प्रदान करणारा डेटा स्टोरेज कंटेनर लागू करणे आवश्यक आहे:

• नवीन घटक घाला
• अनुक्रमांकानुसार घटक काढा
• ऑर्डिनल नंबरद्वारे घटक मिळवा
• डेटा क्रमवारीत संग्रहित केला जातो

डेटा सतत जोडला आणि काढला जात आहे, संरचनेने वेगवान ऑपरेशन गती सुनिश्चित करणे आवश्यक आहे. प्रथम मी पासून मानक कंटेनर वापरून अशी गोष्ट अंमलात आणण्याचा प्रयत्न केला स्टडी. या मार्गावर यशाचा मुकुट घातलेला नाही आणि समज आली की मला स्वत: काहीतरी अंमलात आणण्याची गरज आहे. बायनरी शोध वृक्ष वापरणे ही एकच गोष्ट मनात आली. कारण ते क्रमवारीत डेटा जलद घालण्याची, हटवण्याची आणि साठवण्याची आवश्यकता पूर्ण करते. सर्व घटकांची अनुक्रमणिका कशी करायची आणि जेव्हा झाड बदलते तेव्हा निर्देशांकांची पुनर्गणना कशी करायची हे शोधणे बाकी आहे.

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. जर अशी की असलेली नोड आधीपासून अस्तित्वात असेल, तर आम्ही मूल्य ओव्हरराईट करू आणि आम्ही पास केलेल्या सर्व नोड्सच्या वजनातील बदल रद्द करून रूट वर परत जाऊ.
जर नोड काढला जात असेल, तर आम्ही खाली जातो आणि पास केलेल्या नोड्सचे वजन कमी करतो.

निर्देशांक

आता नोड्स कसे इंडेक्स करायचे ते पाहू. नोड्स स्पष्टपणे त्यांचे निर्देशांक संचयित करत नाहीत, ते नोड्सच्या वजनावर आधारित मोजले जाते. जर त्यांनी त्यांचा निर्देशांक संग्रहित केला असेल तर ते आवश्यक असेल O (n) झाडातील प्रत्येक बदलानंतर सर्व नोड्सचे निर्देशांक अद्यतनित करण्याची वेळ.
चला व्हिज्युअल प्रतिनिधित्वाकडे जाऊया. आमचे झाड रिकामे आहे, चला त्यात पहिला नोड जोडूया:

पहिल्या नोडमध्ये एक निर्देशांक असतो 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