पेड़, लाल और काले पेड़

"हाय, अमीगो!"

"नमस्कार, ऋषि!"

"मुझे अपने पुराने नोट्स वहाँ मिले और मैंने आपके लिए कुछ रोचक सामग्री तैयार की। मुझे लगता है कि आप इसे सुनने में रुचि लेंगे।"

"चलो इसे सुनते हैं। आप हमेशा कुछ दिलचस्प पाते हैं जो बाद में बहुत उपयोगी साबित होता है।"

"ठीक है। आज मैं आपको पेड़ों के बारे में बताना चाहता हूं , इसलिए मैं ग्राफ से शुरुआत करूंगा ।"

" एक ग्राफ़ बिंदुओं और रेखाओं की एक प्रणाली है जो उन्हें जोड़ती है। बिंदुओं को ग्राफ़ के कोने कहा जाता है, और रेखाओं को ग्राफ़ के किनारे कहा जाता है। उदाहरण के लिए:"

"विभिन्न वास्तविक दुनिया की प्रक्रियाओं और कार्यों के लिए एक गणितीय मॉडल के रूप में उपयोग करने के लिए एक ग्राफ बहुत सुविधाजनक है। ग्राफ के लिए कई अलग-अलग कार्यों और एल्गोरिदम का आविष्कार किया गया है, इसलिए उनका उपयोग काफी बार किया जाता है।"

"उदाहरण के लिए, मान लें कि कोने शहर हैं, और किनारे सड़कें हैं। फिर शहरों के बीच सबसे छोटी सड़क की खोज बन जाती है: «एक ग्राफ दिया गया है, दो कोने के बीच सबसे छोटा रास्ता खोजें»। "

"लेकिन A से B तक का पथ हमेशा B से A तक के पथ के समान नहीं होता है। इसलिए, कभी-कभी दो अलग-अलग रेखाओं को प्राथमिकता दी जाती है। ऐसा करने के लिए, रेखाओं (ग्राफ़ के किनारों) को तीरों से बदल दिया जाता है। में दूसरे शब्दों में, ग्राफ़ में दो तीर हो सकते हैं: एक A से B तक, और दूसरा B से A तक।"

"यदि ग्राफ़ तीरों का उपयोग करता है, तो इसे निर्देशित ग्राफ़ कहा जाता है ; यदि इसमें केवल रेखाएँ हैं, तो इसे एक अप्रत्यक्ष ग्राफ़ कहा जाता है ।"

"प्रत्येक शीर्ष के किनारों की अपनी संख्या हो सकती है। एक शीर्ष के पास भी कोई किनारा नहीं हो सकता है। इसके विपरीत, एक शीर्ष को किनारों से हर दूसरे शीर्ष से जोड़ा जा सकता है। यदि ग्राफ में प्रत्येक जोड़ी को किनारे से जोड़ा जाता है, तो  फिर इसे एक पूर्ण ग्राफ कहा जाता है। "

"यदि आप किसी ग्राफ़ में प्रत्येक शीर्ष तक पहुँचने के लिए किनारों का उपयोग कर सकते हैं, तो इसे कनेक्टेड ग्राफ़ कहा जाता है। एक ग्राफ़ जिसमें तीन अलग-अलग कोने होते हैं और कोई किनारा नहीं होता है, फिर भी एक ग्राफ़ होता है, लेकिन हम इसे डिस्कनेक्टेड ग्राफ़ कहते हैं।"

"N कोने से जुड़ा हुआ ग्राफ़ बनाने के लिए, आपको कम से कम N-1 किनारों की आवश्यकता होती है। इस प्रकार के ग्राफ़ को ट्री कहा जाता है।"

"इसके अलावा, आमतौर पर एक शीर्ष को पेड़ की जड़ के रूप में चुना जाता है , और बाकी को शाखाओं के रूप में घोषित किया जाता है। पेड़ की शाखाएँ जिनकी अपनी शाखाएँ नहीं होती हैं, उन्हें पत्तियाँ कहा जाता है । उदाहरण के लिए:"

"यदि पेड़ के प्रत्येक तत्व के दो बच्चे हैं, तो इसे बाइनरी पेड़ कहा जाता है । दूसरे शब्दों में, 0 या 2 शाखाएं हो सकती हैं। आप ऊपरी दाएं भाग में एक बाइनरी पेड़ देख सकते हैं ।"

" एक पेड़ को पूर्ण बाइनरी ट्री कहा जाता है जब प्रत्येक शाखा में 2 बच्चे होते हैं, और सभी पत्ते (बच्चों के बिना कोने) एक ही पंक्ति में होते हैं।"

"उदाहरण के लिए:"

"इन पेड़ों की आवश्यकता क्यों है?"

"ओह, पेड़ों का उपयोग कई जगहों पर किया जाता है। सामान्य तौर पर, बाइनरी पेड़ संरचित डेटा को क्रमबद्ध करते हैं।"

"वह क्या है?"

