झाडं, लाल-काळी झाडं

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

"हॅलो, ऋषी!"

"मला तिथे माझ्या जुन्या नोटा सापडल्या आणि तुमच्यासाठी काही मनोरंजक साहित्य तयार केले. मला वाटते तुम्हाला ते ऐकण्यात रस असेल."

"चला ऐकूया. तुम्हाला नेहमी काहीतरी मनोरंजक वाटते जे नंतर खूप उपयुक्त ठरते."

"ठीक आहे. आज मी तुम्हाला झाडांबद्दल सांगू इच्छितो , म्हणून मी आलेखाने सुरुवात करेन ."

" आलेख ही बिंदू आणि रेषांची एक प्रणाली आहे जी त्यांना जोडते. बिंदूंना आलेखाचे शिरोबिंदू म्हणतात आणि रेषांना आलेखाच्या कडा म्हणतात. उदाहरणार्थ:"

"विविध वास्तविक-जगातील प्रक्रिया आणि कार्यांसाठी एक आलेख हे गणितीय मॉडेल म्हणून वापरण्यास अतिशय सोयीचे आहे. आलेखांसाठी अनेक भिन्न कार्ये आणि अल्गोरिदम शोधण्यात आले आहेत, म्हणून ते बर्‍याचदा वापरले जातात."

"उदाहरणार्थ, समजा शिरोबिंदू शहरे आहेत आणि कडा रस्ते आहेत. मग शहरांमधील सर्वात लहान रस्ता शोधणे असे होईल: «आलेख दिल्यास, दोन शिरोबिंदूंमधील सर्वात लहान मार्ग शोधा». "

"परंतु A ते B पर्यंतचा मार्ग नेहमीच B पासून A पर्यंतच्या मार्गासारखा नसतो. त्यामुळे, काहीवेळा दोन भिन्न रेषा असण्याला प्राधान्य दिले जाते. हे करण्यासाठी, रेषा (ग्राफच्या कडा) बाणांनी बदलल्या जातात. मध्ये दुसऱ्या शब्दांत, आलेखामध्ये दोन बाण असू शकतात: एक A ते B आणि दुसरा B ते A."

"जर आलेख बाण वापरत असेल, तर त्याला निर्देशित आलेख म्हणतात; जर त्यात फक्त रेषा असतील तर त्याला अनिर्देशित आलेख म्हणतात ."

"प्रत्येक शिरोबिंदूला स्वतःच्या कडांची संख्या असू शकते. एका शिरोबिंदूला सुद्धा कडा असू शकत नाहीत. याउलट, एक शिरोबिंदू प्रत्येक इतर शिरोबिंदूशी कडांनी जोडला जाऊ शकतो.  जर आलेखामधील प्रत्येक शिरोबिंदू एका काठाने जोडलेला असेल, तर त्याला संपूर्ण आलेख म्हणतात .

"जर तुम्ही आलेखामधील प्रत्येक शिरोबिंदूपर्यंत पोहोचण्यासाठी कडांचा वापर करू शकत असाल, तर त्याला जोडलेला आलेख म्हणतात. ज्या आलेखमध्ये तीन वेगळे शिरोबिंदू आहेत आणि कडा नाहीत तो आलेख अजूनही आलेख आहे, परंतु आम्ही त्याला डिस्कनेक्ट केलेला आलेख म्हणतो."

"N शिरोबिंदूंपासून जोडलेला आलेख तयार करण्यासाठी, तुम्हाला किमान N-1 कडा आवश्यक आहेत. या प्रकारच्या आलेखाला वृक्ष म्हणतात."

"शिवाय, सामान्यतः एक शिरोबिंदू झाडाचे मूळ म्हणून निवडले जाते , आणि उर्वरित फांद्या म्हणून घोषित केले जातात. ज्या झाडाच्या फांद्या स्वतःच्या फांद्या नसतात त्यांना पाने म्हणतात . उदाहरणार्थ:"

"जर झाडाच्या प्रत्येक घटकाला दोन मुले असतील, तर त्याला बायनरी ट्री म्हणतात . दुसऱ्या शब्दांत, 0 किंवा 2 फांद्या असू शकतात. तुम्हाला वरच्या उजव्या बाजूला बायनरी झाड दिसेल ."

" झाडाला पूर्ण बायनरी ट्री असे म्हणतात जेव्हा प्रत्येक फांदीला 2 मुले असतात आणि सर्व पाने (मुले नसलेले शिरोबिंदू) एकाच रांगेत असतात."

"उदाहरणार्थ:"

"या झाडांची गरज का आहे?"

"अरे, झाडे बर्‍याच ठिकाणी वापरली जातात. सर्वसाधारणपणे, बायनरी झाडे स्ट्रक्चर्ड डेटाची क्रमवारी लावलेली असतात."

"ते काय आहे?"

