5
मैं लाल-काले पेड़ के अपने संस्करण को कार्यान्वित कर रहा हूं, जो ज्यादातर विकिपीडिया (http://en.wikipedia.org/wiki/Red-black_tree) से मेरे एल्गोरिदम का आधार बना रहा है। अधिकांश भाग के लिए यह काफी संक्षेप में है, लेकिन एक ऐसा हिस्सा है जिसे मैं स्पष्टीकरण देना चाहता हूं।रेड-ब्लैक पेड़ - दो गैर-पत्ते वाले बच्चों के साथ एक नोड मिटाना
पेड़ से नोड को मिटाने के दौरान जिसमें 2 गैर पत्ते (गैर-नल) बच्चे हैं, यह कहता है कि दोनों तरफ के बच्चों को हटाने योग्य नोड में स्थानांतरित करने और उस बच्चे को हटाने के लिए कहा जाता है।
मैं उस पर आधारित कुछ पक्ष को हटाने के लिए थोड़ा उलझन में हूं। क्या मैं पक्ष को यादृच्छिक रूप से चुनता हूं, क्या मैं पक्षों के बीच वैकल्पिक हूं, या क्या मैं हर भविष्य में हटाने के लिए एक ही तरफ रहूं?
+1 - जानबूझकर यादृच्छिक व्यवहार शुरू करने से बचें; किसी बिंदु पर, कहीं भी एक बग होगा, और यादृच्छिक व्यवहार बग के प्रभाव को और अधिक परेशान कर देगा, लगातार पुन: उत्पन्न करने के लिए कठिन होगा। –
सहमत हैं। एक परिस्थिति जहां यादृच्छिक व्यवहार शुरू करने लायक है, कुछ निश्चित इनपुटों पर अनुमानित रूप से होने की बजाय, कम संभावना और अप्रत्याशित रूप से पैथोलॉजिकल सबसे खराब केस व्यवहार करना होता है। इसलिए introsort के आविष्कार से पहले qsort में यादृच्छिक पिवट विकल्प। मुझे नहीं लगता कि लाल-काले पेड़ का सबसे खराब मामला व्यवहार यहां उचित ठहराने के लिए पर्याप्त है। एक प्रसिद्ध यादृच्छिक "शायद संतुलित" पेड़ संरचना है, मैं इस पल के लिए इसका नाम याद नहीं कर सकता। –
आपकी त्वरित प्रतिक्रिया के लिए धन्यवाद! – Salami