16
के साथ एक बाइनरी पेड़ में पॉइंटर्स की गणना कैसे करें मैं निहित पॉइंटर्स का उपयोग करके वैन एम्डे बोस लेआउट का उपयोग करके एक सरणी में संग्रहीत कैश-अनजान बाइनरी पेड़ को कार्यान्वित करना चाहता हूं। पेड़ में सभी आइटम 32-बिट पूर्णांक हैं और पेड़ काफी बड़ा हो जाएगा, इसलिए पॉइंटर्स को संग्रहीत करना कम से कम 3x अधिक डेटा होगा।वैन एम्डे बोस लेआउट
समस्या यह है कि मैं नोड इंडेक्स को देखते हुए बाएं और दाएं बच्चों को पॉइंटर्स की गणना करने के लिए किसी गैर-पुनरावृत्ति के तरीके के बारे में नहीं सोच सकता (मैं पेड़ को घुमाने के दौरान किसी भी जानकारी को ट्रैक कर सकता हूं)। कई कागजात/व्याख्यान अंतर्निहित पॉइंटर्स वाले पेड़ों को संदर्भित करते हैं, लेकिन मैंने पॉइंटर्स की गणना करने के लिए एल्गोरिदम नहीं देखा है। क्या ऐसा करने का कोई प्रभावी तरीका है?
क्या आपको इसे एक अनुक्रमणिका से गणना करने की आवश्यकता है? ऐसा लगता है कि आपको वर्तमान नोड से किसी विशेष बच्चे नोड की गणना करने की आवश्यकता है। यदि आप वर्तमान स्तर से अवगत होने के इच्छुक हैं, तो वर्तमान नोड के पथ पर ऑफ़सेट का ढेर रखें, और विभिन्न स्तरों पर सभी ऑफसेट्स की एक सरणी रखें, आपको इसे करने में सक्षम होना चाहिए। मुझे नहीं पता कि उन ढेरों को कितना ओवरहेड जोड़ना होगा, यह सार्थक नहीं हो सकता है। – btilly
आप सही हैं, मुझे इसे मनमाने ढंग से इंडेक्स से गणना करने की आवश्यकता नहीं है। मुझे यकीन नहीं है कि मैं सभी ऑफसेट्स के लिए एक सरणी के साथ विचार समझता हूं? क्या आप एक विशिष्ट स्तर पर सभी वस्तुओं के लिए ऑफसेट का मतलब है? –
क्या आपने [इस पेपर] को चेक किया है (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.76.762&rep=rep1&type=pdf) बाहर? वे खंड 2.1 में वैन एम्डे बोस लेआउट का उपयोग करके पेड़ को कैसे रखना है। – jswolf19