पूर्णांक की स्ट्रीम से एक संतुलित बाइनरी खोज पेड़ बनाएं

Question

मैंने अभी नौकरी साक्षात्कार पूरा कर लिया है और मैं इस प्रश्न से जूझ रहा था, जो मुझे 15 मिनट के साक्षात्कार देने के लिए एक बहुत कठिन सवाल के रूप में लगता है।

प्रश्न था: एक फ़ंक्शन लिखें, जो पूर्णांक (अनियंत्रित) की धारा प्रदान करता है, एक संतुलित खोज वृक्ष बनाता है। अब, आप इनपुट समाप्त होने की प्रतीक्षा नहीं कर सकते (यह एक धारा है), इसलिए आपको फ्लाई पर पेड़ को संतुलित करने की आवश्यकता है।

मेरा पहला जवाब लाल-काले पेड़ का उपयोग करना था, जो निश्चित रूप से नौकरी करता है, लेकिन मुझे लगता है कि उन्होंने मुझे 15 मिनट में लाल काले पेड़ को लागू करने की उम्मीद नहीं की थी।

तो, क्या इस समस्या के लिए कोई आसान समाधान है, मुझे पता नहीं है?

धन्यवाद,

डेव

Answer 1

AA Trees थोड़ा लाल काले पेड़ों से सरल हैं, लेकिन मैं अपने सिर के ऊपर से एक को लागू नहीं कर सका।

Answer 2

मुझे व्यक्तिगत रूप से लगता है कि ऐसा करने का सबसे अच्छा तरीका treap जैसे यादृच्छिक बाइनरी खोज पेड़ के लिए जाना होगा। यह बिल्कुल गारंटी नहीं देता है कि पेड़ संतुलित होगा, लेकिन उच्च संभावना के साथ पेड़ का एक अच्छा संतुलन कारक होगा। एक ट्रेप एक समान यादृच्छिक संख्या के साथ पेड़ के प्रत्येक तत्व को बढ़ाकर काम करता है, फिर यह सुनिश्चित करना कि पेड़ एक बाइनरी खोज पेड़ है और चाबियों के संबंध में और समान यादृच्छिक मूल्यों के संबंध में एक ढेर है। एक ट्रेप में सम्मिलन बेहद आसान है:

1. नए जोड़े गए तत्व को असाइन करने के लिए यादृच्छिक संख्या चुनें।
2. मानक बीएसटी सम्मिलन का उपयोग कर बीएसटी में तत्व डालें।
3. जबकि नव-सम्मिलित तत्व की कुंजी अपने माता-पिता की कुंजी से अधिक है, तो अपने तत्व के ऊपर नया तत्व लाने के लिए पेड़ रोटेशन करें।

वह अंतिम चरण केवल एकमात्र कठिन है, लेकिन यदि आपके पास व्हाइटबोर्ड पर काम करने के लिए कुछ समय था, तो मुझे पूरा यकीन है कि आप इस साक्षात्कार में इस पर उड़ान भर सकते हैं।

एक और विकल्प जो काम कर सकता है splay tree का उपयोग करना होगा। यह एक और प्रकार का तेज़ बीएसटी है जिसे यह मान लिया जा सकता है कि आपके पास मानक बीएसटी सम्मिलन समारोह और वृक्षारोपण करने की क्षमता है। महत्वपूर्ण बात यह है कि, पेप्ले पेड़ अत्यंत अभ्यास में तेज़ी से हैं, और यह ज्ञात है कि वे कम से कम किसी अन्य स्थिर बाइनरी खोज पेड़ के रूप में अच्छे (एक स्थिर कारक के भीतर) हैं।

"खोज पेड़" के अर्थ के आधार पर, आप पूर्णांक की तलाश के लिए अनुकूलित कुछ संरचनाओं में पूर्णांक को संग्रहीत करने पर भी विचार कर सकते हैं। उदाहरण के लिए, आप एक पूर्णांक को स्टोर करने के लिए bitwise trie का उपयोग कर सकते हैं, जो मशीन शब्द में बिट्स की संख्या के अनुपात में लुकअप के समय में लुकअप का समर्थन करता है। बिट्स को देखने के लिए इसे रिकर्सिव फ़ंक्शन का उपयोग करके काफी अच्छी तरह से कार्यान्वित किया जा सकता है, और किसी भी प्रकार के घूर्णन की आवश्यकता नहीं होती है। यदि आपको पंद्रह मिनट में कार्यान्वयन को विस्फोट करने की आवश्यकता है, और यदि साक्षात्कारकर्ता आपको मानक बाइनरी खोज पेड़ से विचलित करने की अनुमति देता है, तो यह एक अच्छा समाधान हो सकता है।

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

Answer 3

सबसे सरल संतुलित बाइनरी खोज पेड़ में से एक बीबी (α) -tree है। आप स्थिर α चुनते हैं, जो कहता है कि पेड़ कितना असंतुलित हो सकता है। हर समय, #descendants(child) <= (1-α) × #descendants(node) पकड़ना चाहिए। आप इसे सामान्य बाइनरी खोज पेड़ के रूप में देखते हैं, लेकिन जब सूत्र कुछ नोड पर लागू नहीं होता है, तो आप पेड़ के उस हिस्से को खरोंच से पुनर्निर्माण करते हैं, ताकि यह पूरी तरह संतुलित हो।

सम्मिलन या हटाने के लिए मिश्रित समय जटिलता अभी भी अन्य संतुलित बाइनरी पेड़ों के साथ ओ (लॉग एन) है।