ट्री बनाम लाल-काले पेड़: जो अंतरिक्ष और समय में बेहतर है?

Question

ट्रे और लाल-काले पेड़ तारों को संग्रहित करने के लिए बहुत ही कुशल हैं।

किसके पास बेहतर समय जटिलता है? अंतरिक्ष जटिलता के बारे में कैसे?

Answer 1

यह कई कारकों पर निर्भर करता है, जैसे कि आप किस तार को संग्रहित कर रहे हैं और कैसे त्रिभुज का प्रतिनिधित्व किया जाता है।

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

अंतरिक्ष उपयोग के संदर्भ में, लाल/काले पेड़ को प्रति नोड दो पॉइंटर्स और एक नोड प्रति स्ट्रिंग की आवश्यकता होगी। (लाल/काला बिट आमतौर पर एक सूचक के कम बिट्स में पैक किया जा सकता है)। इस प्रकार कुल स्थान 2 एन + (सभी तारों की कुल लंबाई) है।

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

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

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