मैं आकार N के अनियमित तत्वों की किसी दिए गए सूची से बी + पेड़ बनाना चाहता हूं।किसी दिए गए सूची से बी + पेड़ को कुशलतापूर्वक कैसे बनाया जाए?
मुझे पता है कि यह करने के लिए इष्टतम बाध्य है Θ(N/B * logM/B(N/B)) ब्लॉक ट्रांसफर, जो सॉर्टिंग के लिए भी इष्टतम है; तो मैं बस एक आइटम नहीं चुन सकता और व्यक्तिगत रूप से पेड़ में एक सम्मिलित कर सकता हूं, क्योंकि यह मुझे O(N logB(N)) ब्लॉक स्थानान्तरण देगा।
तो मुझे लगा कि पेड़ बनाने का सबसे अच्छा तरीका तत्वों को पहले क्रमबद्ध करना है, क्योंकि पत्तियों को वैसे भी आदेश दिया जाता है। उस से, मैं एक नुकसान में हूँ।
मैं कुछ इस तरह के बारे में सोचा:
- सूची
- उन्हें लिखें वे कहीं हैं के रूप में से ले बी तत्वों
- ब्लॉक के अंतिम तत्व ले लो (यह तीन में से एक पत्ता है) (सबसे बड़ा); यह
- अगले तत्वों के लिए दोहराएँ चरण 1, जब तक वहाँ माता-पिता में बी -1 रूटिंग कुंजियों हैं
- माता-पिता में
B-1रूटिंग कुंजियों देखते हैं जब, इसका मतलब यह है पत्ती की मूल के लिए एक मार्ग कुंजी हो जाएगा पूर्ण। इसलिए नए रूटिंग कुंजी "दादा" के बजाय (ताकि पेड़ एक स्तर बढ़ता है) जाना होगा, और सभी नए पत्ते एक नए अभिभावक - इस तरह जारी रखें जब तक
N/Bब्लॉक
मूल रूप से पढ़ा जाता है होगा , इसके साथ समस्या यह है कि मैं उन बच्चों की न्यूनतम संख्या पर विचार नहीं कर रहा हूं जो आंतरिक नोड के पास हो सकते हैं। तो यह उदाहरण के लिए हो सकता है कि एक नोड केवल एक बच्चे के साथ समाप्त होता है, जो स्पष्ट रूप से गलत है।
मैंने हर जगह देखा लेकिन मुझे एल्गोरिदम नहीं मिला कि वास्तव में बताता है कि Θ(N/B * logM/B(N/B)) में पेड़ कैसे बनाया जाए। मुझे लगता है कि बी कारक का शोषण किए बिना सूची में प्रत्येक आइटम के लिए पेड़ में सरल सम्मिलन वाले एल्गोरिदम हैं।
क्या आप मेरी मदद कर सकते हैं, शायद मुझे सही दिशा में इंगित करें?
चरण 5 के संबंध में, "नई रूटिंग कुंजी दादाजी के बजाय जाएगी", यह दादाजी में नहीं बल्कि पुरानी पिता की मध्य कुंजी में नई कुंजी नहीं है। नई कुंजी नए पिता – mangusta
में जाती है आप सही हैं, मेरी गलती! यदि मैं बी-1 तत्वों तक पहुंचने पर आंतरिक नोड्स को विभाजित करता हूं तो मैं गारंटी दे सकता हूं कि पेड़ प्रति नोड की न्यूनतम संख्या के बच्चों का सम्मान करता है। धन्यवाद! – Beriol