"हाँ, यह बहुत सरल है। हम प्रत्येक शीर्ष में एक निश्चित मान संग्रहीत करते हैं। और प्रत्येक तत्व एक नियम का पालन करता है: दाहिने बच्चे में संग्रहीत मूल्य शीर्ष में संग्रहीत मूल्य से अधिक होना चाहिए, और बाएं बच्चे में संग्रहीत मूल्य होना चाहिए वर्टेक्स में संग्रहीत मूल्य से कम हो।  यह ऑर्डरिंग पेड़ के उन तत्वों को तुरंत ढूंढना संभव बनाता है जिनकी आपको आवश्यकता है।"

"क्या आप स्पष्ट कर सकते हैं कि इसका क्या मतलब है?"

"वृक्ष तत्वों को आमतौर पर जोड़कर क्रमबद्ध किया जाता है। मान लीजिए कि हमारे पास 7 तत्व हैं: 13, 5, 4, 16, 8, 11, 10"

"यहां बताया गया है कि पेड़ में तत्व कैसे जोड़े जाते हैं।"

"अगर हम इस पेड़ में 7 नंबर ढूंढ रहे हैं, तो इस तरह से खोज होगी"

"0) रूट से शुरू करें।"

"1a) क्या 7 बराबर 13 है? नहीं"

"1b) क्या 7 13 से बड़ा है? नहीं, इसलिए हम बाएँ सबट्री की ओर बढ़ते हैं।"

"2a) क्या 7 5 के बराबर है? नहीं।"

"2बी) क्या 7 5 से बड़ा है? हां, तो हम दायें सबट्री की ओर बढ़ते हैं।"

"3a) क्या 7 8 के बराबर है? नहीं"

"3b) क्या 7 8 से बड़ा है? नहीं, इसलिए हम बाएँ सबट्री की ओर बढ़ते हैं।"

"4a) कोई बायां सबट्री नहीं है, जिसका मतलब है कि नंबर 7 ट्री में नहीं है।"

"आह। दूसरे शब्दों में, हमें केवल वांछित संख्या के रूट से संभावित स्थान तक पथ पर कोने की जांच करने की आवश्यकता है। हाँ, यह वास्तव में तेज़ है।"

"क्या अधिक है, अगर पेड़ संतुलित है, तो आपको दस लाख तत्वों को खोजने के लिए केवल लगभग 20 कोने से गुजरना होगा।"

"मैं सहमत हूँ - यह बहुत अधिक नहीं है।"

"संतुलित पेड़ से आपका क्या मतलब है?"

"एक पेड़ जो विकृत नहीं होता है, यानी जिसकी लंबी शाखाएँ नहीं होती हैं। उदाहरण के लिए, यदि हम पेड़ बनाते समय तत्वों को पहले ही छाँट चुके होते, तो हम एक शाखा से मिलकर एक बहुत लंबा पेड़ बना लेते। "

"हम्म। तुम सही हो। तो हम क्या करें?"

"जैसा कि आप शायद पहले ही अनुमान लगा चुके हैं, सबसे कुशल पेड़ की शाखाएँ लगभग समान लंबाई की होती हैं। फिर प्रत्येक तुलना शेष सबट्री के सबसे बड़े हिस्से को छोड़ देती है।"

"तो, हमें पेड़ का पुनर्निर्माण करने की आवश्यकता है?"

"हाँ। इसे «संतुलित" करने की आवश्यकता है - एक पूर्ण बाइनरी ट्री के जितना संभव हो उतना करीब बनाने के लिए।

"इस समस्या को हल करने के लिए, स्व-संतुलन वाले पेड़ों का आविष्कार किया गया था।  यदि एक तत्व जोड़ने के बाद पेड़ विकृत हो जाता है, तो यह सब कुछ ठीक करने के लिए तत्वों को थोड़ा पुनर्व्यवस्थित करता है।  यहां संतुलन का एक उदाहरण दिया गया है:"

"इनमें से कुछ पेड़ों को लाल -काले पेड़ के रूप में जाना जाता है।"

"उन्हें लाल-काले क्यों कहा जाता है?"

"उनके आविष्कारक ने दो रंगों का उपयोग करके सभी शीर्षों को चित्रित किया। एक रंग लाल था, और दूसरा काला था। अलग-अलग कोने अलग-अलग नियमों का पालन करते हैं। यह संतुलन प्रक्रिया के लिए संपूर्ण आधार बनाता है।"

"उदाहरण के लिए:"

"तो ये नियम क्या हैं?"

"1) एक लाल शीर्ष एक लाल शीर्ष का बच्चा नहीं हो सकता।"

"2) प्रत्येक पत्ती की काली गहराई समान होती है (काली गहराई जड़ से पथ पर काले शीर्षों की संख्या को संदर्भित करती है)।"

"3) पेड़ की जड़ काली है।"

"मैं यह नहीं समझाऊंगा कि यह कैसे काम करता है - आपका सिर शायद पहले से ही फट रहा है।"

"हाँ। मेरा प्रोसेसर थोड़ा धुआँ छोड़ रहा है।"

"यहां आपके लिए एक लिंक है। यदि आप चाहें, तो आप इसके बारे में यहां अधिक पढ़ सकते हैं।"

अतिरिक्त सामग्री से लिंक करें

"और अब, जाओ एक ब्रेक ले लो।"