इंडेक्सेबल बाइनरी ट्री

मुझे निम्नलिखित समस्या हुई। डेटा स्टोरेज कंटेनर को लागू करना आवश्यक है जो निम्नलिखित कार्यक्षमता प्रदान करता है:

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

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

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 पर सेट होता है। यदि इस तरह की कुंजी के साथ एक नोड पहले से मौजूद है, तो मान को फिर से लिखें और सभी नोड्स के वजन में बदलाव को रद्द करते हुए, रूट पर वापस जाएं।
यदि नोड हटाया जा रहा है, तो हम नीचे जाते हैं और पारित नोड्स के वजन को घटाते हैं।

सूचकांक

अब नोड्स को इंडेक्स करने के तरीके पर आगे बढ़ते हैं। नोड्स स्पष्ट रूप से अपने सूचकांक को संग्रहीत नहीं करते हैं, यह नोड्स के वजन के आधार पर गणना की जाती है। यदि वे अपने सूचकांक को संग्रहीत करते हैं, तो पेड़ के प्रत्येक परिवर्तन के बाद ओ (एन) समय सभी नोड्स के सूचकांक को अपडेट करने की आवश्यकता होगी।
आइए एक दृश्य प्रतिनिधित्व पर चलते हैं। हमारा पेड़ खाली है, उसमें 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 (लॉग एन) की गति के साथ हम इस तथ्य के लिए भुगतान करते हैं कि सभी डेटा सॉर्ट किए गए रूप में संग्रहीत हैं।

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

संदर्भ

• ट्री स्रोत कोड

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