बाइनरी पेड़ में ओ (1) में मध्यस्थ खोजें

Question

मान लीजिए कि मेरे पास संतुलित बीएसटी (बाइनरी सर्च पेड़) है। प्रत्येक पेड़ नोड में एक विशेष क्षेत्र count होता है, जो उस नोड + नोड के सभी वंशजों की गणना करता है। वे इस डेटा संरचना order statistics binary tree कहते हैं।

इस डेटा संरचना (logn) हे के दो आपरेशन का समर्थन करता है:

• rank(x) - कि कम से कम x
• findByRank(k) हैं तत्वों की संख्या - rank == साथ नोड खोजने के k

अब मैं औसत खोजने के लिए एक नया ऑपरेशन median() जोड़ना चाहता हूं। क्या मैं मान सकता हूं कि यह ऑपरेशन ओ (1) है यदि पेड़ संतुलित है?

Answer 1

यदि पेड़ पूरा हो गया है (यानी सभी स्तर पूरी तरह से भरे हुए हैं), हाँ आप कर सकते हैं।

Answer 2

जब तक पेड़ पूरा नहीं हो जाता है, तो औसत एक पत्ता नोड हो सकता है। तो सामान्य स्थिति में लागत ओ (लॉगएन) होगी। मुझे लगता है कि अनुरोधित गुणों के साथ एक डेटा संरचना है और ओ (1) findMedian ऑपरेशन (शायद एक स्किप सूची + मध्य नोड के लिए एक सूचक; मुझे यकीन है कि खोजने के बारे में निश्चित नहीं है हालांकि रैंक और रैंक ऑपरेशन) लेकिन एक संतुलित बीएसटी नहीं है उनमें से एक।

Answer 3

एक संतुलित क्रम आंकड़े के पेड़ में, औसत ढूंढना ओ (लॉग एन) है। यदि ओ (1) समय में औसत खोजना महत्वपूर्ण है, तो आप मध्यस्थ को पॉइंटर बनाए रखकर डेटा संरचना को बढ़ा सकते हैं। पकड़, ज़ाहिर है कि आपको प्रत्येक सूचक या हटाए गए ऑपरेशन के दौरान इस सूचक को अद्यतन करने की आवश्यकता होगी। सूचक को अद्यतन करने से ओ (लॉग एन) समय लगेगा, लेकिन चूंकि उन परिचालनों में पहले से ही ओ (लॉग एन) समय लगता है, मध्य सूचक को अद्यतन करने का अतिरिक्त कार्य उनकी बड़ी लागत को नहीं बदलता है।

एक व्यावहारिक मामले के रूप में, यह केवल तभी समझ में आता है जब आप सम्मिलन/हटाना की संख्या की तुलना में बहुत से "मध्यस्थ" ऑपरेशन करते हैं।

यदि वांछित है, तो आप (doubly) threaded binary tree का उपयोग कर मध्यस्थ सूचक को अद्यतन/हटाएं ओ (1) के दौरान अद्यतन करने की लागत को कम कर सकते हैं, लेकिन सम्मिलित/हटाएं अभी भी ओ (लॉग एन) होगा।