एन-नोड बाइनरी सर्च पेड़ की ऊंचाई पर एक एसिम्प्टोटिक ऊपरी बाउंड दें जिसमें नोड की औसत गहराई Θ (एलजी एन)

Question

हाल ही में, मैं सीएलआरएस में सभी अभ्यासों को हल करने की कोशिश कर रहा हूं। लेकिन उनमें से कुछ हैं जिन्हें मैं समझ नहीं सकता।

n नोड्स ऐसी है कि पेड़ में एक नोड की औसत गहराई Θ है (एलजी एन) लेकिन पेड़ की ऊंचाई पर एक द्विआधारी खोज वृक्ष का वर्णन: यहाँ CLRS व्यायाम 12.4-2 से उनमें से एक है, ω (एलजी एन) है। एन-नोड बाइनरी सर्च पेड़ की ऊंचाई पर एक एसिम्प्टोटिक ऊपरी बाउंड दें जिसमें नोड की औसत गहराई Θ (एलजी एन) है।

क्या कोई इस समस्या को हल करने के लिए कुछ विचार या संदर्भ साझा कर सकता है? धन्यवाद।

Answer 1

तो मान लीजिए कि हम इस तरह पेड़ का निर्माण करते हैं: दिए गए एन नोड्स, एफ (एन) नोड्स लें और उन्हें एक तरफ सेट करें। फिर एक परिपूर्ण बाइनरी पेड़ का निर्माण करके एक पेड़ बनाएं जहां रूट में बाएं उपट्री है जो एन-एफ (एन) - 1 नोड्स का एक सही बाइनरी पेड़ है और एक दाएं उपट्री है जो लंबाई एफ (एन) की श्रृंखला है। हम बाद में एफ (एन) उठाएंगे।

तो पेड़ में औसत गहराई क्या है? चूंकि हम सिर्फ एक एसिम्प्टोटिक बाध्य चाहते हैं, चलिए एन को चुनते हैं कि एन - एफ (एन) - 1 दो की एक पूर्ण शक्ति से कम है, कहें, 2^के - 1. उस स्थिति में, इस में ऊंचाइयों का योग पेड़ का हिस्सा 1 * 2 + 2 * 3 + 4 * 4 + 8 * 5 + ... + 2^(के -1) * के, जो (आईआईआरसी) के 2^के बारे में है, जो बस के बारे में है (एन - एफ (एन)) लॉग (एन - एफ (एन)) के हमारी पसंद से। पेड़ के दूसरे भाग में, कुल गहराई एफ (एन)^2 के बारे में है। इसका मतलब है कि औसत पथ की लंबाई लगभग ((एन - एफ (एन)) लॉग (एन - एफ (एन)) + एफ (एन)^2)/एन है। इसके अलावा, पेड़ की ऊंचाई एफ (एन) है। तो हम औसत गहराई ओ (लॉग एन) रखते हुए एफ (एन) को अधिकतम करना चाहते हैं। और गायब हो जाता है च (एन) = Θ (एन), या अंश में लॉग अवधि ऊंचाई नहीं है -

ऐसा करने के लिए, हम च (एन) को खोजने के लिए ऐसी है कि

1. n जरूरत लॉगरिदमिक,
2. एफ (एन)^2/एन = ओ (लॉग एन), या न्यूमेरर में दूसरा शब्द बहुत बड़ा हो जाता है।

यदि आप f (n) = Θ (sqrt (n log n)) चुनते हैं, तो मुझे लगता है कि 1 और 2 अधिकतम संतुष्ट हैं। तो मैं दांव दूंगा (हालांकि मैं इसके बारे में पूरी तरह गलत हो सकता हूं) कि यह उतना अच्छा है जितना आप प्राप्त कर सकते हैं। आपको ऊंचाई का पेड़ Θ (वर्ग (एन लॉग एन)) मिलता है जिसमें औसत गहराई Θ (लॉग एन) है।

आशा है कि इससे मदद मिलती है! अगर मेरा गणित बंद हो गया है, तो कृपया मुझे बताएं। देर हो चुकी है और मैंने अपनी सामान्य डबल-चेकिंग नहीं की है। :-)

Answer 2

पहले पेड़ की ऊंचाई को अधिकतम करें। (एक पेड़ है जहां प्रत्येक नोड में केवल एक बच्चा नोड होता है, इसलिए आपके पास एक लंबी श्रृंखला नीचे जा रही है)।

औसत गहराई की जांच करें। (जाहिर है औसत गहराई बहुत अधिक होगी)।

जबकि औसत गहराई बहुत अधिक है, तो आपको पेड़ की ऊंचाई को एक से कम करना होगा। पेड़ की ऊंचाई को कम करने के कई तरीके हैं। जिस तरह से औसत ऊंचाई कम करता है चुनें। (प्रेरण से साबित करें कि प्रत्येक बार आपको उस औसत का चयन करना चाहिए जो औसत ऊंचाई को कम करता है)। जब तक आप औसत ऊंचाई की आवश्यकता के तहत गिरते हैं तब तक जारी रखें। (उदाहरण के लिए ऊंचाई और औसत गहराई के लिए एक सूत्र का उपयोग करके गणना करें)।

Answer 3

आप जबकि औसत पेड़ के सभी नोड्स की गहराई को कम करने के लिए एक पेड़ की ऊंचाई अधिकतम करने के लिए कोशिश कर रहे हैं, स्पष्ट सबसे अच्छा आकार एक "अम्ब्रेला" आकार होगा, उदा के नोड्स और ऊंचाई = एलजी के साथ एक पूर्ण बाइनरी पेड़, जहां 0 < के < एन, एक ही पथ, या "पूंछ" के साथ, पूर्ण भाग की पत्तियों में से एक में से बाहर निकलने वाले एन-के नोड्स के साथ। इस पेड़ की ऊंचाई मोटे तौर पर एलजी के + एन - के है।

अब सभी नोड्स की कुल गहराई की गणना करते हैं। पूर्ण भाग के नोड्स की गहराई का योग योग [जे * 2^जे] है, जहां योग j = 0 से j = lg k तक लिया जाता है। कुछ बीजगणित से, परिणाम की प्रमुख अवधि 2k एलजी के है।

इसके बाद, पूंछ भाग की गहराई का योग योग द्वारा दिया जाता है मैं = एन-कश्मीर के लिए है, जहां योग मैं से लिया जाता है = 0 [मैं एलजी K +]। कुछ बीजगणित से, परिणाम लगभग (एन-के) एलजी के + (1/2) (एन-के)^2 है।

इसलिए, दोनों भागों को एक साथ ऊपर और विभाजित करके, सभी नोड्स की औसत गहराई (1 + के/एन) एलजी के + (एन-के)^2/(2 एन) है। ध्यान दें कि 0 < के < एन, यहां पहला शब्द ओ (एलजी एन) कोई फर्क नहीं पड़ता कि हम क्या चुनते हैं। इसलिए, हमें केवल यह सुनिश्चित करना होगा कि दूसरा शब्द ओ (एलजी एन) है। ऐसा करने के लिए, हमें इसकी आवश्यकता है (एन-के)^2 = ओ (एन एलजी एन), या के = एन - ओ (वर्ग (एन एलजी एन))। इस विकल्प के साथ, पेड़ की ऊंचाई है

एलजी k + n - k = ओ (sqrt (एन एलजी एन))

इस साधारण ओ (एलजी एन) की तुलना में asymptotically बड़ा है, और asymptotically है सबसे ऊंची आप जबकि ओ (एलजी एन)

साथ