मुझे यह समझने के लिए कि 2-3-4 trees ऑपरेशन के बाद ऊंचाई संतुलन संपत्ति संचालन को बनाए रखने के बारे में मूलभूत समझ है, यहां तक कि सबसे खराब केस ऑपरेशंस ओ (एन लॉगन) भी हैं।हम 2-3 या 2-3-4-5 पेड़ों का उपयोग क्यों नहीं करते?
लेकिन मुझे यह समझ में नहीं आता कि केवल 2-3-4 क्यों?
2-3 या 2-3-4-5 क्यों नहीं?
ईमानदार होने के लिए, मुझे 2-3-4 पेड़ों से अवगत नहीं था। मेरे डेटा स्ट्रक्चर क्लास में, हमें 2-3 पेड़ सिखाए गए, और ईमानदार होने के लिए, हम में से अधिकांश ने अभ्यास के गीले हिस्से के लिए एवीएल पेड़ों को लागू किया।
लेकिन जाहिर है, इस प्रकार के पेड़ का सामान्यीकरण है: (a,b) tree।
2-3-4 पेड़ों के कार्यान्वयन के लिए आम तौर पर कई कक्षाओं (2NODE, 3NODE, 4NODE) की आवश्यकता होती है या आपके पास केवल NODE है जिसमें आइटमों की एक श्रृंखला है। कई वर्गों के मामले में आप नोड उदाहरणों का निर्माण और विनाश करने में बहुत समय बर्बाद करते हैं और उन्हें पुनर्निर्मित करना बोझिल है। यदि आप वस्तुओं और बच्चों को पकड़ने के लिए सरणी वाले एक वर्ग का उपयोग करते हैं तो आप या तो लगातार सरणी का आकार बदल रहे हैं जो समान रूप से अपर्याप्त है या आप अप्रयुक्त सरणी तत्वों पर अपनी आधा मेमोरी बर्बाद कर देते हैं। यह रेड-ब्लैक पेड़ों की तुलना में बहुत ही कुशल नहीं है।
लाल-काले पेड़ों में केवल एक प्रकार का नोड संरचना है। चूंकि रेड-ब्लैक पेड़ों में 2-3-4 पेड़ों के साथ एक द्वंद्व है, इसलिए आरबी पेड़ 2-3-4 पेड़ों के समान सटीक एल्गोरिदम का उपयोग कर सकते हैं (कॉर्मन, लीसरसन और रिवेस्ट में वर्णित बेवकूफ भ्रमित/जटिल कार्यान्वयन की आवश्यकता नहीं है एए पेड़ जो 2-3-4 एल्गोरिदम से कम जटिल नहीं हैं।)
तो, कार्यान्वयन की आसानी और उनकी स्मृति/सीपीयू दक्षता के लिए लाल-काले पेड़। (एवीएल पेड़ भी अच्छे होते हैं। वे अधिक संतुलित संतुलित पेड़ पैदा करते हैं और केवल कोड के लिए बेवकूफ होते हैं लेकिन वे थोड़ा अधिक कॉम्पैक्ट पेड़ बनाए रखने के लिए अक्सर काम करने के कारण कम कुशल होते हैं।)
ओह, और 2- 3-4-5-6 ... आदि नहीं किया जाता है क्योंकि कुछ भी प्राप्त नहीं होता है। 2-3-4 से 2-3 पेड़ों पर शुद्ध लाभ होता है क्योंकि उन्हें बिना रिकर्सन के आसानी से किया जा सकता है (रिकर्सन कम कुशल होता है, खासकर जब इसे पूंछ-बार-बार कोडित नहीं किया जा सकता)। हालांकि, बी-पेड़ और बप्लस-पेड़ 2-3-4-5-6-7-8-9-आदि पेड़ हैं जहां नोड्स का अधिकतम आकार, एन चुना जाता है ताकि एन रिकॉर्ड को संग्रहीत किया जा सके एक डिस्क क्षेत्र (यानी प्रत्येक डिस्क क्षेत्र पेड़ में एक नोड है और इस क्षेत्र का आकार नोड में संग्रहीत वस्तुओं की संख्या के बराबर है।) ऐसा इसलिए है क्योंकि स्मृति में 512 रिकॉर्ड्स के माध्यम से खोज करने का समय अभी भी नीचे की तुलना में बहुत तेज़ है पेड़ में एक स्तर जिसके लिए एक और डिस्क की तलाश/लाने की आवश्यकता होती है। और ओ (512) अभी भी ओ (1) है और इस प्रकार पेड़ के लिए ओ (एलजी एन) बनाए रखता है।
यदि आपने कभी 2-3-4 या लाल-काले पेड़ को लागू किया है, तो आप जान लेंगे कि सही करने के लिए बहुत छोटा नहीं है और फिर परीक्षण करें। लाल-काले पेड़ का एक सरलीकृत संस्करण भी है, [एए-पेड़] (http://en.wikipedia.org/wiki/AA_tree), जो लाल-काले पेड़ की तुलना में कम सममित है, फिर भी ऐसा लगता है इसके लिए अच्छा विकल्प है जिसमें कम कार्यान्वयन जटिलता है। जब आपको अधिक उपन्यास या चापलूसी पेड़ की आवश्यकता होती है, तो आप बी-पेड़ों के लिए जाते हैं और एक समान तरीके से कई उपन्यासों का स्पष्ट रूप से समर्थन करते हैं। –
प्लस डेटा इलाके और ओवरहेड-प्रति-नोड (आवंटन लागत के कारण) पर हमेशा चिंताएं होती हैं। इस तरह की चिंताओं अभ्यास में सरणी (जैसे, हैश टेबल) के आधार पर समाधान को प्रोत्साहित करती हैं। –