Level ancestor problem
வரைபடக் கோட்பாடு மற்றும் கோட்பாட்டு கணினி அறிவியலில், நிலை மூதாதையர் சிக்கல் என்பது கொடுக்கப்பட்ட வேரூன்றிய மரம் T ஐ ஒரு தரவு கட்டமைப்பிற்குள் முன்கூட்டியே செயலாக்குவதில் உள்ள சிக்கலாகும், இது மரத்தின் வேரிலிருந்து கொடுக்கப்பட்ட தூரத்தில் கொடுக்கப்பட்ட முனையின் மூதாதையரை தீர்மானிக்க முடியும். இன்னும் துல்லியமாக, டி என்பது n முனைகளைக் கொண்ட ஒரு வேரூன்றிய மரமாக இருக்கட்டும், மேலும் வி என்பது டி இன் தன்னிச்சையான முனையாக இருக்கட்டும். நிலை மூதாதையர் வினவல் எல்ஏ (வி, டி) முனை வி இன் மூதாதையரை ஆழம் டி இல் கோருகிறது, அங்கு ஒரு மரத்தில் ஒரு முனை வி இன் ஆழம் மரத்தின் வேர் முதல் முனை வி வரையிலான குறுகிய பாதையில் உள்ள விளிம்புகளின் எண்ணிக்கை. இந்த சிக்கலை ஒரு வினவலுக்கு நிலையான நேரத்தில் தீர்க்க முடியும், ஓ (என்) ஐ எடுக்கும் ஒரு முன் செயலாக்க வழிமுறையின் பின்னர், ஓ (என்) சேமிப்பு இடத்தைப் பயன்படுத்தும் தரவு கட்டமைப்பை உருவாக்குகிறது. முட்டாள்தனமான முறைகள் ஒரு முனையின் நிலை மூதாதையரைக் கண்டுபிடிப்பதற்கான எளிய வழி மரத்தின் வேர் நோக்கி மரத்தை ஏறுவதாகும். மரத்தின் வேர் செல்லும் பாதையில், ஒரு முனையின் ஒவ்வொரு மூதாதையரையும் பார்வையிடலாம், எனவே தெரிவிக்கலாம். இந்த வழக்கில், மரத்தை முன்கூட்டியே செயலாக்க வேண்டிய அவசியமில்லை மற்றும் ஒரு கேள்விக்கு பதிலளிக்கும் நேரம் ஓ (எச்) ஆகும், அங்கு "எச்" என்பது மரத்தின் உயரம். மரம் அதிக உயரத்தைக் கொண்டிருக்கக்கூடிய சூழ்நிலைகளில் இந்த அணுகுமுறை சாத்தியமில்லை மற்றும் அதிக எண்ணிக்கையிலான கேள்விகளை செயலாக்க வேண்டும். மாற்றாக, சாத்தியமான அனைத்து தீர்வுகளும் முன்கூட்டியே கணக்கிடப்பட்டு ஒரு அட்டவணையில் சேமிக்கப்படலாம். இந்த வழக்கில், கேள்விகளுக்கு ஓ (1) இல் பதிலளிக்க முடியும், ஆனால் இடம் மற்றும் முன் செயலாக்க நேரம் ஓ (என் 2) ஆகும். எந்தவொரு முன் செயலாக்கமும் இல்லாமல் நிலையான நேரத்தில் பதிலளிக்கக்கூடிய எளிய கேள்விகள் எல்ஏ (வி, 0) மற்றும் எல்ஏ (வி, ஆழம் (வி)) ஆகும். முந்தைய வழக்கில், பதில் எப்போதும் மரத்தின் வேர் மற்றும் பிந்தைய வழக்கில், பதில் முனை v தான். இந்த முடிவுகள் ஒவ்வொன்றும் O (1) ஐ எடுக்கும். ஒரு வளைந்த பைனரி சீரற்ற அணுகல் பட்டியலில் மரத்தின் வழியாக பாதைகளை சேமிப்பது மரத்தை ஒரு நேரத்தில் ஒரு O (1) படி கீழ்நோக்கி நீட்டிக்க அனுமதிக்கிறது, ஆனால் இப்போது தேடலை O (log (p)) இல் தொடர அனுமதிக்கிறது, அங்கு "p" என்பது v இலிருந்து கோரப்பட்ட ஆழத்திற்கு உள்ள தூரம். மரம் குறிப்பாக அகலமாக இருக்கும்போது அல்லது ஆன்லைனில் நீட்டிக்கப்படும்போது இந்த அணுகுமுறை சாத்தியமாகும், எனவே சேமிப்பு மற்றும் அணுகல் நேரம் முற்றிலும் பாதையின் நீளத்தால் தீர்மானிக்கப்படுவதால் திறம்பட முன் செயலாக்க முடியாது. ஜம்ப் சுட்டிக்காட்டி வழிமுறை ஜம்ப் சுட்டிக்காட்டி வழிமுறை O (n log n) நேரத்தில் ஒரு மரத்தை முன்கூட்டியே செயலாக்குகிறது மற்றும் O (log n) நேரத்தில் நிலை மூதாதையர் கேள்விகளுக்கு பதிலளிக்கிறது. ஜம்ப் சுட்டிக்காட்டி வழிமுறை மரத்தின் ஒவ்வொரு முனையிலும் n சுட்டிகளை பதிவு செய்ய இணைக்கிறது. இந்த சுட்டிகள் ஜம்ப் சுட்டிகள் என்று அழைக்கப்படுகின்றன, ஏனெனில் அவை மரத்தின் வேரை நோக்கி மரத்தின் மேல் குதிக்கின்றன. ஒரு மரத்தின் கொடுக்கப்பட்ட முனை v க்கு, வழிமுறை நீளம் குதிப்பவர்களின் வரிசையை சேமிக்கிறது. இந்த வரிசையின் ith உறுப்பு v இன் 2 வது மூதாதையரை சுட்டிக்காட்டுகிறது. அத்தகைய தரவு கட்டமைப்பைப் பயன்படுத்துவது எந்தவொரு முனையிலிருந்தும் மரத்தின் பாதியிலேயே குதிக்க உதவுகிறது. ஒரு வினவலை செயலாக்குமாறு வழிமுறை கேட்கப்படும்போது, இந்த சுட்டிகளைப் பயன்படுத்தி மரத்தின் மீது மீண்டும் மீண்டும் குதிக்கிறோம். தாவல்களின் எண்ணிக்கை அதிகபட்சமாக பதிவு n ஆக இருக்கும், எனவே கேள்விகளுக்கு பதிவு n நேரத்தில் பதிலளிக்க முடியும். ஏணி வழிமுறை ஏணி வழிமுறை ஒரு மரத்தை பாதைகளின் தொகுப்பாக எளிமைப்படுத்தும் யோசனையை அடிப்படையாகக் கொண்டது. இதற்குக் காரணம், முன்னோர்களின் கேள்விகளை சமன் செய்யும்போது பாதைகளை விசாரிப்பது எளிது. ஒரு முனை r இல் வேரூன்றிய n முனைகளைக் கொண்ட ஒரு பாதை P ஐக் கவனியுங்கள். நாம் பாதையை ஏணி எனப்படும் அளவு n இன் வரிசையில் சேமிக்க முடியும், மேலும் ஆழம் (v) ≤ d என்றால் ஏணி [d] ஐத் திருப்புவதன் மூலம் LA (v, d) இன் நிலை மூதாதையர் வினவலுக்கு விரைவாக பதிலளிக்க முடியும். இது O (1) ஐ எடுக்கும். இருப்பினும், கொடுக்கப்பட்ட மரம் ஒரு பாதையாக இருந்தால் மட்டுமே இது வேலை செய்யும். இல்லையெனில், நாம் அதை பாதைகளாக சிதைக்க வேண்டும். இது இரண்டு நிலைகளில் செய்யப்படுகிறதுஃ நீண்ட பாதை சிதைவு மற்றும் நீண்ட பாதைகளை ஏணியில் விரிவுபடுத்துதல். நிலை 1: நீண்ட பாதை சிதைவு இது கொடுக்கப்பட்ட மரத்தை பாதைகளாக சிதைக்கும் ஒரு தொடர்ச்சியான முறையாகும். இந்த நிலைகள் மரத்தில் மிக நீளமான வேர்-இலை பாதையைக் கண்டுபிடிப்பதன் மூலம் தொடங்குகின்றன. இது மரத்திலிருந்து அதன் பிணைப்புகளை உடைப்பதன் மூலம் இந்த பாதையை நீக்குகிறது, இது மீதமுள்ள மரத்தை துணை மரங்களாக உடைக்கும், பின்னர் அது ஒவ்வொரு துணை மரத்தையும் மீண்டும் மீண்டும் செயலாக்கும். ஒவ்வொரு முறையும் ஒரு பாதை சிதைக்கப்படும்போது, வேர் முதல் இலை வரையிலான பாதையில் உள்ள கூறுகளைக் கொண்ட பாதையுடன் இணைந்து ஒரு வரிசை உருவாக்கப்படுகிறது. இந்த மறுநிகழ்வின் அடிப்படை வழக்கு மரம் ஒரு பாதையாக இருக்கும்போது, அதன் அகற்றல் ஒரு வெற்று வரைபடத்தை விட்டுச்செல்கிறது. ஒவ்வொரு உச்சியிலும் ஒரு தனித்துவமான ஏணி உள்ளது, இது அதை உள்ளடக்கிய ஏணி, அதை "வி 'ஸ் லேடர்" என்று அழைக்கிறோம். இருப்பினும், இந்த முன் செயலாக்க கட்டத்திற்குப் பிறகு, கேள்விகளுக்கு விரைவாக பதிலளிக்க முடியாது. உண்மையில் ஒரு நிலை மூதாதையர் வினவலுக்கு பதிலளிப்பதற்காக, வழிமுறை ஒரு பாதையிலிருந்து மற்றொரு பாதைக்கு அது மூலத்தை அடையும் வரை குதிக்க வேண்டும், மேலும் இலை-க்கு-வேர் பாதையில் அத்தகைய பாதைகளின் θ () இருக்கலாம். இது ஓ (என்) நேரத்தில் மரத்தை முன்கூட்டியே செயலாக்கக்கூடிய மற்றும் ஓ () இல் கேள்விகளுக்கு பதிலளிக்கும் ஒரு வழிமுறைக்கு வழிவகுக்கிறது. உகந்த வினவல் நேரத்தை அடைய, கீழே விவரிக்கப்பட்டுள்ள இரண்டாவது கட்டத்தில் முடிவுகளை நாம் செயலாக்க வேண்டும். நிலை 2: நீண்ட பாதைகளை ஏணியில் விரிவுபடுத்துதல் வழிமுறைக்கான முதல் கட்டம் மரத்தை பல வேறுபட்ட பாதைகளாக சிதைக்கிறது. வழிமுறையின் இரண்டாவது கட்டத்தில், ஒவ்வொரு பாதையும் நீட்டிக்கப்படுகிறது, எனவே இதன் விளைவாக வரும் பாதைகள் பரஸ்பர பிரத்தியேகமாக இருக்காது. வழிமுறையின் முதல் கட்டத்தில், ஒவ்வொரு பாதையும் அளவு h 'இன் வரிசையுடன் தொடர்புடையது. அதே வரிசையில் பாதையின் உச்சியில் உள்ள எச் 'உடனடி மூதாதையர்களைச் சேர்ப்பதன் மூலம் இந்த பாதையை விரிவுபடுத்துகிறோம். இது ஒவ்வொரு வரிசையையும் அதன் அசல் அளவை விட இரண்டு மடங்கு விரிவுபடுத்தும், இதன் விளைவாக அனைத்து ஏணியில் 2n மொத்த முனைகள் இருக்கும். ஏணி எண்ணிக்கை மாற்றப்படவில்லை மற்றும் ஒவ்வொரு முனையின் ஏணி ஒரே மாதிரியாக உள்ளது என்பதைக் கவனியுங்கள். ஒரு முனை v ஐ இப்போது பல பாதைகளில் பட்டியலிட முடியும் என்றாலும், அதன் ஏணி வழிமுறை முதல் கட்டத்தில் v உடன் தொடர்புடையது. இந்த இரண்டு நிலைகளும் O (n) இல் உள்ள செயல்முறைகளாக இருக்கலாம், ஆனால் வினவல் நேரம் இன்னும் நிலையானதாக இல்லை. உயரம் h கொண்ட ஒரு முனை u இல் ஒரு நிலை மூதாதையர் வினவலைக் கவனியுங்கள். u இன் ஏணியில் மேலே பயணிப்பதன் மூலம், குறைந்தது 2h உயரம் கொண்ட ஒரு உச்சியை அடைய முடியும். அனைத்து முனைகளும் குறைந்தது 1 உயரத்தைக் கொண்டுள்ளன என்பதைக் கவனியுங்கள், எனவே இதை i முறை செய்த பிறகு, குறைந்தபட்சம் 2i உயரமுள்ள ஒரு முனையை அடைகிறோம், எனவே இதை அதிகபட்சமாக பதிவு n முறை செய்ய வேண்டும். இது O (log n) இன் வினவல் நேரத்தை நமக்கு வழங்குகிறது. நிலை 3: இரண்டு அணுகுமுறைகளையும் இணைத்தல் ஏணி வழிமுறை அதன் சொந்த தந்திரத்தை செய்யவில்லை என்று மாறிவிடும். உண்மையில் ஜம்ப் சுட்டிக்காட்டி வழிமுறை மற்றும் ஏணி வழிமுறை ஒருவருக்கொருவர் பூர்த்தி செய்கின்றன. இரண்டு வழிமுறைகளும் எதிர் திசைகளில் செயல்படுகின்றனஃ ஜம்ப் சுட்டிக்காட்டி வழிமுறை அதிவேகமாக ஹாப்ஸைக் குறைக்கிறது மற்றும் ஏணி வழிமுறை அதிவேகமாக ஹாப்ஸை அதிகரிக்கிறது. இரண்டு வழிமுறைகளின் கலவையால் O (1) நேரத்தில் கேள்விகளுக்கு பதிலளிக்க முடியும். ஒரு ஒற்றை ஜம்ப் சுட்டிக்காட்டி எந்தவொரு கேள்வியையும் குறைந்தபட்சம் மரத்தின் பாதியிலேயே எடுத்துக்கொள்கிறது, அதன் பிறகு ஒரு ஏணியில் ஏறுவது மட்டுமே கேள்விக்கு பதிலளிக்கும். இதன் விளைவாக O (n log n) முன் செயலாக்க நேரம் மற்றும் O (1) வினவல் நேரம் ஏற்படுகிறது. நான்கு ரஷ்யர்களின் முறையைப் பயன்படுத்துவதன் மூலம் முன் செயலாக்கத்தை O (n) நேரமாகக் குறைக்கலாம், இதில் மரம் நேரியல் முன் செயலாக்கத்துடன் ஒரு சிறிய மரமாக குறைக்கப்படுகிறது, மேலும் மிகச் சிறிய மரங்களின் தொகுப்பு, அவை அனைத்து மரங்களின் முழுமையான கணக்கீடு மற்றும் அந்த மரங்களின் முன் செயலாக்கம் இன்னும் O (n) நேரமாக இருக்கும் அளவுக்கு சிறியவை. மரங்களின் அளவு (பதிவு எண்)/4 போதுமானது. பெர்க்மேன் மற்றும் விஷ்கினின் தீர்வு பெர்க்மேன் மற்றும் விஷ்கினின் காரணமாக வேறுபட்ட தீர்வாகும். இந்த தீர்வு மரங்களை பதப்படுத்துவதற்கான யூலர் சுற்றுப்பயண நுட்பத்தை அடிப்படையாகக் கொண்டது. முக்கிய அவதானிப்பு என்னவென்றால், வி இன் கடைசி தோற்றத்திற்குப் பிறகு யூலர் சுற்றுப்பயணத்தில் தோன்றும் ஆழம் டி இன் முதல் முனை எல்ஏ (வி, டி) ஆகும். எனவே, யூலர் சுற்றுப்பயணத்தையும் ஆழத்தைப் பற்றிய தொடர்புடைய தகவல்களையும் உருவாக்குவதன் மூலம், சிக்கல் வரிசைகளில் ஒரு வினவலாகக் குறைக்கப்படுகிறது, இது ஃபைண்ட் ஸ்மாலர் (எஃப்எஸ்) என்று அழைக்கப்படுகிறது. ஒரு வரிசை A மற்றும் செல்லுபடியாகும் குறியீடு i க்கு, FS (i, x) முதல் குறியீடு j> i ஐ A [i] <x (இங்கே, நாம் x = d + 1 ஐப் பயன்படுத்துகிறோம்) என்று காட்டுகிறது. எஃப்எஸ் சிக்கலுக்கு ஒரு திறமையான தீர்வு பொதுவாக கடினம், ஆனால் யூலர் சுற்றுப்பயணங்களிலிருந்து எழும் சிறப்பு வழக்குக்கு எளிதானது; இந்த விஷயத்தில், அருகிலுள்ள கூறுகள் ±1 ஆல் வேறுபடுகின்றன. இந்த யோசனை O (1) வினவல் நேரத்தை வழங்குகிறது, சிக்கலான O (n log n) இன் முன் செயலாக்க வழிமுறையுடன். நான்கு ரஷ்யர்களின் முறையைப் பயன்படுத்துவதன் மூலம் முன் செயலாக்க நேரம் O (n) ஆக மேம்படுத்தப்படுகிறது. மேலும் காண்க ரேஞ்ச் வினவல் (கணினி அறிவியல்) மிகக் குறைந்த பொதுவான மூதாதையர் குறிப்புகள் கோட்பாட்டு கணினி அறிவியல் மரங்கள் (வரைபடக் கோட்பாடு)