மரங்கள், சிவப்பு மற்றும் கருப்பு மரங்கள்

"ஹாய், அமிகோ!"

"ஹலோ ரிஷி!"

"அங்கே எனது பழைய குறிப்புகளைக் கண்டுபிடித்தேன், உங்களுக்காக சில சுவாரஸ்யமான விஷயங்களைத் தயார் செய்தேன். நீங்கள் அதைக் கேட்க ஆர்வமாக இருப்பீர்கள் என்று நினைக்கிறேன்."

"இதைக் கேட்போம். நீங்கள் எப்பொழுதும் சுவாரஸ்யமான ஒன்றைக் காண்பீர்கள், அது பின்னர் மிகவும் பயனுள்ளதாக இருக்கும்."

"சரி. இன்று நான் உங்களுக்கு மரங்களைப் பற்றி சொல்ல விரும்புகிறேன் , அதனால் நான் வரைபடங்களுடன் தொடங்குகிறேன் ."

" வரைபடம் என்பது அவற்றை இணைக்கும் புள்ளிகள் மற்றும் கோடுகளின் அமைப்பாகும். புள்ளிகள் வரைபடத்தின் முனைகள் என்றும், கோடுகள் வரைபடத்தின் விளிம்புகள் என்றும் அழைக்கப்படுகின்றன. எடுத்துக்காட்டாக:"

"ஒரு வரைபடம் பல்வேறு நிஜ-உலக செயல்முறைகள் மற்றும் பணிகளுக்கு கணித மாதிரியாகப் பயன்படுத்த மிகவும் வசதியானது. வரைபடங்களுக்காக பல்வேறு பணிகள் மற்றும் வழிமுறைகள் கண்டுபிடிக்கப்பட்டுள்ளன, எனவே அவை மிகவும் அடிக்கடி பயன்படுத்தப்படுகின்றன."

"உதாரணமாக, செங்குத்துகள் நகரங்கள் என்றும், விளிம்புகள் சாலைகள் என்றும் வைத்துக்கொள்வோம். பின்னர் நகரங்களுக்கு இடையே உள்ள குறுகிய சாலையைத் தேடுவது: "வரைபடம் கொடுக்கப்பட்டால், இரண்டு செங்குத்துகளுக்கு இடையே உள்ள குறுகிய பாதையைக் கண்டறியவும்" .

"ஆனால் 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) 13 ஐ விட 7 பெரியதா? இல்லை, எனவே நாம் இடது துணை மரத்திற்கு செல்கிறோம்."

"2a) 7 சமம் 5? இல்லை."

"2b) 5 ஐ விட 7 பெரியதா? ஆம், எனவே நாம் வலது துணை மரத்திற்கு செல்கிறோம்."

"3a) 7 சமம் 8? இல்லை"

"3b) 8 ஐ விட 7 பெரியதா? இல்லை, எனவே நாம் இடது துணை மரத்திற்கு செல்கிறோம்."

"4a) இடது சப்ட்ரீ இல்லை, அதாவது எண் 7 மரத்தில் இல்லை."

"ஆ. வேறு வார்த்தைகளில் கூறுவதானால், வேரிலிருந்து விரும்பிய எண்ணின் இருப்பிடத்திற்குச் செல்லும் பாதையில் உள்ள செங்குத்துகளை மட்டுமே நாம் சரிபார்க்க வேண்டும். ஆம், அது உண்மையில் வேகமானது."

"மேலும் என்னவென்றால், மரம் சமநிலையில் இருந்தால், ஒரு மில்லியன் உறுப்புகளைத் தேட நீங்கள் சுமார் 20 முனைகளைக் கடந்து செல்ல வேண்டும்."

"நான் ஒப்புக்கொள்கிறேன் - அது பல இல்லை."

"சமநிலை மரம் என்றால் என்ன?"

"சிதைந்து போகாத, அதாவது நீளமான கிளைகள் இல்லாத ஒரு மரம். உதாரணமாக, நாம் மரத்தை கட்டும் போது தனிமங்கள் ஏற்கனவே வரிசைப்படுத்தப்பட்டிருந்தால், ஒரு கிளையை உள்ளடக்கிய மிக நீண்ட மரத்தை உருவாக்கியிருப்போம். "

"ஹ்ம்ம். நீங்க சொல்றது சரிதான். அப்போ நாம என்ன செய்வோம்?"

"நீங்கள் ஏற்கனவே யூகித்துள்ளபடி, மிகவும் திறமையான மரமானது ஏறக்குறைய அதே நீளமுள்ள கிளைகளைக் கொண்டுள்ளது. பின்னர் ஒவ்வொரு ஒப்பீடும் மீதமுள்ள துணை மரத்தின் மிகப்பெரிய பகுதியை நிராகரிக்கிறது."

"அப்படியானால், நாம் மரத்தை மீண்டும் கட்ட வேண்டுமா?"

"ஆமாம். இது "சமநிலை" - ஒரு முழுமையான பைனரி மரத்திற்கு முடிந்தவரை நெருக்கமாக இருக்க வேண்டும்."

"இந்தச் சிக்கலைத் தீர்க்க, சுய-சமநிலை மரங்கள் கண்டுபிடிக்கப்பட்டன.  ஒரு உறுப்பைச் சேர்த்த பிறகு மரம் சிதைந்தால், எல்லாவற்றையும் சரியாகச் செய்ய உறுப்புகளை சிறிது மறுவரிசைப்படுத்துகிறது.  சமநிலைப்படுத்துவதற்கான ஒரு எடுத்துக்காட்டு:"

"இந்த மரங்களில் சில சிவப்பு -கருப்பு மரங்கள் என்று அழைக்கப்படுகின்றன ."

"அவர்கள் ஏன் சிவப்பு-கருப்பு என்று அழைக்கப்படுகிறார்கள்?"

"அவர்களின் கண்டுபிடிப்பாளர் இரண்டு வண்ணங்களைப் பயன்படுத்தி அனைத்து முனைகளையும் வரைந்தார். ஒரு நிறம் சிவப்பு, மற்றொன்று கருப்பு. வெவ்வேறு செங்குத்துகள் வெவ்வேறு விதிகளுக்குக் கீழ்ப்படிகின்றன. இது சமநிலை செயல்முறைக்கான முழு அடிப்படையையும் உருவாக்குகிறது."

"உதாரணத்திற்கு:"

"அப்படியானால் இந்த விதிகள் என்ன?"

"1) சிவப்பு உச்சி ஒரு சிவப்பு முனையின் குழந்தையாக இருக்க முடியாது."

"2) ஒவ்வொரு இலையின் கருப்பு ஆழமும் ஒன்றுதான் (கருப்பு ஆழம் என்பது வேரிலிருந்து வரும் பாதையில் உள்ள கருப்பு செங்குத்துகளின் எண்ணிக்கையைக் குறிக்கிறது)."

"3) மரத்தின் வேர் கருப்பு."

"இது எப்படி வேலை செய்கிறது என்பதை நான் விளக்கமாட்டேன் - உங்கள் தலை ஏற்கனவே வெடித்துக்கொண்டிருக்கலாம்."

"ஆமாம். என் செயலி கொஞ்சம் புகையைக் கொடுக்கிறது."

"இதோ உங்களுக்காக ஒரு இணைப்பு. நீங்கள் விரும்பினால், அதைப் பற்றி மேலும் படிக்கலாம்."

கூடுதல் பொருள் இணைப்பு

"இப்போது, ​​போய் ஓய்வு எடுத்துக்கொள்."