"होय, हे अगदी सोपे आहे. आम्ही प्रत्येक शिरोबिंदूमध्ये एक विशिष्ट मूल्य संचयित करतो. आणि प्रत्येक घटक एक नियम पाळतो: उजव्या मुलामध्ये संग्रहित मूल्य शिरोबिंदूमध्ये संग्रहित मूल्यापेक्षा जास्त असणे आवश्यक आहे आणि डाव्या मुलामध्ये संग्रहित मूल्य असणे आवश्यक आहे. शिरोबिंदूमध्ये साठवलेल्या मूल्यापेक्षा कमी असावे.  या क्रमाने आपल्याला आवश्यक असलेल्या झाडाचे घटक द्रुतपणे शोधणे शक्य होते."

"तुम्ही याचा अर्थ काय ते स्पष्ट करू शकता?"

"वृक्ष घटक सहसा जोडून क्रमवारी लावले जातात. समजा आपल्याकडे 7 घटक आहेत: 13, 5, 4, 16, 8, 11, 10"

"झाडात घटक कसे जोडले जातात ते येथे आहे."

"जर आपण या झाडात 7 नंबर शोधत आहोत, तर शोध कसा जाईल"

"0) मुळापासून सुरुवात करा."

"1अ) 7 बरोबर 13 आहे का? नाही"

"1b) 13 पेक्षा 7 मोठे आहे का? नाही, म्हणून आम्ही डाव्या सबट्रीकडे जाऊ."

"2a) 7 बरोबर 5 आहे का? नाही."

"2b) 5 पेक्षा 7 मोठे आहे का? होय, म्हणून आम्ही उजव्या सबट्रीकडे जाऊ."

"3a) 7 बरोबर 8 आहे का? नाही"

"3b) 8 पेक्षा 7 मोठे आहे का? नाही, म्हणून आम्ही डाव्या सबट्रीकडे जाऊ."

"4a) डावे सबट्री नाही, याचा अर्थ 7 नंबर झाडात नाही."

"अहो. दुसऱ्या शब्दांत सांगायचे तर, आपल्याला रूटपासून इच्छित संख्येच्या स्थानापर्यंतच्या मार्गावरील शिरोबिंदू तपासण्याची आवश्यकता आहे. होय, ते खरोखर जलद आहे."

"आणखी काय, जर झाड संतुलित असेल, तर दशलक्ष घटक शोधण्यासाठी तुम्हाला फक्त 20 शिरोबिंदूंमधून जावे लागेल."

"मी सहमत आहे - ते फारसे नाही."

"तुला संतुलित झाड म्हणजे काय?"

"एखादे झाड जे विकृत नाही, म्हणजे ज्याला लांब फांद्या नाहीत. उदाहरणार्थ, जर आम्ही झाड बांधले तेव्हा घटकांची वर्गवारी आधीच केली असती, तर आम्ही एक फांदी असलेले खूप लांब झाड बनवले असते. "

"हम्म. तू बरोबर आहेस. मग आम्ही काय करू?"

"तुम्ही कदाचित आधीच अंदाज केला असेल, सर्वात कार्यक्षम झाडाला फांद्या आहेत ज्यांची लांबी अंदाजे समान आहे. नंतर प्रत्येक तुलना उर्वरित उपवृक्षाचा सर्वात मोठा भाग टाकून देते."

"मग, आम्हाला झाड पुन्हा बांधण्याची गरज आहे?"

"होय. ते «संतुलित» असणे आवश्यक आहे — पूर्ण बायनरी झाडाच्या शक्य तितक्या जवळ केले पाहिजे."

"या समस्येचे निराकरण करण्यासाठी, स्वयं-संतुलित झाडांचा शोध लावला गेला.  जर घटक जोडल्यानंतर झाड विकृत झाले, तर ते सर्व काही ठीक करण्यासाठी घटकांना थोडेसे पुनर्क्रमित करते.  येथे संतुलनाचे उदाहरण आहे:"

"यापैकी काही झाडे लाल -काळी झाडे म्हणून ओळखली जातात."

"त्यांना लाल-काळा का म्हणतात?"

"त्यांच्या शोधकर्त्याने दोन रंगांचा वापर करून सर्व शिरोबिंदू काढले. एक रंग लाल आणि दुसरा काळा होता. भिन्न शिरोबिंदू वेगवेगळ्या नियमांचे पालन करतात. हे संतुलन प्रक्रियेसाठी संपूर्ण आधार तयार करते."

"उदाहरणार्थ:"

"मग हे नियम काय आहेत?"

"1) लाल शिरोबिंदू लाल शिरोबिंदूचे मूल असू शकत नाही."

"२) प्रत्येक पानाची काळी खोली सारखीच असते (काळी खोली म्हणजे मुळापासून मार्गावरील काळ्या शिरोबिंदूंची संख्या).

"३) झाडाचे मूळ काळे असते."

"हे कसे कार्य करते हे मी स्पष्ट करणार नाही - तुमचे डोके आधीच फुटले आहे."

"हो. माझा प्रोसेसर थोडा धूर देत आहे."

"तुमच्यासाठी ही लिंक आहे. तुम्हाला हवे असल्यास, तुम्ही त्याबद्दल इथे अधिक वाचू शकता."

अतिरिक्त साहित्याचा दुवा

"आणि आता, जा ब्रेक घ्या."