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

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

• एक नवीन घटक घाला
• क्रमिक संख्येनुसार घटक हटवा
• क्रमिक संख्येने घटक मिळवा.
• डेटा क्रमवारीत साठवला जातो.

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

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

निर्देशांक

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

पहिल्या नोडमध्ये एक निर्देशांक असतो 0, आणि आता दोन संभाव्य प्रकरणे आहेत. पहिल्यामध्ये, मूळ घटकाचा निर्देशांक बदलेल, दुसऱ्यामध्ये, तो बदलणार नाही.

मुळाशी, डाव्या उपवृक्षाचे वजन १ आहे.

दुसरे प्रकरण:

डाव्या उपवृक्षाचे वजन ० राहिल्याने मूळ निर्देशांक बदललेला नाही.

नोडचा इंडेक्स कसा मोजला जातो? तो त्याच्या डाव्या सबट्रीचे वजन आणि त्याच्या मूळ क्रमांकावरून पाठवलेली संख्या आहे. हा आकडा काय आहे? हा एक इंडेक्स काउंटर आहे आणि सुरुवातीला तो 0, कारण रूटला पालक नाही. तिथून, आपण डाव्या चाइल्डवर उतरत आहोत की उजवीकडे यावर सर्व काही अवलंबून असते. जर आपण डाव्या चाइल्डवर उतरत आहोत, तर काउंटरमध्ये काहीही जोडले जात नाही. जर आपण उजव्या चाइल्डवर उतरत आहोत, तर आपण वर्तमान नोडचा निर्देशांक जोडतो.

उदाहरणार्थ, की ८ (रूटचा उजवा उपवर्ग) असलेल्या घटकाचा निर्देशांक कसा मोजला जातो? हा "रूट अनुक्रमणिका" + "की ८ असलेल्या नोडच्या डाव्या उपवृक्षाचे वजन" + "१" == ३ + २ + १ == आहे. 6
की ६ असलेल्या घटकाचा निर्देशांक "रूट इंडेक्स" + १ == ३ + १ == असेल. 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 ऑपरेशन्स. निकाल खूप चांगला होता: ~८ सेकंद.

स्त्रोत: www.habr.com