[Powered by Google Translate] நீங்கள் ஒரு கணினி அனைத்து உங்கள் குடும்ப உறுப்பினர்கள் எப்படி பிரதிபலிக்கும்? நாம் சாதாரணமாக, ஒரு பட்டியலை பயன்படுத்த முடியும் ஆனால் ஒரு தெளிவான வரிசைக்கு இங்கே இல்லை. 

நாம் உங்கள் பெரும் பாட்டி, ஆலிஸ் தொடங்கி சொல்கிறீர்கள். அவர் 2 மகன்கள், பாப் உள்ளது உங்கள் தாத்தா, சார்லி. சார்லி, 3 குழந்தைகள் உள்ளனர் உங்கள் மாமா, டேவ், உங்கள் அத்தை, ஈவ், உங்கள் தந்தை, பிரெட். நீங்கள் பிரெட் ஒரே குழந்தை. 

ஏன் இந்த வழியில், உங்கள் குடும்ப உறுப்பினர்கள் ஏற்பாடு எளிய பட்டியல் பிரதிநிதித்துவம் விட வேண்டும்? ஒரு காரணம் என்று இந்த படிநிலை கட்டமைப்பானது, ஒரு எனப்படும் 'மரம்,' ஒரு எளிய பட்டியல் விட தகவல்களை கொண்டுள்ளது. நாம் அனைவரும் இடையே குடும்ப உறவுகள் தெரியும் ஒரு மரம் ஆய்வு மூலம். மேலும், அது வேகமாக முடியாது ஆனால் அப் நேரம் எனலாம், மரம் தரவு வரிசையாக்கம் என்றால். 

நாம் இங்கே அந்த பயன்படுத்தி கொள்ள முடியாது, ஆனால் நாங்கள் விரைவில் இந்த ஒரு உதாரணம் பார்க்கலாம். ஒருவர் மரத்தில் ஒரு முனை குறிப்பிடப்படுகின்றன. முனைகளில் குழந்தை முனைகளில் முடியும் அத்துடன் ஒரு தாய் முனை போன்ற. இந்த, தொழில்நுட்ப சொற்கள் உள்ளன குடும்பங்கள் தவிர விஷயங்கள் மரங்கள் பயன்படுத்தி கூட. ஆலிஸ் இன் முனை, 2 குழந்தைகள் மற்றும் பெற்றோர் உள்ளது சார்லியின் முனை 3 குழந்தைகள் மற்றும் 1 பெற்றோர் உள்ளன. 

ஒரு இலை கணு எந்த குழந்தைகள் இல்லை என்று ஒரு மரம் வெளியே விளிம்பில். மரத்தின் மிக உயர்ந்த முனை, வேர் கணு, எந்த பெற்றோர் உள்ளது. 

ஒரு பைனரி மரம், மரத்தின் ஒரு குறிப்பிட்ட வகை இதில் ஒவ்வொரு கணு, அதிகபட்சம், 2 குழந்தைகள் உள்ளன. இங்கே சி ஒரு பைனரி மரம் ஒரு முனையத்தின் struct உள்ளது ஒவ்வொரு முனையும் அது தொடர்புடைய சில தரவு மற்ற முனைகள் மற்றும் 2 சுட்டிகள். 

எங்கள் குடும்பம் மரம், தொடர்புடைய தரவு ஒவ்வொரு நபரின் பெயர் இருந்தது. இது ஒன்றும் இருக்க முடியும் என்று இங்கே அது ஒரு முழு எண்ணாக இருக்கிறது. அதை திருப்பி என, ஒரு பைனரி மரம், ஒரு குடும்பத்தில் ஒரு நல்ல பிரதிநிதித்துவம் இருக்க மாட்டேன் மக்கள் அடிக்கடி மேற்பட்ட 2 குழந்தைகள் நடத்திவருகிறோம். 

ஒரு பைனரி தேடல் மரம் பைனரி மரம் ஒரு சிறப்பு, உத்தரவின் வகை என்று நம்மை விரைவில் மதிப்புகள் பார்க்க அனுமதிக்கிறது. நீங்கள் கவனித்தீர்களா ஒரு மரத்தின் வேர் கீழே ஒவ்வொரு கணு மற்றொரு மரத்தின் வேர், ஒரு 'உபப்படிநிலையின்.' என்று அழைக்கப்படுகிறது இங்கே, மரத்தின் வேர், 6 அதன் குழந்தை, 2, உபப்படிநிலையின் வேர். 

ஒரு பைனரி தேடல் கிளையில் ஒரு முனை அனைத்து மதிப்புகள் சரியான உபப்படிநிலையின் தான் கணு மதிப்பு அதிகமாக இருக்கும். இங்கே: 6. சரி, ஒரு முனை இடது உபப்படிநிலையின் மதிப்புகள் கணு மதிப்பு குறைவாக இருக்கும். நாங்கள் போலி மதிப்புகள் கையாள வேண்டும் என்றால், நாம், ஒரு தளர்வான சமத்துவமின்மை வேண்டும் அல்லது அந்த மாற்றலாம் ஒரே மதிப்புகள் இடது அல்லது வலது அல்லது கீழ் அதாவது, நீண்ட நாம் முழுவதும் இது பற்றி உறுதியான உள்ளன. இந்த மரம் ஒரு பைனரி தேடல் மரம் இந்த விதிகள் பின்வருமாறு காரணம். 

