Simplex tree
இடவியல் தரவு பகுப்பாய்வில், ஒரு சிம்ப்ளக்ஸ் மரம் என்பது எந்தவொரு பொதுவான எளிய சிக்கலையும் திறம்பட பிரதிநிதித்துவப்படுத்தப் பயன்படுத்தப்படும் ஒரு வகை முக்கோணமாகும். அதன் முனைகள் மூலம், இந்த தரவு அமைப்பு குறிப்பாக அனைத்து எளிமைகளையும் வெளிப்படையாகக் குறிக்கிறது. அதன் நெகிழ்வான அமைப்பு தொடர்ச்சியான ஒத்த தன்மையை கணக்கிடுவதற்கு பயனுள்ள பல அடிப்படை செயல்பாடுகளை செயல்படுத்த அனுமதிக்கிறது. இந்த தரவு அமைப்பு 2014 ஆம் ஆண்டில் ஜீன்-டேனியல் போய்சொன்னாட் மற்றும் கிளெமென்ட் மரியா ஆகியோரால் கண்டுபிடிக்கப்பட்டது, கட்டுரையில் சிம்ப்ளக்ஸ் ட்ரீஃ பொது எளிய சிக்கல்களுக்கான ஒரு திறமையான தரவு அமைப்பு. இந்த தரவு அமைப்பு சிறிய எளிய வளாகங்களில் திறமையான செயல்பாடுகளை வழங்குகிறது. அடர்த்தியான அல்லது அதிகபட்ச எளிமைகளுக்கு, எலும்புக்கூடு-பிளாக்கர் பிரதிநிதித்துவங்கள் அல்லது டோப்லெக்ஸ் வரைபட பிரதிநிதித்துவங்கள் பயன்படுத்தப்படுகின்றன. வரையறைகள் இடவியல் தரவு பகுப்பாய்வில் பல ஆராய்ச்சியாளர்கள் சிம்ப்ளக்ஸ் மரத்தை எளிமையான வளாகங்களுக்கான மிகவும் கச்சிதமான சிம்ப்ளக்ஸ் அடிப்படையிலான தரவு கட்டமைப்பாகவும், அவற்றின் கணித பண்புகளின் ஒருங்கிணைந்த பயன்பாட்டின் காரணமாக எளிமையான வளாகங்களைப் பற்றிய உள்ளுணர்வு புரிதலை அனுமதிக்கும் தரவு கட்டமைப்பாகவும் கருதுகின்றனர். எந்தவொரு எளிமையான சிக்கலையும் கருத்தில் கொள்ளுங்கள், புள்ளிகள் (0 பரிமாணங்கள்), கோடு பிரிவுகள் (1 பரிமாணம்), முக்கோணங்கள் (2 பரிமாணங்கள்) மற்றும் அவற்றின் n-பரிமாண சகாக்கள் ஆகியவற்றைக் கொண்ட ஒரு தொகுப்பாகும், இது ஒரு இடவியல் இடத்திற்குள் n-சிம்ப்ளக்ஸ் என்று அழைக்கப்படுகிறது. சிம்ப்ளக்ஸ்களின் கணிதப் பண்புகளின்படி, எந்தவொரு n-சிம்ப்ளக்ஸும் பல-சிம்ப்ளக்ஸ்களால் ஆனது. எனவே, கோடுகள் புள்ளிகள், கோடுகளின் முக்கோணங்கள், முக்கோணத்தின் நாற்கரங்கள் ஆகியவற்றால் ஆனவை. ஒவ்வொரு உயர் மட்டமும் n-சிம்ப்ளக்ஸின் செங்குத்துகளுக்கு 1 உச்சியை சேர்ப்பதை கவனிக்கவும். தரவு அமைப்பு சிம்ப்ளக்ஸ் அடிப்படையிலானது, எனவே, இது சிம்ப்ளக்ஸை வரையறுக்கும் புள்ளிகளால் அனைத்து சிம்ப்ளக்ஸ்களையும் தனித்துவமாக பிரதிநிதித்துவப்படுத்த வேண்டும். இதை அடைவதற்கான ஒரு எளிய வழி, ஒவ்வொரு சிம்ப்ளக்ஸையும் அதன் புள்ளிகளால் வரிசைப்படுத்தப்பட்ட வரிசையில் வரையறுப்பது. பரிமாணம் k இன் எளிமையான வளாகமாக இருக்கட்டும், அதன் உச்சி தொகுப்பு, அங்கு செங்குத்துகள் 1 முதல் பெயரிடப்பட்டு அதற்கேற்ப வரிசைப்படுத்தப்படுகின்றன. இப்போது, அனைத்து வெர்டெக்ஸ் லேபிள்களையும் வரிசையில் கொண்ட ஒரு அகராதி அளவை உருவாக்குங்கள். இது 0 பரிமாண சிம்ப்ளக்ஸ்களைக் குறிக்கிறது. பின்னர், ஆரம்ப அகராதியில் உள்ள ஒவ்வொரு உள்ளீட்டின் ஆரம்ப அகராதிக்கான பாதைக்கு, தற்போதைய செங்குத்துகளின் தொகுப்புடன் முழுமையாக இணைக்கப்பட்ட அனைத்து செங்குத்துகளையும் ஒரு குழந்தை அகராதியாகச் சேர்க்கவும், இவை அனைத்தும் அதை விட பெரிய லேபிளைக் கொண்டுள்ளன. இந்த படிநிலையை k மட்டங்களில் பிரதிநிதித்துவப்படுத்துங்கள். தெளிவாக, முதல் அகராதியை ஆழம் 0 என்று கருதினால், இந்த தரவு கட்டமைப்பில் உள்ள எந்தவொரு அகராதியின் ஆழத்திலும் உள்ள எந்த உள்ளீடும் தனித்துவமாக ஒரு-சிம்ப்ளக்ஸ் ஐ குறிக்கிறது. முழுமையைப் பொறுத்தவரை, ஆரம்ப அகராதியின் புள்ளி வெற்று சிம்ப்ளக்ஸின் பிரதிநிதித்துவமாகக் கருதப்படுகிறது. செயல்பாடுகளின் நடைமுறைக்கு, ஒரே மட்டத்தில் மீண்டும் மீண்டும் செய்யப்படும் லேபிள்கள் ஒன்றாக இணைக்கப்பட்டு, ஒரு வளையப்பட்ட இணைக்கப்பட்ட பட்டியலை உருவாக்குகின்றன. இறுதியாக, குழந்தை அகராதிகள் விரைவான மூதாதையர் அணுகலுக்காக, அவர்களின் பெற்றோர் அகராதிக்கான சுட்டிகளையும் கொண்டுள்ளன. ஆக்கபூர்வமான வரையறை k பரிமாணத்தின் எளிமையான காம்ப்ளக்ஸ் ஆக இருக்கட்டும். எளிமையான காம்ப்ளக்ஸை பரஸ்பர பிரத்தியேகமான சிம்ப்ளக்ஸ்களாக சிதைப்பதன் மூலம் தொடங்குகிறோம். எளிமையான வளாகத்திலிருந்து எளிமையான வளாகம் காலியாக இருக்கும் வரை மிக உயர்ந்த வரிசை சிம்ப்ளக்ஸ்களை மீண்டும் மீண்டும் அகற்றுவதன் மூலம் இதை பேராசை வழியில் அடைய முடியும். பின்னர் நாம் ஒவ்வொரு உச்சியையும் 1 முதல் பெயரிட வேண்டும் மற்றும் ஒவ்வொரு சிம்ப்ளக்ஸையும் அதனுடன் தொடர்புடைய "சொல்" உடன் தொடர்புபடுத்த வேண்டும், இது அதன் உச்சிகளின் வரிசைப்படுத்தப்பட்ட பட்டியலாகும். சிம்ப்ளக்ஸை விவரிக்க ஒரே ஒரு வழி இருப்பதால், லேபிள்களை ஆர்டர் செய்வது சிம்ப்ளக்ஸ் மரத்தில் மீண்டும் மீண்டும் செய்யப்படுவதை உறுதி செய்கிறது. பூஜ்ய சிம்ப்ளக்ஸைக் குறிக்கும் பூஜ்ய மூலத்துடன் தொடங்குகிறோம். பின்னர், அனைத்து சிம்ப்ளக்ஸ்கள் வழியாகவும், ஒவ்வொரு சிம்ப்ளக்ஸ் வார்த்தையின் ஒவ்வொரு லேபிளிலும் மீண்டும் மீண்டும் செய்கிறோம். தற்போதைய மூலத்திற்கு லேபிள் ஒரு குழந்தையாக இருந்தால், அந்த குழந்தையை செருகும் செயல்முறையின் தற்காலிக மூலமாக ஆக்குங்கள், இல்லையெனில், குழந்தைக்கு ஒரு புதிய முனையை உருவாக்கி, அதை புதிய தற்காலிக மூலமாக மாற்றி, மீதமுள்ள வார்த்தையுடன் தொடருங்கள். இந்த செயல்பாட்டின் போது, கே அகராதிகள் அனைத்து லேபிள்களுடனும் பராமரிக்கப்பட்டு, தொடர்புடைய லேபிளுக்கான முனையின் முகவரியை செருகுகின்றன. அகராதியில் அந்த இடத்தில் ஏற்கனவே ஒரு முகவரி இருந்தால், பழைய முனையிலிருந்து புதிய முனைக்கு ஒரு சுட்டிக்காட்டி உருவாக்கப்படுகிறது. செயல்முறை முடிந்ததும் ஒவ்வொரு முனையின் அனைத்து குழந்தைகளும் ஒரு அகராதியில் உள்ளிடப்படுகிறார்கள், மேலும் அனைத்து சுட்டிகளும் வளையப்பட்டு இணைக்கப்பட்ட பட்டியல்களை உருவாக்க வளையப்படுகின்றன. ஹாஷ் அட்டவணைகள் போன்ற பரந்த அளவிலான அகராதிகளை இங்கு பயன்படுத்தலாம், ஆனால் சில செயல்பாடுகள் உள்ளீடுகளின் வரிசைப்படுத்தப்பட்ட பயணத்தின் சாத்தியக்கூறுகளைக் கருதுகின்றன, இதனால் சிவப்பு-கருப்பு மரங்களைப் பயன்படுத்துவதற்கான பெரும்பாலான செயல்பாடுகள் அகராதிகளாகும். செயல்பாடுகள் சிம்ப்ளக்ஸ் மரங்கள் எளிமையான சிக்கலான பிரதிநிதித்துவத்திற்கான மிகவும் இடம் திறமையான தரவு கட்டமைப்புகள் அல்ல என்றாலும், குறைந்த தரவுகளில் அவற்றின் செயல்பாடுகள் அதிநவீனமாகக் கருதப்படுகின்றன. இங்கே, இந்த பிரதிநிதித்துவத்தின் மூலம் சாத்தியமான பல்வேறு பயனுள்ள செயல்பாடுகளின் வரம்புகளை நாங்கள் வழங்குகிறோம். இந்த செயல்பாடுகளின் பல செயல்பாடுகள் கிடைக்கின்றன. நாம் முதலில் குறியீட்டை அறிமுகப்படுத்துகிறோம். கொடுக்கப்பட்ட சிம்ப்ளக்ஸ், கடைசி முனையுடன் தொடர்புடைய கொடுக்கப்பட்ட முனை, அந்த முனையுடன் தொடர்புடைய லேபிள், அந்த முனையின் ஆழம், எளிமையான வளாகத்தின் பரிமாணம், ஒரு அகராதியில் அணுகக்கூடிய செயல்பாடுகளின் அதிகபட்ச எண்ணிக்கை (அகராதி ஒரு சிவப்பு-கருப்பு மரமாக இருந்தால், சிக்கலானது). கோஃபேஸ்களின் எண்ணிக்கையைக் கவனியுங்கள், மேலும் சிம்ப்ளக்ஸ் மரத்தின் முனைகளின் எண்ணிக்கை அதை விட ஆழத்தில் லேபிளுடன் முடிவடைகிறது. கவனிக்கவும். சொற்களைத் தேடுதல், செருகுதல் மற்றும் அகற்றுதல் ஆகியவை செய்யப்படுகின்றன. ஒரு முழு சிம்ப்ளக்ஸையும் செருகவும் அகற்றவும் செய்யப்படுகிறது. தொடர்ச்சியான ஒத்த தன்மையைக் கணக்கிடுவது, அல்லது மிகவும் ஈடுபாடு கொண்ட வழியில், பெட்டி எண்களைக் கணக்கிடுவது, ஒரு சிம்ப்ளக்ஸ் மரத்தைப் பயன்படுத்தி மிகவும் திறமையாக ஒரு திறந்த சிக்கலாகவே உள்ளது, இருப்பினும், அரிதான எளிய வளாகங்களில் இந்த பணிக்கான தற்போதைய வழிமுறைகள் அதிநவீன செயல்திறனை அடைகின்றன. சிம்ப்ளக்ஸ் மரங்களின் அமைப்பு உடைக்கக்கூடிய சிம்ப்ளக்ஸ்களின் அடிப்படை சரிவை அனுமதிக்கிறது, இருப்பினும் பொதுவாக இந்த செயல்பாட்டின் வரம்புகள் தெரியவில்லை. அடிப்படை சரிவின் ஒரு துணை வழக்கு விளிம்பு-சுருக்கம் ஆகும். விளிம்பில் சுருக்கத்தை அடைய முடியும். கொடுக்கப்பட்ட சிம்ப்ளக்ஸின் கோஃபேஸ்களைக் கண்டறிவது இதில் அடையப்படலாம். கொடுக்கப்பட்ட சிம்ப்ளக்ஸின் கோஃபாசெட்டுகளைக் கண்டறிவது இதில் அடையப்படலாம். கட்டுமானத்தைப் பொறுத்தவரை, ஆக்கபூர்வமான வரையறையில் பார்ப்பது போல, கட்டுமானம் என்பது எளிமையான வளாகத்தில் உள்ள சிம்ப்ளக்ஸ்களின் எண்ணிக்கை மற்றும் சிக்கலுக்கு விகிதாசாரமாகும். எளிமையான வளாகம் அடர்த்தியாக இருந்தால் இது குறிப்பாக விலை உயர்ந்ததாக இருக்கும். இருப்பினும், கொடி வளாகங்கள், ரிப்ஸ் வளாகங்கள் மற்றும் சாட்சி வளாகங்கள் உள்ளிட்ட குறிப்பிட்ட எளிய வளாகங்களுக்கான சில உகப்பாக்கங்கள். பயன்பாடுகள் சிம்ப்ளக்ஸ் மரம் அரிதான எளிய வளாகங்களில் திறமையானவை. இந்த நோக்கத்திற்காக, உயர் பரிமாண உண்மையான தரவுகளில் (பெரும்பாலும் அரிதாக) கவனம் செலுத்தும் பல தொடர்ச்சியான ஹோமோலஜி வழிமுறைகள் இந்த வழிமுறைகளுக்குள் சிம்ப்ளக்ஸ் மரங்களைப் பயன்படுத்துகின்றன. சிம்ப்ளக்ஸ் மரங்கள் இன்சிடன்ஸ் மேட்ரிக்ஸைப் போல திறமையானவை அல்ல என்றாலும், அவற்றின் சிம்ப்ளக்ஸ் அடிப்படையிலான அமைப்பு தொடர்ச்சியான ஹோமோலஜி வழிமுறைகளுக்குள் எளிமையான சிக்கலான சேமிப்புக்கு பயனுள்ள திறமையானதாக இருக்க அனுமதிக்கிறது. குறிப்புகள் மரங்கள் (தரவு கட்டமைப்புகள்) எளிய தொகுப்புகள்