பி-மரம் மற்றும் பைனரி மரம் இடையே வேறுபாடு
உள்ளடக்கம்
- ஒப்பீட்டு விளக்கப்படம்
- பி-மரத்தின் வரையறை
- ஒழுங்கு B இன் மரத்தின் பண்புகள்
- பைனரி மரத்தின் வரையறை
- பயண நுட்பங்கள்
- தீர்மானம்
பி-மரம் மற்றும் பைனரி மரம் ஆகியவை நேரியல் அல்லாத தரவு கட்டமைப்பின் வகைகள். சொற்கள் ஒத்ததாகத் தோன்றினாலும் எல்லா அம்சங்களிலும் வேறுபட்டவை. ரேமின் அணுகல் வேகம் வட்டை விட அதிகமாக இருப்பதால், வட்டுகளுக்கு பதிலாக பதிவுகள் அல்லது தரவு ரேமில் சேமிக்கப்படும் போது பைனரி மரம் பயன்படுத்தப்படுகிறது. மறுபுறம், தரவை வட்டில் சேமிக்கும்போது பி-மரம் பயன்படுத்தப்படுகிறது, இது மரத்தின் உயரத்தைக் குறைப்பதன் மூலமும் முனையிலுள்ள கிளைகளை அதிகரிப்பதன் மூலமும் அணுகல் நேரத்தைக் குறைக்கிறது.
பி-மரம் மற்றும் பைனரி மரம் ஆகியவற்றுக்கு இடையிலான மற்றொரு வேறுபாடு என்னவென்றால், பி-மரம் அதன் அனைத்து குழந்தை முனைகளையும் ஒரே மட்டத்தில் கொண்டிருக்க வேண்டும், அதே சமயம் பைனரி மரத்திற்கு அத்தகைய கட்டுப்பாடு இல்லை. ஒரு பைனரி மரம் அதிகபட்சம் 2 சப்டிரீக்கள் அல்லது முனைகளைக் கொண்டிருக்கலாம், அதேசமயம் பி-மரத்தில் எம் எந்த சப்டிரீஸ் அல்லது முனைகளையும் கொண்டிருக்க முடியாது, அங்கு எம் என்பது பி-மரத்தின் வரிசை.
- ஒப்பீட்டு விளக்கப்படம்
- வரையறை
- முக்கிய வேறுபாடுகள்
- தீர்மானம்
ஒப்பீட்டு விளக்கப்படம்
ஒப்பிடுவதற்கான அடிப்படை | பி மரம் | பைனரி மரம் |
---|---|---|
அத்தியாவசிய தடை | ஒரு முனை குழந்தை முனைகளின் அதிகபட்ச M எண்ணைக் கொண்டிருக்கலாம் (இங்கு M என்பது மரத்தின் வரிசை). | ஒரு முனை அதிகபட்சம் 2 எண்ணிக்கையிலான சப்டிரீக்களைக் கொண்டிருக்கலாம். |
பயன்படுத்திய | தரவு வட்டில் சேமிக்கப்படும் போது இது பயன்படுத்தப்படுகிறது. | பதிவுகள் மற்றும் தரவு ரேமில் சேமிக்கப்படும் போது இது பயன்படுத்தப்படுகிறது. |
மரத்தின் உயரம் | பதிவுஎம் N (எங்கே m என்பது எம்-வழி மரத்தின் வரிசை) | பதிவு2 என் |
விண்ணப்ப | பல டிபிஎம்எஸ்ஸில் குறியீட்டு அட்டவணை தரவு அமைப்பு. | குறியீடு தேர்வுமுறை, ஹஃப்மேன் குறியீட்டு போன்றவை. |
பி-மரத்தின் வரையறை
ஒரு பி-மரம் என்பது சீரான எம்-வழி மரம் மற்றும் சமச்சீர் வகை மரம் என்றும் அழைக்கப்படுகிறது. இது பைனரி தேடல் மரத்தைப் போன்றது, அங்கு முனைகள் ஒழுங்கற்ற பயணத்தின் அடிப்படையில் ஒழுங்கமைக்கப்படுகின்றன. பி-மரத்தின் இட சிக்கலானது O (n) ஆகும். செருகும் மற்றும் நீக்கும் நேர சிக்கலானது O (log n) ஆகும்.
பி-மரத்திற்கு உண்மையாக இருக்க வேண்டிய சில நிபந்தனைகள் உள்ளன:
- மரத்தின் உயரம் முடிந்தவரை குறைந்தபட்சமாக இருக்க வேண்டும்.
- மரத்தின் இலைகளுக்கு மேலே, வெற்று சப்டிரீக்கள் எதுவும் இருக்கக்கூடாது.
- மரத்தின் இலைகள் ஒரே மட்டத்தில் வர வேண்டும்.
- விடுப்பு முனைகளைத் தவிர அனைத்து முனைகளிலும் குறைந்தது குழந்தைகள் இருக்க வேண்டும்.
ஒழுங்கு B இன் மரத்தின் பண்புகள்
- ஒவ்வொரு முனையிலும் அதிகபட்ச M குழந்தைகள் மற்றும் குறைந்தபட்ச M / 2 குழந்தைகளின் எண்ணிக்கை அல்லது 2 முதல் அதிகபட்சம் வரை எந்த எண்ணும் இருக்கலாம்.
- ஒவ்வொரு முனையிலும் அதிகபட்ச M-1 விசைகளைக் கொண்ட குழந்தைகளை விட ஒரு விசை குறைவாக உள்ளது.
- விசைகளின் ஏற்பாடு முனைகளுக்குள் சில குறிப்பிட்ட வரிசையில் உள்ளது. விசையின் இடதுபுறத்தில் உள்ள சப்டிரீயில் உள்ள அனைத்து விசைகளும் விசையின் முன்னோடிகளாகும், மேலும் விசையின் வலதுபுறத்தில் உள்ளவை வாரிசுகள் என்று அழைக்கப்படுகின்றன.
- ஒரு முழு முனையைச் செருகும் நேரத்தில், மரம் இரண்டு பகுதிகளாகப் பிரிகிறது, மற்றும் சராசரி மதிப்பைக் கொண்ட விசை பெற்றோர் முனையில் செருகப்படுகிறது.
- முனைகள் நீக்கப்படும் போது இணைத்தல் செயல்பாடு நடைபெறுகிறது.
பைனரி மரத்தின் வரையறை
ஒரு பைனரி மரம் என்பது ஒரு மர அமைப்பாகும், இது அதன் குழந்தை முனைகளுக்கு அதிகபட்சம் இரண்டு சுட்டிகளைக் கொண்டிருக்கலாம். இதன் பொருள் ஒரு கணு இருக்கக்கூடிய மிக உயர்ந்த பட்டம் 2 ஆகும், மேலும் பூஜ்ஜியம் அல்லது ஒரு டிகிரி கணு கூட இருக்கலாம்.
கண்டிப்பாக பைனரி மரம், முழுமையான பைனரி மரம், நீட்டிக்கப்பட்ட பைனரி மரம் போன்ற பைனரி மரத்தின் சில வகைகள் உள்ளன.
- கண்டிப்பாக பைனரி மரம் என்பது ஒரு மரமாகும், அங்கு ஒவ்வொரு முனையமும் அல்லாத முனை இடது சப்டிரீ மற்றும் வலது சப்டிரீ ஆகியவற்றைக் கொண்டிருக்க வேண்டும்.
- 2 என்ற நிலையை பூர்த்தி செய்யும் போது ஒரு மரம் முழுமையான பைனரி மரம் என்று அழைக்கப்படுகிறது நான் ஒவ்வொரு மட்டத்திலும் நான் நிலை இருக்கும் முனைகள்.
- திரிக்கப்பட்ட பைனரி என்பது பைனரி மரமாகும், இது 0 முனைகள் அல்லது 2 எண்ணிக்கையிலான முனைகளைக் கொண்டுள்ளது.
பயண நுட்பங்கள்
மரம் குறுக்குவெட்டு என்பது மர தரவு கட்டமைப்பில் அடிக்கடி நிகழ்த்தப்படும் செயல்பாடுகளில் ஒன்றாகும், இதில் ஒவ்வொரு முனையும் ஒரு முறை முறையான வழியில் பார்வையிட்டது.
- ஒழுங்குபடுத்தல்- இந்த மரப் பயணத்தில் இடது சப்டிரீ மீண்டும் மீண்டும் பார்வையிடப்படுகிறது, பின்னர் ரூட் முனை பார்வையிடப்படுகிறது மற்றும் கடைசி வலது சப்டிரீ பார்வையிடப்படுகிறது.
- Preorer- இந்த மரம் பயணத்தில் ரூட் முனை முதலில் இடது சப்டிரீ மற்றும் கடைசி வலது சப்ட்ரீயில் பார்வையிடப்படுகிறது.
- போஸ்டார்டர்- இந்த நுட்பம் இடது சப்டிரீயையும் பின்னர் வலது சப் ட்ரீ மற்றும் கடைசி ரூட் முனையையும் பார்வையிடுகிறது.
- பி-மரத்தில், முனையம் அல்லாத முனை இருக்கக்கூடிய அதிகபட்ச குழந்தை முனைகளின் எண்ணிக்கை எம் ஆகும், எம் என்பது பி-மரத்தின் வரிசை. மறுபுறம், ஒரு பைனரி மரத்தில் அதிகபட்சம் இரண்டு சப்டிரீக்கள் அல்லது குழந்தை முனைகள் இருக்கலாம்.
- தரவு வட்டில் சேமிக்கப்படும் போது பி-மரம் பயன்படுத்தப்படுகிறது, அதே சமயம் ரேம் போன்ற வேகமான நினைவகத்தில் தரவு சேமிக்கப்படும் போது பைனரி மரம் பயன்படுத்தப்படுகிறது.
- பி-மரத்திற்கான பயன்பாட்டின் மற்றொரு பகுதி டிபிஎம்எஸ்ஸில் குறியீட்டு அட்டவணைப்படுத்தல் தரவு கட்டமைப்பு ஆகும், இதற்கு மாறாக, பைனரி மரம் குறியீடு தேர்வுமுறை, ஹஃப்மேன் குறியீட்டு போன்றவற்றில் பயன்படுத்தப்படுகிறது.
- பி-மரத்தின் அதிகபட்ச உயரம் பதிவுஎம்N (M என்பது மரத்தின் வரிசை). எதிராக, பைனரி மரத்தின் அதிகபட்ச உயரம் பதிவு2N (N என்பது முனைகளின் எண்ணிக்கை மற்றும் அடிப்படை 2 ஆகும், ஏனெனில் இது பைனரிக்கானது).
தீர்மானம்
பை-மரம் பைனரி மற்றும் பைனரி தேடல் மரத்தின் மீது பயன்படுத்தப்படுகிறது இதற்கு முக்கிய காரணம் நினைவக வரிசைமுறை, அங்கு உயர் அலைவரிசை சேனல்களுடன் தற்காலிக சேமிப்புடன் CPU இணைக்கப்பட்டுள்ளது, அதே நேரத்தில் CPU குறைந்த அலைவரிசை சேனல் மூலம் வட்டில் இணைக்கப்பட்டுள்ளது. பதிவுகள் ரேமில் (சிறிய மற்றும் வேகமான) சேமிக்கப்படும் போது பைனரி மரம் பயன்படுத்தப்படுகிறது மற்றும் பதிவுகள் வட்டில் (பெரிய மற்றும் மெதுவான) சேமிக்கப்படும் போது பி-மரம் பயன்படுத்தப்படுகிறது. எனவே, பைனரி மரத்திற்கு பதிலாக பி-மரத்தைப் பயன்படுத்துவது அணுகல் நேரத்தை கணிசமாகக் குறைக்கிறது, ஏனெனில் அதிக கிளை காரணி மற்றும் மரத்தின் உயரம் குறைகிறது.