Tango tree
டாங்கோ மரம் என்பது 2004 ஆம் ஆண்டில் எரிக் டி. டெமைன், டியான் ஹார்மன், ஜான் ஐகோனோ மற்றும் மிஹாய் பேட்ராசுகு ஆகியோரால் முன்மொழியப்பட்ட ஒரு வகை பைனரி தேடல் மரம் ஆகும். இது பியூனஸ் அயர்ஸ் பெயரால் அழைக்கப்படுகிறது, இதில் டாங்கோ சின்னமாக உள்ளது. இது ஒரு ஆன்லைன் பைனரி தேடல் மரமாகும், இது ஆஃப்லைன் உகந்த பைனரி தேடல் மரத்துடன் தொடர்புடைய போட்டி விகிதத்தை அடைகிறது, அதே நேரத்தில் ஒரு முனைக்கு கூடுதல் நினைவக பிட்களை மட்டுமே பயன்படுத்துகிறது. இது முந்தைய நன்கு அறியப்பட்ட போட்டி விகிதத்தை விட மேம்பட்டது. கட்டமைப்பு டாங்கோ மரங்கள் ஒரு பைனரி தேடல் மரத்தை விருப்பமான பாதைகளின் தொகுப்பாகப் பிரிப்பதன் மூலம் செயல்படுகின்றன, அவை துணை மரங்களில் சேமிக்கப்படுகின்றன (எனவே டாங்கோ மரம் மரங்களின் மரமாக குறிப்பிடப்படுகிறது). குறிப்பு மரம் ஒரு டாங்கோ மரத்தை உருவாக்க, குறிப்பு மரம் என்று அழைக்கப்படும் ஒரு முழுமையான பைனரி தேடல் மரத்தை நாம் உருவகப்படுத்துகிறோம், இது அனைத்து கூறுகளையும் கொண்ட ஒரு பாரம்பரிய பைனரி தேடல் மரமாகும். இந்த மரம் உண்மையான செயல்பாட்டில் ஒருபோதும் தோன்றாது, ஆனால் ஒரு டாங்கோ மரத்தின் பின்வரும் துண்டுகளுக்குப் பின்னால் உள்ள கருத்தியல் அடிப்படையாகும். குறிப்பாக, குறிப்பு மரத்தின் உயரம். இது மிக நீளமான பாதையின் நீளத்திற்கு சமம், எனவே மிகப்பெரிய துணை மரத்தின் அளவு. துணை மரங்களை நியாயமான சமநிலையில் வைத்திருப்பதன் மூலம், துணை மரங்களின் உயரத்தை இதனுடன் கட்டுப்படுத்தலாம் இது வழிமுறையின் செயல்திறன் உத்தரவாதங்களின் ஆதாரமாகும். விருப்பமான பாதைகள் முதலில், ஒவ்வொரு முனையிலும் அதன் விருப்பமான சைல்டை வரையறுக்கிறோம், இது ஒரு பாரம்பரிய பைனரி தேடல் மரம் தேடல் மூலம் முறைசாரா முறையில் சமீபத்தில் பார்வையிடப்பட்ட சைல்டாகும். மேலும் முறைப்படி, குழந்தைகள் l (இடது) மற்றும் r (வலது) உடன் p இல் வேரூன்றிய ஒரு துணை மரம் T ஐக் கவனியுங்கள். T இல் மிக சமீபத்தில் அணுகப்பட்ட முனை r இல் வேரூன்றிய துணை மரத்தில் இருந்தால், p இன் விருப்பமான குழந்தையாக r ஐ அமைக்கிறோம், இல்லையெனில் விரும்பத்தக்க குழந்தையாக l ஐ அமைக்கிறோம். T இன் மிக சமீபத்தில் அணுகப்பட்ட முனை p ஆக இருந்தால், வரையறையின்படி l என்பது விருப்பமான குழந்தை என்பதை நினைவில் கொள்க. ஒரு விருப்பமான பாதை வேரில் தொடங்கி, ஒரு இலை முனையை அடையும் வரை விருப்பமான குழந்தைகளைப் பின்பற்றுவதன் மூலம் வரையறுக்கப்படுகிறது. இந்த பாதையில் உள்ள முனைகளை அகற்றுவது மீதமுள்ள மரத்தை பல துணை மரங்களாகப் பிரிக்கிறது, மேலும் ஒவ்வொரு துணை மரத்திலும் நாம் மறுபரிசீலனை செய்கிறோம் (அதன் மூலத்திலிருந்து விருப்பமான பாதையை உருவாக்குகிறது, இது துணை மரத்தை அதிக துணை மரங்களாகப் பிரிக்கிறது). துணை மரங்கள் ஒரு விருப்பமான பாதையை பிரதிநிதித்துவப்படுத்த, அதன் முனைகளை ஒரு சீரான பைனரி தேடல் மரத்தில், குறிப்பாக ஒரு சிவப்பு-கருப்பு மரத்தில் சேமிக்கிறோம். விருப்பமான பாதை P இல் உள்ள ஒவ்வொரு இலை அல்லாத முனை n க்கும், இது ஒரு விருப்பமற்ற சைல்ட் c ஐக் கொண்டுள்ளது, இது ஒரு புதிய துணை மரத்தின் வேர் ஆகும். இந்த மற்ற துணை மரத்தின் வேர் (சி) ஐ பி இல் n உடன் இணைக்கிறோம், இதனால் துணை மரங்களை ஒன்றாக இணைக்கிறோம். ஒவ்வொரு முனையிலும் அந்த முனையின் கீழ் உள்ள துணை மரத்தில் உள்ள முனைகளின் குறைந்தபட்ச மற்றும் அதிகபட்ச ஆழத்தை (குறிப்பு மரத்தில் ஆழம், அதாவது) சேமிப்பதன் மூலம் துணை மரத்தை அதிகரிக்கிறோம். வழிமுறை தேடல் டாங்கோ மரத்தில் ஒரு உறுப்பைத் தேட, குறிப்பு மரத்தைத் தேடுவதை நாம் வெறுமனே உருவகப்படுத்துகிறோம். வேருடன் இணைக்கப்பட்ட விருப்பமான பாதையைத் தேடுவதன் மூலம் தொடங்குகிறோம், இது விருப்பமான பாதையுடன் தொடர்புடைய துணை மரத்தைத் தேடுவதன் மூலம் உருவகப்படுத்தப்படுகிறது. துணை மரத்தில் விரும்பிய உறுப்பு இல்லையென்றால், தேடல் விரும்பிய உறுப்பைக் கொண்ட துணை மரத்தின் வேரின் பெற்றோரில் முடிவடைகிறது (மற்றொரு விருப்பமான பாதையின் தொடக்கம்), எனவே அந்த விருப்பமான பாதைக்கு துணை மரத்தைத் தேடுவதன் மூலம் நாம் தொடர்கிறோம். புதுப்பித்தல் டாங்கோ மரத்தின் கட்டமைப்பைப் பராமரிப்பதற்காக (துணை மரங்கள் விருப்பமான பாதைகளுடன் ஒத்திருக்கின்றன), தேடல்களின் விளைவாக விருப்பமான குழந்தைகள் மாறும்போதெல்லாம் நாம் சில புதுப்பிப்பு வேலைகளைச் செய்ய வேண்டும். ஒரு விருப்பமான குழந்தை மாறும்போது, விருப்பமான பாதையின் மேல் பகுதி கீழ் பகுதியிலிருந்து பிரிக்கப்பட்டு (இது அதன் விருப்பமான பாதையாக மாறுகிறது) மற்றொரு விருப்பமான பாதையுடன் மீண்டும் இணைக்கப்படுகிறது (இது புதிய கீழ் பகுதியாக மாறுகிறது). இதை திறம்பட செய்ய, எங்கள் துணை மரங்களில் வெட்டு மற்றும் இணைவு செயல்பாடுகளை வரையறுப்போம். எங்கள் இணைப்பு செயல்பாட்டில் சேருங்கள் ஒன்றின் மேல் முனை (குறிப்பு மரத்தில்) மற்றொன்றின் கீழ் முனையின் சைல்ட் (அடிப்படையில், தொடர்புடைய விருப்பமான பாதைகளை இணைக்க முடியும்) என்ற பண்பு இருக்கும் வரை இரண்டு துணை மரங்களை இணைக்கும். இது சிவப்பு-கருப்பு மரங்களின் ஒருங்கிணைந்த செயல்பாட்டின் அடிப்படையில் செயல்படும், இது இரண்டு மரங்களை இணைக்கிறது, அவை ஒன்றின் அனைத்து கூறுகளும் மற்றொன்றின் அனைத்து கூறுகளையும் விட குறைவாக இருக்கும் பண்பைக் கொண்டிருக்கும் வரை, மற்றும் பிளவு, இது தலைகீழாக செய்கிறது. குறிப்பு மரத்தில், மேல் பாதையில் இரண்டு முனைகள் உள்ளன என்பதைக் கவனியுங்கள், அதாவது ஒரு முனை அதன் முக்கிய மதிப்பு அவற்றுக்கிடையே இருந்தால் மட்டுமே கீழ் பாதையில் இருக்கும். இப்போது, மேல் பாதையின் கீழ் பாதையில் சேர, அந்த இரண்டு முனைகளுக்கு இடையில் மேல் பாதையை பிரித்து, பின்னர் கீழ் பாதையின் துணை மரத்தின் இருபுறமும் இரண்டு துணை மரங்களை இணைக்கிறோம், மேலும் எங்கள் இறுதி, இணைந்த துணை மரம் உள்ளது. கட் எங்கள் வெட்டு செயல்பாடு ஒரு விருப்பமான பாதையை கொடுக்கப்பட்ட முனையில் இரண்டு பகுதிகளாக உடைக்கும், ஒரு மேல் பகுதி மற்றும் ஒரு கீழ் பகுதி. மேலும் முறையாக, இது ஒரு துணை மரத்தை இரண்டு துணை மரங்களாகப் பிரிக்கும், அதாவது ஒன்று குறிப்பு மரத்தில் ஒரு குறிப்பிட்ட ஆழத்தில் அல்லது அதற்கு மேல் உள்ள அனைத்து முனைகளையும் கொண்டுள்ளது, மற்றொன்று அந்த ஆழத்திற்குக் கீழே உள்ள அனைத்து முனைகளையும் கொண்டுள்ளது. இணைப்பைப் போலவே, மேல் பகுதியில் இரண்டு முனைகள் உள்ளன, அவை கீழ் பகுதியை அடைப்புக்குறிக்குள் கொண்டுள்ளன என்பதை நினைவில் கொள்க. எனவே, பாதையை மூன்று பகுதிகளாகப் பிரிக்க இந்த இரண்டு முனைகளிலும் நாம் வெறுமனே பிரிக்கலாம், பின்னர் இரண்டு வெளிப்புறங்களையும் இணைக்கலாம், எனவே நாம் விரும்பியபடி மேல் மற்றும் கீழ் என இரண்டு பகுதிகளுடன் முடிவடைகிறோம். பகுப்பாய்வு டாங்கோ மரங்களுக்கான போட்டி விகிதத்தை பிணைக்க, நாம் ஒரு அளவுகோலாகப் பயன்படுத்தும் உகந்த ஆஃப்லைன் மரத்தின் செயல்திறனில் குறைந்த வரம்பைக் கண்டுபிடிக்க வேண்டும். டாங்கோ மரத்தின் செயல்திறனில் ஒரு மேல் வரம்பைக் கண்டறிந்தவுடன், போட்டி விகிதத்தை பிணைக்க அவற்றைப் பிரிக்கலாம். உகந்த ஆஃப்லைன் பைனரி தேடல் மரத்தால் செய்யப்பட்ட வேலையின் கீழ் வரம்பைக் கண்டறிய, நாம் மீண்டும் விருப்பமான குழந்தைகளின் கருத்தை பயன்படுத்துகிறோம். ஒரு அணுகல் வரிசையை (தேடல்களின் வரிசை) கருத்தில் கொள்ளும்போது, ஒரு குறிப்பு மர முனையின் விருப்பமான சைல்ட் எத்தனை முறை மாறுகிறது என்பதைக் கண்காணிக்கிறோம். சுவிட்சுகளின் மொத்த எண்ணிக்கை (அனைத்து முனைகளிலும் சுருக்கமாக) கொடுக்கப்பட்ட அணுகல் வரிசையில் எந்தவொரு பைனரி தேடல் மரம் வழிமுறையால் செய்யப்படும் வேலையில் ஒரு அறிகுறியற்ற கீழ் வரம்பைக் கொடுக்கிறது. இது இன்டர்லீவ் லோயர் பௌண்ட் என்று அழைக்கப்படுகிறது. டாங்கோ மரம் இதை டாங்கோ மரங்களுடன் இணைப்பதற்காக, கொடுக்கப்பட்ட அணுகல் வரிசைக்கு டாங்கோ மரம் செய்த வேலையின் மேல் வரம்பைக் காண்போம். நமது மேல் எல்லை இருக்கும், இங்கு k என்பது இன்டர்லீவ்களின் எண்ணிக்கை. மொத்த செலவு இரண்டு பகுதிகளாகப் பிரிக்கப்பட்டுள்ளது, உறுப்பைத் தேடுதல் மற்றும் சரியான மாறிலிகளைப் பராமரிக்க டேங்கோ மரத்தின் கட்டமைப்பைப் புதுப்பித்தல் (விருப்பமான குழந்தைகளை மாற்றுதல் மற்றும் விருப்பமான பாதைகளை மறுசீரமைத்தல்). தேடல் (புதுப்பிக்கப்படாதது) இந்த வரம்பிற்குள் பொருந்துகிறதா என்பதைப் பார்க்க, ஒவ்வொரு முறையும் ஒரு துணை மரத் தேடல் தோல்வியடையும் போது, அடுத்த துணை மரத்திற்கு நாம் செல்ல வேண்டும், இதன் விளைவாக ஒரு விருப்பமான குழந்தை சுவிட்ச் ஏற்படுகிறது (ஏனெனில் பெற்றோர் விரும்பிய பாதை இப்போது குழந்தைக்கு விருப்பமான பாதையில் சேர திசைகளை மாற்றுகிறது). கடைசி மரத்தைத் தவிர அனைத்து துணை மரத் தேடல்களும் தோல்வியுற்றதால் (ஒரு தேடல் வெற்றிகரமாக முடிந்தவுடன் நாம் நிறுத்துகிறோம், இயற்கையாகவே), துணை மரங்களைத் தேடுகிறோம். ஒவ்வொரு தேடலும் எடுக்கும், ஏனெனில் ஒரு துணை மரத்தின் அளவு, குறிப்பு மரத்தின் உயரத்தால் வரையறுக்கப்பட்டுள்ளது. புதுப்பிப்பு செலவு இந்த வரம்பிற்குள் பொருந்துகிறது, ஏனென்றால் நாம் பார்வையிடப்பட்ட ஒவ்வொரு துணை மரத்திற்கும் ஒரு வெட்டு மற்றும் ஒரு இணைப்பை மட்டுமே செய்ய வேண்டும். ஒரு ஒற்றை வெட்டு அல்லது இணைப்பு செயல்பாடு நிலையான எண்ணிக்கையிலான தேடல்கள், பிளவுகள் மற்றும் இணைப்புகளை மட்டுமே எடுக்கும், அவை ஒவ்வொன்றும் துணை மரத்தின் அளவில் மடக்கை நேரத்தை எடுக்கும், எனவே எங்கள் புதுப்பிப்பு செலவு. போட்டி விகிதம் டாங்கோ மரங்கள்-போட்டித்தன்மை கொண்டவை, ஏனென்றால் உகந்த ஆஃப்லைன் பைனரி தேடல் மரத்தால் செய்யப்படும் வேலை குறைந்தபட்சம் k இல் நேரியல் ஆகும் (விருப்பமான குழந்தை சுவிட்சுகளின் மொத்த எண்ணிக்கை), மேலும் டாங்கோ மரத்தால் செய்யப்படும் வேலை அதிகபட்சமாக உள்ளது. மேலும் காண்கஃ பிளே மரம் உகந்த பைனரி தேடல் மரம் சிவப்பு-கருப்பு மரம் மரம் (தரவு அமைப்பு) குறிப்புகள் பைனரி மரங்கள் தேடல் மரங்கள்