ओ (एन) समय में एक बीएसटी में एक ढेर को परिवर्तित करना?

Question

मुझे लगता है कि मुझे जवाब पता है और न्यूनतम जटिलता ओ (nlogn) है।

लेकिन क्या कोई तरीका है कि मैं ओ (एन) जटिलता में एक ढेर से बाइनरी खोज पेड़ बना सकता हूं?

Answer 1

ओ (एन) समय में एक ढेर से बीएसटी बनाने के लिए कोई एल्गोरिदम नहीं है। इसका कारण यह है कि एन तत्व दिए गए हैं, आप ओ (एन) समय में उनमें से एक ढेर बना सकते हैं। यदि आपके पास मूल्यों के सेट के लिए बीएसटी है, तो आप इन्हें ओ (एन) समय में एक इनऑर्डर ट्रैवर्सल करके सॉर्ट कर सकते हैं। आप हे (एन) समय में एक ढेर से एक BST बना सकते हैं, तो आप तो एक हे (एन) द्वारा

1. हे (एन) समय में ढेर बिल्डिंग,
2. छँटाई एल्गोरिथ्म ढेर परिवर्तित हो सकता था ओ (एन) समय में बीएसटी के लिए, और
3. एक क्रमबद्ध अनुक्रम प्राप्त करने के लिए ओ (एन) समय में बीएसटी चलना।

इसलिए, यह हे (एन) के समय में एक BST करने के लिए एक ढेर कन्वर्ट करने के लिए (या ओ में (एन लॉग इन करें n) समय है, जहां ओ little-o notation है) संभव नहीं है।

हालांकि, बीएसटी से अधिकतम मूल्य को बार-बार हटाकर और पेड़ में सही नोड के रूप में डालने के द्वारा ओ (एन लॉग एन) समय में एक ढेर से बीएसटी बनाना संभव है। (आपको तेजी से पहुंच के लिए वहां एक पॉइंटर स्टोर करना होगा; बस रूट पर डालने से ओ (एन) समय लगेगा।)

आशा है कि इससे मदद मिलती है!