Top tree
ஒரு மேல் மரம் என்பது வேரூன்றாத மாறும் மரங்களுக்கான பைனரி மரத்தை அடிப்படையாகக் கொண்ட ஒரு தரவு அமைப்பு ஆகும், இது முக்கியமாக பல்வேறு பாதை தொடர்பான செயல்பாடுகளுக்கு பயன்படுத்தப்படுகிறது. இது எளிய வகுத்தல் மற்றும் வெற்றி வழிமுறைகளை அனுமதிக்கிறது. விட்டம், மையம் மற்றும் சராசரி போன்ற ஒரு மரத்தின் மாறும் பல்வேறு பண்புகளை பராமரிக்க இது பின்னர் அதிகரிக்கப்பட்டுள்ளது. ஒரு மேல் மரம் ஒரு அடிப்படை மரத்திற்கு வரையறுக்கப்படுகிறது மற்றும் வெளிப்புற எல்லை செங்குத்துகள் என்று அழைக்கப்படும் அதிகபட்சம் இரண்டு செங்குத்துகளின் தொகுப்பு சொற்களஞ்சிய எல்லை முனை பார்க்க எல்லை வெர்டெக்ஸ் எல்லை வெர்டெக்ஸ் ஒரு இணைக்கப்பட்ட துணை மரத்தில் ஒரு உச்சி ஒரு விளிம்பால் துணை மரத்திற்கு வெளியே ஒரு உச்சியுடன் இணைக்கப்பட்டிருந்தால் அது ஒரு எல்லை வெர்டெக்ஸ் ஆகும். வெளிப்புற எல்லை செங்குத்துகள் மேல் மரத்தில் ஒரு ஜோடி செங்குத்துகள் வரை வெளிப்புற எல்லை செங்குத்துகள் என்று அழைக்கப்படலாம், அவை கிளஸ்டரின் எல்லை செங்குத்துகளாகக் கருதப்படலாம், இது முழு மேல் மரத்தையும் குறிக்கிறது. கிளஸ்டர் ஒரு கிளஸ்டர் என்பது அதிகபட்சம் இரண்டு எல்லை செங்குத்துகளுடன் இணைக்கப்பட்ட துணை மரமாகும். கொடுக்கப்பட்ட கிளஸ்டரின் எல்லை செங்குத்துகளின் தொகுப்பு ஒவ்வொரு கிளஸ்டருடன் பயனர் சில மெட்டா தகவல்களை இணைக்கலாம் மற்றும் பல்வேறு உள் செயல்பாடுகளின் கீழ் அதை பராமரிப்பதற்கான முறைகளை வழங்கலாம். பாதை கிளஸ்டர் குறைந்தபட்சம் ஒரு விளிம்பைக் கொண்டிருந்தால் அது பாதை கிளஸ்டர் என்று அழைக்கப்படுகிறது. பாயிண்ட் கிளஸ்டர் பார்க்கவும் லீஃப் கிளஸ்டர் லீஃப் கிளஸ்டர் எந்த விளிம்பும் இல்லை என்றால் அதாவது. ஒரே ஒரு எல்லை வெர்டெக்ஸ் இருந்தால் அது லீஃப் கிளஸ்டர் என்று அழைக்கப்படுகிறது. எட்ஜ் கிளஸ்டர் ஒற்றை விளிம்பைக் கொண்ட ஒரு கிளஸ்டர் எட்ஜ் கிளஸ்டர் என்று அழைக்கப்படுகிறது. லீஃப் எட்ஜ் கிளஸ்டர் அசல் கிளஸ்டரில் உள்ள ஒரு இலை ஒரு எல்லை வெர்டெக்ஸ் கொண்ட ஒரு கிளஸ்டரால் குறிக்கப்படுகிறது, மேலும் இது லீஃப் எட்ஜ் கிளஸ்டர் என்று அழைக்கப்படுகிறது. இரண்டு எல்லை முனைகளைக் கொண்ட பாதை விளிம்பு கிளஸ்டர் கிளஸ்டர்கள் பாதை விளிம்பு கிளஸ்டர் என்று அழைக்கப்படுகின்றன. உள் முனை ஒரு முனை கிளஸ்டர் பாதையின் உள் முனை என்று அழைக்கப்படுகிறது எல்லை செங்குத்துகளுக்கு இடையிலான பாதை கிளஸ்டர் பாதை என்று அழைக்கப்படுகிறது, மேலும் இது இணைக்கக்கூடிய கிளஸ்டர்கள் இரண்டு கிளஸ்டர்களால் குறிக்கப்படுகிறது, மேலும் ஒரு சிங்கிள்டன் தொகுப்பாக இருந்தால் அவை இணைக்கப்படுகின்றன (அவை பொதுவான ஒரு முனையைக் கொண்டுள்ளன) மற்றும் ஒரு கிளஸ்டர் ஆகும். இணைப்பு மற்றும் வெட்டு நடவடிக்கைகளின் கீழ் ஒரு மாறும் காடுகளை (மரங்களின் தொகுப்பு) பராமரிக்க மேல் மரங்கள் பயன்படுத்தப்படுகின்றன. அடிப்படை யோசனை என்னவென்றால், அசல் மரத்தில் உள்ள முனைகளின் எண்ணிக்கையில் மடக்கை உயரம் கொண்ட ஒரு சீரான பைனரி மரத்தை பராமரிப்பதாகும் (அதாவது. காலப்போக்கில்); மேல் மரம் அடிப்படையில் அசல் மரத்தின் தொடர்ச்சியான உட்பிரிவுகளை கொத்துகளாகக் குறிக்கிறது. பொதுவாக மரத்தின் விளிம்புகளில் எடை இருக்கலாம். அசல் மரத்தின் விளிம்புகள் மற்றும் மேல் மரத்தின் இலை முனைகளுடன் ஒருவருக்கொருவர் தொடர்பு உள்ளது, மேலும் ஒவ்வொரு உள் முனையும் அதன் குழந்தைகளான கொத்துக்களின் ஒன்றிணைப்பு காரணமாக உருவாகும் ஒரு கிளஸ்டரைக் குறிக்கிறது. மேல் மரம் தரவு கட்டமைப்பை சரியான நேரத்தில் துவக்கலாம். எனவே () க்கு மேல் உள்ள மரம் ஒரு பைனரி மரமாகும், அதாவது முனைகள் () இன் கொத்துக்களாகும்; இதன் இலைகள் உடன்பிறப்பு கொத்துக்களின் விளிம்புகள் அவை ஒரு உச்சியில் வெட்டுகின்றன என்ற பொருளில் அண்டை நாடுகள், பின்னர் அவற்றின் தாய் கொத்து அவற்றின் ஒன்றிணைப்பாகும். மரத்தின் வேர், அதிகபட்சம் இரண்டு வெளிப்புற எல்லை செங்குத்துகளின் தொகுப்பைக் கொண்டுள்ளது. ஒற்றை உச்சியைக் கொண்ட ஒரு மரம் ஒரு வெற்று மேல் மரத்தைக் கொண்டுள்ளது, மேலும் ஒரு விளிம்பைக் கொண்ட ஒன்று ஒரு முனை மட்டுமே. தரவு கட்டமைப்பின் உள் செயல்பாடுகளின் விவரங்களுக்குள் செல்லாமல் பயனருக்கு பல்வேறு வகையான நெகிழ்வுத்தன்மை மற்றும் உற்பத்தித்திறனை அனுமதிக்கும் வகையில் இந்த மரங்கள் சுதந்திரமாக அதிகரிக்கக்கூடியவை, இது பிளாக் பாக்ஸ் என்றும் குறிப்பிடப்படுகிறது. டைனமிக் செயல்பாடுகள் பின்வரும் மூன்றும் பயனர் அனுமதிக்கக்கூடிய வன புதுப்பிப்புகள் ஆகும். இணைப்பு (வி, டபிள்யூ): வெவ்வேறு மரங்கள் 1 மற்றும் 2 இல் செங்குத்துகள் எங்கே மற்றும் உள்ளன. இது வி. டபிள்யூ கட் (வி, டபிள்யூ) ஐக் குறிக்கும் ஒற்றை மேல் மரத்தைத் திருப்பித் தருகிறதுஃ மேல் மரத்தைக் கொண்ட ஒரு மரத்தின் விளிம்பை அகற்றி, அதை இரண்டு மரங்களாக வி மற்றும் டபிள்யூ ஆக மாற்றுகிறது, மேலும் இரண்டு மேல் மரங்கள் வி மற்றும் டபிள்யூ ஐத் திருப்பித் தருகிறது. வெளிப்படுத்து (எஸ்): ஒரு மேல் மரத்தில் பெரும்பாலான கேள்விகளைச் செயல்படுத்துவதற்கான துணை வழிமுறை என்று அழைக்கப்படுகிறது. அதிகபட்சம் 2 செங்குத்துகளைக் கொண்டுள்ளது. இது அசல் வெளிப்புற செங்குத்துகளை சாதாரண செங்குத்துகளாக ஆக்குகிறது மற்றும் மேல் மரத்தின் புதிய வெளிப்புற எல்லை செங்குத்துகளிலிருந்து செங்குத்துகளை உருவாக்குகிறது. காலியாக இல்லாவிட்டால், செங்குத்துகள் வெவ்வேறு மரங்களிலிருந்து இருந்தால், அது புதிய ரூட் கிளஸ்டரை எக்ஸ்போஸ் ({v, w}) தோல்வியுடன் திருப்பித் தருகிறது. உள் செயல்பாடுகள் வன புதுப்பிப்புகள் அனைத்தும் பெரும்பாலான உள் செயல்பாடுகளின் வரிசையால் மேற்கொள்ளப்படுகின்றன, இதன் வரிசை அடுத்த நேரத்தில் கணக்கிடப்படுகிறது. ஒரு மர புதுப்பிப்பின் போது, ஒரு இலைக் கொத்து ஒரு பாதை கொத்து மற்றும் அதற்கு நேர்மாறாக மாறக்கூடும். மேல் மரத்திற்கான புதுப்பிப்புகள் இந்த உள் செயல்பாடுகளால் பிரத்தியேகமாக செய்யப்படுகின்றன. ஒவ்வொரு உள் செயல்பாட்டுடனும் தொடர்புடைய பயனர் வரையறுக்கப்பட்ட செயல்பாட்டை அழைப்பதன் மூலம் புதுப்பிக்கப்படுகிறது. இங்கே இணைக்கவும் மற்றும் இணைக்கக்கூடிய கிளஸ்டர்கள் ஆகும், இது கம்ப்யூட்களின் எல்லை செங்குத்துகளாக மற்றும் எல்லை செங்குத்துகளுடன் தாய் கிளஸ்டராக திரும்புகிறது மற்றும் ஸ்ப்லிட் இங்கே ரூட் கிளஸ்டர் இது புதுப்பிக்கிறது மற்றும் பயன்படுத்துகிறது மற்றும் கிளஸ்டரை நீக்குகிறது. ஸ்ப்லிட் பொதுவாக க்ளீன் முறையைப் பயன்படுத்தி செயல்படுத்தப்படுகிறது, இது அதன் குழந்தைகளில் நிலுவையில் உள்ள புதுப்பிப்பு தேவையில்லை என்று தெரிந்துகொள்ளும் வகையில் புதுப்பிப்புகள் மற்றும் பயன்பாடு மற்றும் புதுப்பிப்புகளுக்கான பயனர் முறையை அழைக்கிறது. பயனர் வரையறுக்கப்பட்ட செயல்பாடுகளை அழைக்காமல் நிராகரிக்கப்படுகிறது. பிரிக்க வேண்டிய அவசியமில்லாமல் கேள்விகளுக்கு பெரும்பாலும் க்ளீன் தேவைப்படுகிறது. ஸ்ப்லிட் க்ளீன் சப்ரூட்டினைப் பயன்படுத்தவில்லை என்றால், க்ளீன் தேவைப்பட்டால், அதன் விளைவை இணைத்தல் மற்றும் ஸ்ப்லிட் ஆகியவற்றை இணைப்பதன் மூலம் மேல்நிலை மூலம் அடைய முடியும். அடுத்த இரண்டு செயல்பாடுகள் மேலே உள்ள இரண்டிற்கும் ஒத்தவை மற்றும் அடிப்படை கிளஸ்டர்களுக்கு பயன்படுத்தப்படுகின்றன. விளிம்பிற்கு ஒரு கிளஸ்டரை உருவாக்குகிறது செட்டுகள் புதிதாக கணக்கிடப்படுகின்றன. எரடிகேட் என்பது எட்ஜ் கிளஸ்டர் பயனர் வரையறுக்கப்பட்ட செயல்பாடு செயலாக்கத்திற்கு அழைக்கப்படுகிறது மற்றும் கிளஸ்டர் மேல் மரத்திலிருந்து நீக்கப்படுகிறது. உள்ளூர் அல்லாத தேடல் பயனர் தேர்ந்தெடுக்கும் செயல்பாட்டை வரையறுக்க முடியும், இது ஒரு வேர் (இலை அல்லாத) கிளஸ்டருக்கு அதன் சைல்ட் கிளஸ்டர்களில் ஒன்றைத் தேர்ந்தெடுக்கிறது. மேல் மர கருப்பு பெட்டி தேடல் வழக்கத்தை வழங்குகிறது, இது தேர்ந்தெடுக்கப்பட்ட கேள்விகள் மற்றும் மேல் மரத்தின் மறுசீரமைப்பை (உள் செயல்பாடுகளைப் பயன்படுத்தி) ஒழுங்கமைக்கிறது, இது தேர்ந்தெடுக்கப்பட்ட அனைத்து கிளஸ்டர்களின் குறுக்குவெட்டில் ஒரே விளிம்பைக் கண்டறிகிறது. சில நேரங்களில் தேடல் ஒரு பாதைக்கு மட்டுப்படுத்தப்பட வேண்டும். அத்தகைய நோக்கங்களுக்காக உள்ளூர் அல்லாத தேடலின் ஒரு மாறுபாடு உள்ளது. ரூட் கிளஸ்டரில் இரண்டு வெளிப்புற எல்லை செங்குத்துகள் இருந்தால், விளிம்பு பாதையில் மட்டுமே தேடப்படும். பின்வரும் மாற்றங்களைச் செய்தால் போதுமானதுஃ ரூட் கிளஸ்டர் குழந்தைகளில் ஒன்று மட்டுமே பாதை கிளஸ்டராக இருந்தால், அது தேர்வு செயல்பாட்டை அழைக்காமல் இயல்பாகவே தேர்ந்தெடுக்கப்படும். உள்ளூர் அல்லாத தேடலின் எடுத்துக்காட்டுகள் முதல் முதல் வரை நீண்ட பாதையில் i-வது விளிம்பைக் கண்டுபிடிப்பது = எக்ஸ்போஸ் ({v, w}) மூலம் செய்யப்படலாம், அதைத் தொடர்ந்து தேடல் () பொருத்தமான தேர்வுடன் செய்யப்படலாம். தேர்வு செய்ய உலகளாவிய மாறி பிரதிநிதித்துவம் மற்றும் உலகளாவிய மாறி பிரதிநிதித்துவம் தேர்வு குறைந்தபட்சம் ஐ. எஃப். எஃப் நீளம் கொண்ட கிளஸ்டர் தேர்ந்தெடுக்கிறது செயல்படுத்த. செயல்பாட்டை ஆதரிக்க நீளம் பராமரிக்கப்பட வேண்டும். இதே போன்ற பணியை அலகு அல்லாத நீளங்களைக் கொண்ட விளிம்புகளைக் கொண்ட வரைபடத்திற்கு வடிவமைக்க முடியும். அவ்வாறான நிலையில், தூரம் இரண்டு விளிம்புகளுக்கு இடையில் ஒரு விளிம்பு அல்லது ஒரு உச்சியை குறிக்கலாம். உச்சிக்கு வழிவகுக்கும் விளிம்பு பிந்தைய வழக்கில் திரும்பும் வகையில் தேர்வு என்பதை நாம் வரையறுக்கலாம். ஒரு பாதையில் அனைத்து விளிம்பு நீளங்களையும் ஒரு மாறிலி மூலம் அதிகரிக்கும் வரையறுக்கப்பட்ட புதுப்பிப்பு இருக்கலாம். அத்தகைய சூழ்நிலையில் இந்த புதுப்பிப்புகள் ரூட் கிளஸ்டரில் மட்டுமே நிலையான நேரத்தில் செய்யப்படுகின்றன. தாமதமான புதுப்பிப்பை குழந்தைகளுக்கு விநியோகிக்க க்ளீன் தேவைப்படுகிறது. தேர்வு செய்யப்படுவதற்கு முன்பு தூய்மையை அழைக்க வேண்டும். நீளத்தை பராமரிக்க, அந்த விஷயத்தில் அலகு நீளத்தையும் பராமரிக்க வேண்டும். உச்சியைக் கொண்ட மரத்தின் மையத்தைக் கண்டுபிடிப்பது இருமுனை விளிம்பை அல்லது மையத்தை ஒரு இறுதிப் புள்ளியாகக் கொண்ட விளிம்பைக் கண்டுபிடிப்பதன் மூலம் செய்யப்படலாம். விளிம்பை = எக்ஸ்போஸ் ({v}) மூலம் காணலாம், அதைத் தொடர்ந்து பொருத்தமான சோஸ் உடன் தேடல் (). தேர்வு அதிக அதிகபட்ச தூரம் கொண்ட குழந்தைகளுடன் குழந்தைகளைத் தேர்ந்தெடுக்கிறது. செயல்பாட்டை ஆதரிக்க, ஒரு எல்லை முனையிலிருந்து கிளஸ்டர் சப்ட்ரீயில் அதிகபட்ச தூரம் பராமரிக்கப்பட வேண்டும். அதற்கு கிளஸ்டர் பாதையின் நீளத்தையும் பராமரிக்க வேண்டும். சுவாரஸ்யமான முடிவுகள் மற்றும் பயன்பாடுகள் பிற முறைகளால் முதலில் செயல்படுத்தப்பட்ட பல சுவாரஸ்யமான பயன்பாடுகள் மேல் மரத்தின் இடைமுகத்தைப் பயன்படுத்தி எளிதாக செயல்படுத்தப்பட்டுள்ளன. அவற்றில் சில ([ஸ்லீட்டர் மற்றும் டார்ஜன் 1983]) அடங்கும். ஒரு இணைப்பு மற்றும் வெட்டு நேரத்தில் எடையுள்ள மரங்களின் மாறும் தொகுப்பை நாம் பராமரிக்க முடியும், எந்த இரண்டு செங்குத்துகளுக்கும் இடையிலான அதிகபட்ச விளிம்பு எடை பற்றிய கேள்விகளை ஆதரிக்கிறது. ஆதார அவுட்லைன்ஃ இது ஒவ்வொரு முனையிலும் அதன் கிளஸ்டர் பாதையில் அதிகபட்ச எடையை (அதிகபட்சம் _ டபிள்யூடி) பராமரிப்பதை உள்ளடக்கியது, இது ஒரு புள்ளி கிளஸ்டராக இருந்தால், அதிகபட்சம் _ டபிள்யூடி () என துவக்கப்படுகிறது ஒரு கிளஸ்டர் இரண்டு கிளஸ்டர்களின் சங்கமமாக இருக்கும்போது, அது இணைக்கப்பட்ட இரண்டு கிளஸ்டர்களின் அதிகபட்ச மதிப்பாகும். அதற்கும் அதற்கும் இடையில் அதிகபட்சம் wt ஐக் கண்டுபிடிக்க வேண்டுமானால், நாம் எக்ஸ்போஸ் மற்றும் ரிப்போர்ட் அதிகபட்சம் _ wt ([SLEATOR and TARJAN 1983]) செய்கிறோம். மேலே உள்ள பயன்பாட்டின் சூழ்நிலையில், கொடுக்கப்பட்ட பாதையில் உள்ள அனைத்து விளிம்புகளுக்கும் ஒரு பொதுவான எடையைச் சேர்க்கலாம். ஆதார அவுட்லைன்ஃ அனைத்து விளிம்புகளிலும் சேர்க்க வேண்டிய கூடுதல் () என்ற எடையை நாங்கள் அறிமுகப்படுத்துகிறோம், அதில் சரியான முறையில் பராமரிக்கப்படுகிறது; ஸ்ப்லிட் () தேவைப்படுகிறது, ஒவ்வொரு பாதை குழந்தைக்கும் நாம் அதிகபட்சம் _ டபிள்யூடி (ஏ): = அதிகபட்சம் _ டபிள்யூடி () + கூடுதல் () மற்றும் கூடுதல் (): = கூடுதல் () + கூடுதல் (). இதற்குஃ = சேர் (), நாம் அதிகபட்சம் _ டபிள்யூடி (): = அதிகபட்சம் {அதிகபட்சம் _ டபிள்யூடி (), அதிகபட்சம் _ டபிள்யூடி ()} மற்றும் கூடுதல் (): = 0 ஐ அமைக்கிறோம். இறுதியாக, பாதையில் அதிகபட்ச எடையைக் கண்டறிய ··· நாம் அமைக்கிறோம்ஃ = வெளிப்படுத்துங்கள் மற்றும் மாக்ஸ் _ டபிள்யூடி () ஐத் திருப்பித் தரவும். ([GOLDBERG ET AL. 1991]). கொடுக்கப்பட்ட உச்சியைக் கொண்ட அடிப்படை மரத்தின் அதிகபட்ச எடையை நாம் சரியான நேரத்தில் கேட்கலாம். ஆதார அவுட்லைன்ஃ இதற்கு இணைப்பு மற்றும் பிளவு செயல்பாடுகளின் கீழ் ஒரு கிளஸ்டரில் அதிகபட்ச எடை அல்லாத கிளஸ்டர் பாதை விளிம்பைப் பற்றிய கூடுதல் தகவல்களைப் பராமரிக்க வேண்டும். இரண்டு செங்குத்துகளுக்கு இடையிலான தூரம் மற்றும் நீளமாக நேரத்தைக் காணலாம் (வெளிப்படுத்துங்கள்). ஆதார அவுட்லைன்ஃ கிளஸ்டர் பாதையின் நீளம் () ஐ பராமரிப்போம். நீளம் அதிகபட்ச எடையாக பராமரிக்கப்படுகிறது, தவிர, ஒரு இணைப்பால் (இணைத்தல்) உருவாக்கப்பட்டால், நீளம் () என்பது அதன் பாதை குழந்தைகளுடன் சேமிக்கப்பட்ட நீளங்களின் கூட்டுத்தொகையாகும். ஒரு மரத்தின் விட்டம் மற்றும் அதன் அடுத்தடுத்த பராமரிப்பு பற்றிய கேள்விகளுக்கு நேரம் எடுக்கும். மையம் மற்றும் சராசரி இணைப்பு (இணைத்தல்) மற்றும் வெட்டு (பிளவு) செயல்பாடுகளின் கீழ் பராமரிக்கப்படலாம் மற்றும் உள்ளூர் அல்லாத தேடல் மூலம் சரியான நேரத்தில் விசாரிக்கப்படலாம். மாறும் இரண்டு முனை இணைப்புக்கான அதிநவீன வழிமுறைகளில் மேல் மரங்கள் பயன்படுத்தப்படுகின்றன. இந்த சிக்கலில், டைனமிக் இணைப்பைப் போலவே, வரைபடமும் விளிம்பில் நீக்குதல் மற்றும் செருகலுக்கு உட்பட்டது, அதே போல் ஒரு ஜோடி செங்குத்துகள் இரண்டு விளிம்புகளுடன் இணைக்கப்பட்டுள்ளதா அல்லது அவற்றைப் பிரிக்கும் ஒரு பாலம் உள்ளதா என்று கேட்கும் கேள்விகளும் உள்ளன. ஹோல்ம், டி லிச்சென்பெர்க் மற்றும் தோரப் ஆகியோர் கடனுதவி செய்யப்பட்ட புதுப்பிப்பு நேரம் மற்றும் வினவல் நேரத்துடன் ஒரு தீர்மானகரமான வழிமுறையை வழங்குகிறார்கள். ஹோல்ம், ரோட்டன்பெர்க் மற்றும் தோரப் ஆகியோரின் அடுத்தடுத்த வேலைகள் இதை ஒரு கடனுதவி புதுப்பிப்பு நேரமாக மேம்படுத்துகின்றன, மேலும் மேல் மரங்களைப் பயன்படுத்துகின்றன வரைபடத்தை பராமரிக்க முடியும், இது விளிம்பு தொகுப்பைப் புதுப்பிக்கவும், உச்சி 2-இணைப்பு குறித்து கேள்விகளைக் கேட்கவும் அனுமதிக்கிறது. புதுப்பிப்புகளின் கடனுதவி சிக்கலானது. கேள்விகளை இன்னும் விரைவாக செயல்படுத்த முடியும். வழிமுறை அற்பமானது அல்ல, இடத்தைப் பயன்படுத்துகிறது. டிஏஜி சுருக்கத்தை விட ஒருபோதும் மோசமாக இல்லாத வகையில் மரங்களை சுருக்க மேல் மரங்களைப் பயன்படுத்தலாம், ஆனால் அதிவேகமாக சிறப்பாக இருக்கலாம். செயல்படுத்தல் மேல் மரங்கள் பல்வேறு வழிகளில் செயல்படுத்தப்பட்டுள்ளன, அவற்றில் சில பல நிலை பகிர்வு (மேல் மரங்கள் மற்றும் மாறும் வரைபட வழிமுறைகள் ஜேக்கப் ஹோல்ம் மற்றும் கிறிஸ்டியன் டி லிச்சென்பெர்க்) பயன்படுத்தி செயல்படுத்தப்படுகின்றன. தொழில்நுட்ப அறிக்கை), மற்றும் ஸ்லேட்டர்-டார்ஜன் எஸ்-டி மரங்களைப் பயன்படுத்துவதன் மூலமும் (பொதுவாக கடனுதவி செய்யப்பட்ட கால வரம்புகளுடன்), ஃப்ரெடெரிக்சனின் இடவியல் மரங்கள் (மோசமான நேர வரம்புகளுடன்) (ஆல்ஸ்ட்ரப் மற்றும் பலர். மேல் மரங்களுடன் முழுமையாக மாறும் மரங்களில் தகவல்களைப் பராமரித்தல்). கடனுதவி செய்யப்பட்ட செயலாக்கங்கள் மிகவும் எளிமையானவை, மேலும் நேர சிக்கலில் சிறிய பெருக்கக் காரணிகளுடன் உள்ளன. மாறாக, மோசமான நடைமுறைப்படுத்தல்கள் வினவலின் போது தேவையற்ற தகவல் புதுப்பிப்புகளை முடக்குவதன் மூலம் வினவல்களை விரைவுபடுத்த அனுமதிக்கின்றன (விடாமுயற்சி நுட்பங்களால் செயல்படுத்தப்படுகிறது). வினவலுக்கு பதிலளித்த பிறகு, மேல் மரத்தின் அசல் நிலை பயன்படுத்தப்பட்டு வினவல் பதிப்பு நிராகரிக்கப்படுகிறது. ஒரு மரத்தின் கிளஸ்டர்களின் எந்தவொரு பகிர்வையும் கிளஸ்டர் பகிர்வு மரம் CPT மூலம் மரத்தில் உள்ள ஒவ்வொரு கிளஸ்டருக்கும் ஒரு விளிம்பால் மாற்றுவதன் மூலம் குறிப்பிடலாம். பகிர்வுக்கு ஒரு மூலோபாயம் P ஐப் பயன்படுத்தினால், CPT CPTP ஆக இருக்கும் இது ஒரு விளிம்பு மட்டுமே இருக்கும் வரை மீண்டும் மீண்டும் செய்யப்படுகிறது. தொடர்புடைய மேல் மரத்தின் அனைத்து முனைகளும் இந்த பல நிலை பகிர்வின் விளிம்புகளில் தனித்துவமாக வரைபடமாக்கப்பட்டிருப்பதை நாம் கவனிப்போம். மேல் மரத்தில் உள்ள எந்த முனையுடனும் பொருந்தாத பல நிலை பகிர்வில் சில விளிம்புகள் இருக்கலாம், இவை அதற்குக் கீழே உள்ள மட்டத்தில் ஒரு குழந்தையை மட்டுமே குறிக்கும் விளிம்புகள், அதாவது. ஒரு எளிய கிளஸ்டர். கலப்பு கிளஸ்டர்களுடன் ஒத்திருக்கும் விளிம்புகள் மட்டுமே மேல் மரத்தில் உள்ள முனைகளுடன் ஒத்திருக்கின்றன, மரத்தை கிளஸ்டர்களாக பிரிக்கும்போது ஒரு பகிர்வு உத்தி முக்கியமானது. ஒரு கவனமான உத்தி மட்டுமே நாம் ஒரு உயரம் பல நிலை பகிர்வில் (எனவே மேல் மரம்) முடிவடைவதை உறுதி செய்கிறது. அடுத்தடுத்த நிலைகளில் விளிம்புகளின் எண்ணிக்கை ஒரு நிலையான காரணியால் குறைய வேண்டும். ஒரு கீழ் நிலை ஒரு புதுப்பிப்பால் மாற்றப்பட்டால், அதற்கு மேலே உள்ளதை உடனடியாக ஒரு நிலையான எண்ணிக்கையிலான செருகல்கள் மற்றும் நீக்குதல்களைப் பயன்படுத்தி புதுப்பிக்க முடியும். மேற்கண்ட பகிர்வு உத்தி சரியான நேரத்தில் மேல் மரத்தின் பராமரிப்பை உறுதி செய்கிறது. மேலும் காண்க லிங்க்/கட் ட்ரீ யூலர் டூர் ட்ரீ டைனமிக் அல்காரிதம் டைனமிக் இணைப்பு குறிப்புகள் ஸ்டீபன் ஆல்ஸ்ட்ரப், ஜேக்கப் ஹோல்ம், கிறிஸ்டியன் டி லிச்சென்பெர்க் மற்றும் மிக்கெல் தோரப், மேல் மரங்களுடன் முழு டைனமிக் மரங்களில் தகவல்களைப் பராமரித்தல், வழிமுறைகளில் ஏசிஎம் பரிவர்த்தனைகள் (டிஏஎல்ஜி), தொகுதி. 1 (2005), 243-264, ஸ்டீபன் ஆல்ஸ்ட்ரப், ஜேக்கப் ஹோல்ம், கிறிஸ்டியன் டி லிச்சென்பெர்க், மற்றும் மிக்கெல் தோரப், இணைப்புக்கான பாலி-லோகரிதமிக் டெர்மினிஸ்டிக் டைனமிக் வழிமுறைகள், குறைந்தபட்ச ஸ்பானிங் ட்ரீ, 2-எட்ஜ் மற்றும் பைகானக்டிவிட்டி, ஜர்னல் ஆஃப் தி ஏசிஎம், தொகுதி. 48 இதழ் 4 (ஜூலை 2001), 723-760, டொனால்ட் க்னுத். தி ஆர்ட் ஆஃப் கம்ப்யூட்டர் புரோகிராமிங்ஃ ஃபண்டமெண்டல் அல்காரிதம், மூன்றாம் பதிப்பு. அடிசன்-வெஸ்லி, 1997. பிரிவு 2.3: மரங்கள், பக்கங்கள். 308-423. தாமஸ் எச். கோர்மென், சார்லஸ் ஈ. லெய்சர்சன், ரொனால்ட் எல். ரிவெஸ்ட் மற்றும் கிளிஃபோர்ட் ஸ்டீன். வழிமுறைகளின் அறிமுகம், இரண்டாவது பதிப்பு. எம்ஐடி பிரஸ் மற்றும் மெக்ரா-ஹில், 2001. பிரிவு 10.4: வேரூன்றிய மரங்களை பிரதிநிதித்துவப்படுத்துதல், பக். 214-217. அத்தியாயங்கள் 12-14 (பைனரி தேடல் மரங்கள், சிவப்பு-கருப்பு மரங்கள், விரிவாக்க தரவு கட்டமைப்புகள்), pp. 253-320. வெளிப்புற இணைப்புகள் மேல் மரங்களுடன் முழுமையாக மாறும் மரங்களில் தகவல்களைப் பராமரித்தல். ஆல்ஸ்ட்ரப் மற்றும் பலர் மேல் மரங்களை சுயமாக சரிசெய்கிறார்கள். டார்ஜன் மற்றும் வெர்னெக், புரோக். 16வது சோடா, 2005 பைனரி மரங்கள்