இந்த நாங்கள் சி structs அனைத்து முனைகளில் திரும்பி அது இருக்கும் என்று எப்படி இருக்கும். கவனிக்க ஒரு குழந்தை இல்லை என்றால், சுட்டிக்காட்டி பூஜ்ய உள்ளது. எப்படி நாம் 7 மரம் இருக்கிறது என்று பார்? நாம் ரூட் துவங்க. அது மரம் என்றால் ஏழு 6 அதிகமாக உள்ளது, எனவே, அதை சரி செய்ய வேண்டும். பின்னர், அது 8 விட குறைவாக இருக்கும், அதனால் அதை விட்டு வேண்டும். இங்கே, நாங்கள் 7 கிடைத்தது. இப்போது, நாங்கள் 5 பார்க்கிறேன். ஐந்து 6 குறைவாக உள்ளது, எனவே அது இடது இருக்க வேண்டும். ஐந்து, 2 விட அதிகமாக இருக்கும் அதனால், சரியான இருக்க வேண்டும் மேலும் 4 விட, அதை சரி மீண்டும் இருக்க வேண்டும். ஆனால், எந்த குழந்தை இங்கே இருக்கிறது. சுட்டிக்காட்டி பூஜ்ய உள்ளது. இந்த 5 எங்கள் மரம் இல்லை என்று அர்த்தம். 

நாம் பின்வரும் குறியீடு இரும மரம் தேடலாம்: ஒவ்வொரு முனையும் போது, நாம் காண வேண்டும் என்பதை பார்க்கவும் நாம் தேடும் மதிப்பு. நாம் அது கிடைக்கவில்லை என்றால் அது இருக்க வேண்டும் என்றால், நாம் தீர்மானிக்க இடது அல்லது வலது மற்றும் அந்த உபப்படிநிலையின் சரிபார்க்கவும். இந்த வட்டத்திற்கு மரம் கீழே வரும் இடது அல்லது வலது அல்லது எந்த குழந்தை முனை உள்ளது வரை. 

5 மரம் இல்லை என்பதை நினைவில் கொள்ளுங்கள். எப்படி நாம் அதை செருகுவது? செயல்முறை தேட போன்ற தோற்றம். நாம், 6 இருந்து தொடங்கி மரம் கீழே கூறு 2 விட்டு, 4 உரிமை, வலது மீண்டும், ஆனால் 4 இந்த பக்கத்தில் எந்த குழந்தையும் உள்ளது. இந்த, 5 புதிய நிலை இருக்கும் அது எந்த குழந்தைகள் ஆரம்பிக்கும். 

எப்படி வேகமாக ஒரு பைனரி தேடல் மரத்தில் நடவடிக்கைகள் என்ன? Bigohnotation ஒரு மேல் வரம்பையே வழங்க முயற்சிக்கின்றது என்பதை நினைவில் கொள்ளுங்கள். மோசமான நிலையில், எங்கள் மரம் வெறுமனே ஒரு இணைக்கப்பட்ட பட்டியலில் இருக்க முடியும் அந்த உட்புகுத்தல், நீக்குதல், மற்றும் தேடல் பொருள் மரம் முனைகளுக்கிடையே எண்ணிக்கை விகிதாசார நேரம் ஆகலாம். இந்த ஓ (n) ஆகும். 

எடுத்துக்காட்டாக, பின்வரும் சரியான பைனரி தேடல் மரம். எனினும், நாம் 9 கண்டுபிடிக்க முயற்சி என்றால், நாம் ஒவ்வொரு கணு தொடரவேண்டும். இது ஒரு இணைக்கப்பட்ட பட்டியலில் விட சிறந்தது. வெறுமனே, நாம் ஒவ்வொரு கணு வேண்டும் எங்கள் இரும தேடல் மரத்தின் 2 குழந்தைகள் வேண்டும். இந்த வழியில், புகுத்தியது, நீக்கல் மற்றும் தேடல் , மோசமான நிலையில், O (log n) நேரம் எடுக்கும். முன் இருந்து மரம், இன்னும் சீரான இருக்க முடியும் இந்த மாதிரி. இப்போது, எந்த மதிப்பு தேடும் 3 படிகள், அதிகபட்சம், எடுக்கிறது. இந்த மரம், சமச்சீர் உள்ளது என்று பொருள் குறைந்த பட்ச ஆழம் உள்ளது முனைகளில் எண்ணிக்கையை ஒப்பிடும்போது. 

ஒரு சீரான இரும தேடல் மரம் ஒரு மதிப்பு திருமணம் செய்ய ஒரு வரிசைப்படுத்தப்பட்ட வரிசையில் இரும தேடல் போல. உண்மையில், நாம் பொருட்களை சேர்க்க அல்லது நீக்க வேண்டும் என்றால், அவர்கள் அதே வழியில் நடந்து. எனினும், ஒரு மரம் அமைப்பு நல்லது கையாளுதல் புகுத்தல் மற்றும் நீக்கங்கள் இடம் 

என் பெயர் Bannus வான் டெர் Kloot உள்ளது. இந்த CS50 உள்ளது.