1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [இரும தேடல்]

2
00:00:02,000 --> 00:00:04,000
[பேட்ரிக் ஷ்சூமிட்டின் - ஹார்வர்ட் பல்கலைக்கழகம்]

3
00:00:04,000 --> 00:00:07,000
[இந்த CS50 உள்ளது. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
>> நான் அகரவரிசையில் நீங்கள் டிஸ்னி பாத்திரங்களின் பெயர்கள் பட்டியலை கொடுத்தார் என்றால்

5
00:00:09,000 --> 00:00:11,000
மேலும், மிக்கி மவுஸ் கண்டுபிடிக்க நீங்கள் கேட்டு

6
00:00:11,000 --> 00:00:13,000
எப்படி இதை பற்றி போக முடியும்?

7
00:00:13,000 --> 00:00:15,000
ஒரு தெளிவான வழி தொடக்கத்தில் இருந்து பட்டியல் ஸ்கேன் செய்ய வேண்டும்

8
00:00:15,000 --> 00:00:18,000
அது மிக்கி என்று பார்க்க ஒவ்வொரு பெயரை சரிபார்க்கவும்.

9
00:00:18,000 --> 00:00:22,000
ஆனால் நீ அடிக்கடி அலாதீன், ஆலிஸ், ஏரியல், வாசிக்க மற்றும்,

10
00:00:22,000 --> 00:00:25,000
நீங்கள் விரைவில் பட்டியல் முன் தொடங்கி ஒரு நல்ல யோசனை அல்ல என்று புரியும்.

11
00:00:25,000 --> 00:00:29,000
சரி, ஒருவேளை நீங்கள் பட்டியலை முடிவில் இருந்து பின்னோக்கி வேலை தொடங்க வேண்டும்.

12
00:00:29,000 --> 00:00:33,000
இப்போது நீங்கள் டார்சன் கோஸ் டு, தைத்து, ஸ்னோ ஒயிட், மற்றும் நான்காவது வாசிக்க.

13
00:00:33,000 --> 00:00:36,000
இன்னும், இது பற்றி செல்ல சிறந்த வழி போல் தெரியவில்லை.

14
00:00:36,000 --> 00:00:38,000
>> நன்றாக, நீங்கள் இதை பற்றி செல்ல முடியும் என்று மற்றொரு வழி அதிகரிக்கவும் முயற்சி ஆகும்

15
00:00:38,000 --> 00:00:41,000
நீங்கள் பார்க்க வேண்டும் என்று பெயர்கள்.

16
00:00:41,000 --> 00:00:43,000
நீங்கள் அவர்கள் அகரவரிசையில் என்று பின்னர்,

17
00:00:43,000 --> 00:00:45,000
நீங்கள் பட்டியல் மத்தியில் பெயர்கள் பார்க்க முடியும்

18
00:00:45,000 --> 00:00:49,000
மிக்கி மவுஸ் இந்த பெயரை முன் அல்லது பின் என்று பாருங்கள்.

19
00:00:49,000 --> 00:00:51,000
இரண்டாவது நிரலை கடந்த பெயரை பார்த்தால்

20
00:00:51,000 --> 00:00:54,000
நீங்கள், அந்த மிக்கி எம் ஜாஸ்மின் ஒரு ஜே பின்னர் வரும் உணர விரும்புகிறேன்

21
00:00:54,000 --> 00:00:57,000
எனவே வெறுமனே பட்டியலில் முதல் அரை தவிர்க்க விரும்புகிறேன்.

22
00:00:57,000 --> 00:00:59,000
பின்னர் ஒருவேளை நீங்கள் கடந்த பத்தியில் மேல் இருக்கும் என்று

23
00:00:59,000 --> 00:01:02,000
அது Rapunzel தொடங்குகிறது என்று பார்க்க.

24
00:01:02,000 --> 00:01:06,000
மிக்கி Rapunzel முன் வரும்; நாங்கள் அதே கடைசி பத்தியில் தவிர்க்க முடியும் தெரிகிறது.

25
00:01:06,000 --> 00:01:08,000
தேடல் உத்தியை தொடர்ந்து, நீங்கள் விரைவில் காண்பீர்கள் என்று மிக்கி

26
00:01:08,000 --> 00:01:11,000
பெயர்கள் மீதமுள்ள பட்டியலில் முதல் பாதியில் உள்ளது

27
00:01:11,000 --> 00:01:14,000
இறுதியாக மிக்கி மெர்லின் மற்றும் மின்னி இடையே மறைத்து கண்டறிய.

28
00:01:14,000 --> 00:01:17,000
>> நீங்கள் என்ன அடிப்படையில் இரும தேடல் இருந்தது.

29
00:01:17,000 --> 00:01:22,000
இந்த பெயர் குறிப்பிடுவதுபோல், அது ஒரு பைனரி விஷயத்தில் அதன் தேடல் உத்தியை செய்கிறது.

30
00:01:22,000 --> 00:01:24,000
இதற்கு என்ன அர்த்தம்?

31
00:01:24,000 --> 00:01:27,000
நன்றாக, வரிசைப்படுத்தப்பட்ட பட்டியல் கொடுக்கப்பட்ட, பைனரி தேடல் வழிமுறை ஒரு பைனரி முடிவு செய்கிறது -

32
00:01:27,000 --> 00:01:33,000
இடது அல்லது வலது, அதிகமாக அல்லது குறைவாக முன் அல்லது பின் அகர வரிசைப்படி, மேல் - ஒவ்வொரு கட்டத்திலும்.

33
00:01:33,000 --> 00:01:35,000
இப்போது நாம் இந்த தேடல் வழிமுறை இணைந்து செல்லும் ஒரு பெயர் உண்டு என்று,

34
00:01:35,000 --> 00:01:38,000
இது மற்றொரு எடுத்துக்காட்டு பார்த்து விட்டு, ஆனால் இந்த நேரம் வரிசையில் எண்கள் பட்டியல்.

35
00:01:38,000 --> 00:01:43,000
நாம் வரிசைப்படுத்தப்பட்ட எண்கள் இந்த பட்டியலில் எண் 144 தேடுகின்றனர் என்று.

36
00:01:43,000 --> 00:01:46,000
முன்பு போல தான், நாங்கள் நடுத்தர உள்ள எண்ணை கண்டறிய -

37
00:01:46,000 --> 00:01:50,000
இந்த வழக்கில் 13 - மற்றும் 144 க்கும் அதிகமான அல்லது 13 ஐ விட குறைவாக இருந்தால் பார்க்க.

38
00:01:50,000 --> 00:01:54,000
அது 13 க்கும் தெளிவாக அதிக என்பதால், நாம் 13 அல்லது குறைவாக என்று எல்லாம் தவிர்க்க முடியாது

39
00:01:54,000 --> 00:01:57,000
மற்றும் மீதமுள்ள பாதி கவனம்.

40
00:01:57,000 --> 00:01:59,000
நாம் இப்போது விட்டு பொருட்களை கூட எண்ணை, ஏனெனில்

41
00:01:59,000 --> 00:02:01,000
நாம் வெறுமனே நடுத்தர நெருக்கமான ஒரு எண்ணை தேர்வு.

42
00:02:01,000 --> 00:02:03,000
இந்த வழக்கில் நாம் 55 தேர்வு.

43
00:02:03,000 --> 00:02:06,000
நாம் எளிதாக 89 தேர்வு.

44
00:02:06,000 --> 00:02:11,000
சரி. மீண்டும், 144 55 க்கும் அதிகமாக உள்ளது, எனவே சரியான சென்று.

45
00:02:11,000 --> 00:02:14,000
அதிர்ஷ்டவசமாக எங்களுக்கு, அடுத்த நடுத்தர எண், 144 ஆகும்

46
00:02:14,000 --> 00:02:16,000
நாம் தேடும் ஒரு.

47
00:02:16,000 --> 00:02:21,000
ஒரு பைனரி தேடல் பயன்படுத்தி 144 கண்டுபிடிக்க மிகவும் பொருட்டு, நாம் மட்டும் 3 படிகளில் அதை கண்டுபிடிக்க முடிகிறது.

48
00:02:21,000 --> 00:02:24,000
நாம் இங்கே நேரியல் தேடல் பயன்படுத்த வேண்டும் என்றால், அது 12 முயற்சியில்லாமல்.

49
00:02:24,000 --> 00:02:28,000
உண்மையில் ஒரு விஷயத்தை போல, இந்த தேடல் முறை பொருட்களை எண்ணிக்கை பாதிகளுக்கு

50
00:02:28,000 --> 00:02:31,000
ஒவ்வொரு படியிலும் பார்க்க வேண்டும், அது தேடி உருப்படியை கண்டுபிடிக்கும்

51
00:02:31,000 --> 00:02:35,000
பட்டியலில் உருப்படிகளின் எண்ணிக்கையை பதிவு பற்றி உள்ள.

52
00:02:35,000 --> 00:02:37,000
இப்போது நாம் 2 உதாரணங்கள் பார்த்திருக்கிறேன் என்று, தான் பார்த்து விட்டு

53
00:02:37,000 --> 00:02:41,000
இரும தேடல் செயல்படுத்தும் ஒரு சுழல்நிலை செயல்பாடு சில சூடோகுறியீடு.

54
00:02:41,000 --> 00:02:44,000
மேலே தொடங்கி, நாங்கள் 4 வாதங்களை எடுத்து ஒரு செயல்பாட்டை கண்டறிய வேண்டும் என்று பார்க்க:

55
00:02:44,000 --> 00:02:47,000
முக்கிய, வரிசை, நிமிடம், மற்றும் அதிகபட்சம்.

56
00:02:47,000 --> 00:02:51,000
முக்கிய நாம் முந்தைய எடுத்துக்காட்டில் அதனால் 144, தேடுகிறீர்கள் என்று எண்.

57
00:02:51,000 --> 00:02:54,000
வரிசை நாம் தேடும் அந்த எண்களின் பட்டியல்.

58
00:02:54,000 --> 00:02:57,000
Min மற்றும் அதிகபட்சம் குறைந்தபட்ச மற்றும் அதிகபட்ச நிலைகளை குறியீடுகள் உள்ளன

59
00:02:57,000 --> 00:02:59,000
நாம் தற்போது பார்க்கிறாய் என்று.

60
00:02:59,000 --> 00:03:03,000
எனவே தொடங்கலாம் போது, நாள் பூஜ்ஜியமாக இருக்கும் மற்றும் அதிகபட்ச அணியின் அதிகபட்ச அட்டவணை இருக்கும்.

61
00:03:03,000 --> 00:03:07,000
நாம் தேடல் சொற்களை போல், நாம் நாள் மற்றும் அதிகபட்சம் புதுப்பிப்போம்

62
00:03:07,000 --> 00:03:10,000
நாம் இன்னும் உள்ளே இருக்கும் என்று தான் வரம்பில் இருக்க வேண்டும்

63
00:03:10,000 --> 00:03:12,000
>> முதல் சுவாரஸ்யமான பகுதி தவிர்க்கவும் நாம்.

64
00:03:12,000 --> 00:03:14,000
நாம் முதல் விஷயம், இடையில் கண்டறிய உள்ளது

65
00:03:14,000 --> 00:03:19,000
பாதியில் நாம் இன்னும் பரிசீலித்து, அந்த அணியின் நாள் மற்றும் அதிகபட்சம் இடையில் என்று குறியீட்டு.

66
00:03:19,000 --> 00:03:22,000
நாம் அது இடையில் இடத்தில் வரிசை மதிப்பு பாருங்கள்

67
00:03:22,000 --> 00:03:25,000
நாம் தேடும் அந்த எண்ணை முக்கிய விட குறைவாக இருந்தால் பார்க்கலாம்.

68
00:03:25,000 --> 00:03:27,000
அந்த இடத்தில் எண்ணை குறைவாக இருந்தால்,

69
00:03:27,000 --> 00:03:31,000
அது முக்கிய நிலையை இடது அனைத்து எண்கள் விட பெரியதாக உள்ளது என்று பொருள்.

70
00:03:31,000 --> 00:03:33,000
எனவே, மீண்டும் இரும தேடல் செயல்பாடு அழைக்க முடியும்

71
00:03:33,000 --> 00:03:36,000
ஆனால் இந்த முறை பாதி வாசிக்க நாள் மற்றும் அதிகபட்சம் அளவுருக்கள் மேம்படுத்தும்

72
00:03:36,000 --> 00:03:40,000
அந்த விட அல்லது நாம் தான் பார்த்து மதிப்பு சமமாக இருக்கும்.

73
00:03:40,000 --> 00:03:44,000
மறுபுறம், முக்கிய வரிசை தற்போதைய இடையில் உள்ள எண்ணை விட குறைவாக இருந்தால்,

74
00:03:44,000 --> 00:03:47,000
நாம் இடது சென்று அதிக அனைத்து எண்கள் புறக்கணிக்க வேண்டும்.

75
00:03:47,000 --> 00:03:52,000
மீண்டும், நாம் நாள் மற்றும் அதிகபட்சம் புதுப்பித்தார் வரம்பில் இரும தேடல் ஆனால் இந்த முறை அழைப்பு

76
00:03:52,000 --> 00:03:54,000
ஒரு குறைந்த அரை சேர்க்க.

77
00:03:54,000 --> 00:03:57,000
அணியின் தற்போதைய இடையில் உள்ள மதிப்பு இல்லை என்றால்

78
00:03:57,000 --> 00:04:01,000
விட பெரிய அல்லது முக்கிய விட சிறிய, அது முக்கிய சமமாக இருக்க வேண்டும்.

79
00:04:01,000 --> 00:04:05,000
எனவே, நாங்கள் வெறுமனே தற்போதைய இடையில் குறியீட்டு திரும்ப முடியும், மற்றும் நாம் முடித்துவிட்டீர்கள்.

80
00:04:05,000 --> 00:04:09,000
இறுதியாக, இங்கே இந்த காசோலை வழக்கு என்று பல

81
00:04:09,000 --> 00:04:11,000
நாம் தேடும் எண்கள் வரிசையில் உண்மையில் இல்லை.

82
00:04:11,000 --> 00:04:14,000
நாம் தேடும் அந்த எல்லை அதிகபட்ச அட்டவணை

83
00:04:14,000 --> 00:04:17,000
குறைந்தபட்ச விட எப்போதும் குறைவாகவே உள்ளது, என்று நாம் வெகு தூரம் சென்றுவிட்டேன் என்று பொருள்.

84
00:04:17,000 --> 00:04:20,000
எண் உள்ளீடு வரிசை இல்லை என்பதால், நாம் -1 திரும்ப

85
00:04:20,000 --> 00:04:24,000
எதுவும் குறிப்பிட கண்டுபிடிக்கப்பட்டது.

86
00:04:24,000 --> 00:04:26,000
>> நீங்கள், இந்த வழிமுறையை வேலை செய்ய கவனித்தனர்

87
00:04:26,000 --> 00:04:28,000
எண்களின் பட்டியல் வரிசையில் வேண்டும்.

88
00:04:28,000 --> 00:04:31,000
வேறுவிதமாக கூறினால், நாம் மட்டும் இரும தேடல் பயன்படுத்தி 144 காணலாம்

89
00:04:31,000 --> 00:04:34,000
அனைத்து எண்கள் குறைந்த இருந்து அதிக உத்தரவிட்டார் இருந்தால்.

90
00:04:34,000 --> 00:04:38,000
இந்த வழக்கில் இல்லை என்றால், நாம் ஒவ்வொரு படியிலும் எண்கள் பாதி தவிர்க்க முடியாது.

91
00:04:38,000 --> 00:04:40,000
எனவே 2 தேர்வுகள் உண்டு.

92
00:04:40,000 --> 00:04:43,000
ஒன்று நாம், பைனரி தேடல் பயன்படுத்தி முன் ஒரு வரிசையாக்கம் செய்யப்படாத பட்டியல் எடுத்து அடுக்க முடியும்

93
00:04:43,000 --> 00:04:48,000
அல்லது நாம் அது எண்கள் சேர்க்க என எண்களின் பட்டியல் வரிசைப்படுத்தப்பட்டுள்ளது என்று உறுதி செய்யலாம்.

94
00:04:48,000 --> 00:04:50,000
எனவே, அதற்கு பதிலாக நாம் தேட வேண்டும் வெறும் போது வரிசையாக்கம்,

95
00:04:50,000 --> 00:04:53,000
ஏன் எல்லா நேரங்களிலும் வரிசைப்படுத்தப்பட்ட பட்டியலை வைத்து?

96
00:04:53,000 --> 00:04:57,000
>> ஒரே நேரத்தில் அனுமதிக்கும் போது எண்கள் பட்டியல் வைக்க ஒரு வழி வரிசைப்படுத்தப்பட்ட

97
00:04:57,000 --> 00:04:59,000
இந்த பட்டியலில் இருந்து எண்கள் சேர்க்க அல்லது நகர்த்த

98
00:04:59,000 --> 00:05:02,000
ஒரு பைனரி தேடல் மரம் எனப்படும் ஒன்றை பயன்படுத்தி வருகிறது.

99
00:05:02,000 --> 00:05:05,000
ஒரு பைனரி தேடல் மரம் 3 சொத்துக்களின் தகவல்களை வைத்துள்ளார் என்று ஒரு தரவு கட்டமைப்பு உள்ளது.

100
00:05:05,000 --> 00:05:09,000
முதல், எந்த முனை இடது உபப்படிநிலையின் விட குறைவாக மட்டுமே மதிப்புகள் கொண்டுள்ளது

101
00:05:09,000 --> 00:05:11,000
அல்லது கணு மதிப்பு சமமாக.

102
00:05:11,000 --> 00:05:15,000
இரண்டாவது, ஒரு முனை வலது உபப்படிநிலையின் மட்டும் அதிகமாக இருக்கும் என்று மதிப்புகள் கொண்டுள்ளது

103
00:05:15,000 --> 00:05:17,000
அல்லது கணு மதிப்பு சமமாக.

104
00:05:17,000 --> 00:05:20,000
அனைத்து கணுக்களின் மற்றும், இறுதியாக, இடது மற்றும் வலது subtrees இரு

105
00:05:20,000 --> 00:05:23,000
மேலும் இரும தேடல் மரங்கள்.

106
00:05:23,000 --> 00:05:26,000
நாம் முன்னர் பயன்படுத்திய அதே எண்கள் ஒரு உதாரணம் பாருங்கள் நாம்.

107
00:05:26,000 --> 00:05:30,000
ஒரு கணினி அறிவியல் மரம் முன் பார்த்ததில்லை என்று நீங்கள் அந்த,

108
00:05:30,000 --> 00:05:34,000
என்னை ஒரு கணினி அறிவியல் மரம் கீழ்நோக்கி வளரும் என்று கூறி ஆரம்பிக்கலாம்.

109
00:05:34,000 --> 00:05:36,000
ஆமாம், நீங்கள் தயார்படுத்தப்படுகிறார்கள் மரங்கள் போல்,

110
00:05:36,000 --> 00:05:38,000
ஒரு கணினி அறிவியல் மரத்தின் வேர், மேல் உள்ளது

111
00:05:38,000 --> 00:05:41,000
மற்றும் இலைகள் கீழே இருக்கும்.

112
00:05:41,000 --> 00:05:45,000
ஒவ்வொரு சிறிய பெட்டியில் ஒரு முனை என அழைக்கப்படும், மற்றும் முனைகளில் முனைகளை ஒவ்வொரு மற்ற இணைக்கப்பட்டுள்ளது.

113
00:05:45,000 --> 00:05:48,000
இந்த மரத்தின் வேர், மதிப்பு 13 ஒரு முனை மதிப்பு

114
00:05:48,000 --> 00:05:52,000
இது மதிப்புகள் 5 மற்றும் 34 2 குழந்தைகள் முனைகளில் உள்ளது.

115
00:05:52,000 --> 00:05:57,000
ஒரு உபப்படிநிலையின் தான் முழு மரம் ஒரு துணைப்பிரிவில் பார்த்து உருவாக்கப்பட்டது என்று மரம்.

116
00:05:57,000 --> 00:06:03,000
>> எடுத்துக்காட்டாக, முனை 3 இடது உபப்படிநிலையின் முனைகளில் 0, 1, 2 விவரங்களை மரம்.

117
00:06:03,000 --> 00:06:06,000
எனவே, நாம் ஒரு பைனரி தேடல் மரம் பண்புகள் திரும்பி சென்றால்,

118
00:06:06,000 --> 00:06:09,000
நாம், மரம் ஒவ்வொரு கணு அதாவது அனைத்து 3 பண்புகள், ரத்து போகிறது என்று பார்க்க

119
00:06:09,000 --> 00:06:15,000
இடது உபப்படிநிலையின் மட்டுமே குறைவாக அல்லது கணு மதிப்பு சமமாக இருக்கும் மதிப்புகள் கொண்டுள்ளது;

120
00:06:15,000 --> 00:06:16,000
அனைத்து முனைகளில் வலது உபப்படிநிலையின்

121
00:06:16,000 --> 00:06:19,000
மட்டுமே அதிகமாக அல்லது கணு மதிப்பு சமமாக இருக்கும் மதிப்புகள் கொண்டுள்ளது; மற்றும்

122
00:06:19,000 --> 00:06:25,000
அனைத்து முனைகளில் இடது மற்றும் வலது இரண்டு subtrees மேலும் இரும தேடல் மரங்கள்.

123
00:06:25,000 --> 00:06:28,000
இந்த மரம் வித்தியாசமாக தெரிகிறது எனினும், இந்த சரியான பைனரி தேடல் மரம்

124
00:06:28,000 --> 00:06:30,000
எண்கள் ஒரே செட்.

125
00:06:30,000 --> 00:06:32,000
உண்மையில் ஒரு விஷயத்தை, நீங்கள் உருவாக்க முடியும் என்று பல வழிகளிலும் உள்ளன

126
00:06:32,000 --> 00:06:35,000
இந்த எண்கள் இருந்து சரியான பைனரி தேடல் மரம்.

127
00:06:35,000 --> 00:06:38,000
சரி, நாம் உருவாக்கிய முதல் மீண்டும் செல்லலாம்.

128
00:06:38,000 --> 00:06:40,000
எனவே நாம் இந்த மரங்கள் என்ன செய்ய முடியும்?

129
00:06:40,000 --> 00:06:44,000
சரி, நாம் மிக எளிதாக குறைந்த பட்ச மற்றும் அதிகபட்ச மதிப்புகள் காணலாம்.

130
00:06:44,000 --> 00:06:46,000
குறைந்தபட்ச மதிப்புகள் எப்போதும் இடது செல்வதன் மூலம் காணலாம்

131
00:06:46,000 --> 00:06:48,000
பார்க்க இன்னும் முனைகள் உள்ளன வரை.

132
00:06:48,000 --> 00:06:53,000
மாறாக, அதிகபட்ச ஒரு தேட தான் ஒவ்வொரு நேரத்தில் சரியான கீழே செல்லும்.

133
00:06:54,000 --> 00:06:56,000
>> வேறு எந்த கண்டுபிடித்து குறைந்தபட்ச அல்லது அதிகபட்ச என்று

134
00:06:56,000 --> 00:06:58,000
தான் எளிது.

135
00:06:58,000 --> 00:07:00,000
நாம் எண் 89 தேடுகிறீர்கள் என்று.

136
00:07:00,000 --> 00:07:03,000
நாம் சாதாரணமாக, ஒவ்வொரு கணு மதிப்பு சரிபார்த்து இடது அல்லது வலது சென்று

137
00:07:03,000 --> 00:07:06,000
கணு மதிப்பு குறைவாக அல்லது அதிகமாக உள்ளது என்பதை பொறுத்து

138
00:07:06,000 --> 00:07:08,000
நாம் தேடும் ஒரு.

139
00:07:08,000 --> 00:07:11,000
எனவே, 13 வேர் தொடங்கி, நாம், 89 அதிகம் என்று பார்க்க

140
00:07:11,000 --> 00:07:13,000
அதனால் நாம் சரியான சென்று.

141
00:07:13,000 --> 00:07:16,000
நாம் 34 க்கு முனை பார்க்க, மீண்டும் நாம் சரியான சென்று.

142
00:07:16,000 --> 00:07:20,000
89 இன்னும் 55 விட அதிகமாக உள்ளது, எனவே சரியான போகிறேன் தொடர்ந்து.

143
00:07:20,000 --> 00:07:24,000
நாம் 144 மதிப்பு கொண்ட ஒரு முனை வரை வந்து இடது சென்று.

144
00:07:24,000 --> 00:07:26,000
லோ மற்றும் இதோ, 89 உரிமை உள்ளது.

145
00:07:26,000 --> 00:07:31,000
>> நாம் என்ன செய்ய முடியும் என்று மற்றொரு விஷயம் ஒரு inorder பயணித்தல் மூலம் அனைத்து எண்கள் அவுட் அச்சிட உள்ளது.

146
00:07:31,000 --> 00:07:35,000
ஒரு inorder பயணித்தல் இடது உபப்படிநிலையின் எல்லாம் வெளியே அச்சிட பொருள்

147
00:07:35,000 --> 00:07:37,000
கணு தன்னை அச்சிடும் தொடர்ந்து

148
00:07:37,000 --> 00:07:40,000
பின்னர் வலது உபப்படிநிலையின் எல்லாம் அச்சிடுகிறது தொடர்ந்து.

149
00:07:40,000 --> 00:07:43,000
உதாரணமாக, நாம் பிடித்த இரும தேடல் மரம் எடுத்து விடுங்கள்

150
00:07:43,000 --> 00:07:46,000
மற்றும் வரிசைப்படுத்தப்பட்ட வரிசையில் எண்கள் அவுட் அச்சிட.

151
00:07:46,000 --> 00:07:49,000
நாங்கள் 13 ரூட் துவங்க, ஆனால் அச்சிடும் 13 முன்னர் நாம் வெளியே அச்சிட வேண்டும்

152
00:07:49,000 --> 00:07:51,000
இடது உபப்படிநிலையின் எல்லாம்.

153
00:07:51,000 --> 00:07:55,000
எனவே 5 சென்று. நாம் இன்னும், நாம் இடது மிகவும் முனை வரும் வரை மரத்தில் ஆழ்ந்த கீழே போக வேண்டும்

154
00:07:55,000 --> 00:07:57,000
இது பூஜ்ஜியம்.

155
00:07:57,000 --> 00:08:00,000
அச்சிடும் பூஜ்யம் பிறகு, நாம் 1 திரும்பி சென்று அந்த அச்சிட.

156
00:08:00,000 --> 00:08:03,000
நாம் 2 இது, சரியான உபப்படிநிலையின் சென்று, அந்த அவுட் அச்சிட.

157
00:08:03,000 --> 00:08:05,000
இப்போது நாம், அந்த உபப்படிநிலையின் முடித்துவிட்டீர்கள்

158
00:08:05,000 --> 00:08:07,000
நாங்கள் 3 மீண்டும் எழுந்து சென்று அச்சிட முடியாது.

159
00:08:07,000 --> 00:08:11,000
வரை மீண்டும் தொடரும், நாங்கள் 8 பின்னர் 5 அச்சிட்டு.

160
00:08:11,000 --> 00:08:13,000
இப்போது நாம் முழு நிறைவு என்று, உபப்படிநிலையின் விட்டு

161
00:08:13,000 --> 00:08:17,000
நாங்கள் 13 அச்சிட மற்றும் வலது உபப்படிநிலையின் வேலை செய்ய.

162
00:08:17,000 --> 00:08:21,000
நாங்கள் 34 கீழே ஹாப், ஆனால் அச்சிடும் 34 முன்னர் நாம் அதன் இடது உபப்படிநிலையின் அவுட் அச்சிட வேண்டும்.

163
00:08:21,000 --> 00:08:27,000
எனவே 21 அவுட் அச்சிட; நாம் 34 அவுட் அச்சிட மற்றும் அதன் வலது உபப்படிநிலையின் பார்க்க கிடைக்கும்.

164
00:08:27,000 --> 00:08:31,000
55 எந்த இடது உபப்படிநிலையின் ஏனெனில், நாம் அதை அச்சிட்டு, அதன் வலது உபப்படிநிலையின் மீது தொடர்ந்து.

165
00:08:31,000 --> 00:08:36,000
144 ஒரு இடது உபப்படிநிலையின் உள்ளது, எனவே நாம், 144 தொடர்ந்து, 89 அவுட் அச்சிட

166
00:08:36,000 --> 00:08:39,000
233 மற்றும் இறுதியாக வலது மிக முனை.

167
00:08:39,000 --> 00:08:44,000
அங்கு நீங்கள் இது; அனைத்து எண்கள் குறைந்த இருந்து அதிக பொருட்டு வெளியே அச்சிடப்படுகிறது.

168
00:08:44,000 --> 00:08:47,000
>> மரம் ஒன்று சேர்த்தல் மற்றும் ஒப்பீட்டளவில் வலியற்றது.

169
00:08:47,000 --> 00:08:51,000
நாம் செய்ய வேண்டியது எல்லாம் நாங்கள் 3 இரும தேடல் மரம் பண்புகளை பின்பற்ற என்பதையும் உறுதி

170
00:08:51,000 --> 00:08:53,000
விண்வெளி, அங்கு பின்னர் மதிப்பை செருக.

171
00:08:53,000 --> 00:08:55,000
நாம் 7 மதிப்பை செருக வேண்டும் என்று.

172
00:08:55,000 --> 00:08:58,000
7 குறைவாக 13 என்பதால், நாம் இடது சென்று.

173
00:08:58,000 --> 00:09:01,000
ஆனால் அது 5 விட, நாம் சரியான நடந்தே செல்கிறார்கள்.

174
00:09:01,000 --> 00:09:04,000
இது 8 மற்றும் 8 ஒரு இலை கணு என்பது குறைவான என்பதால், நாம் 8 இடது குழந்தை 7 சேர்க்க.

175
00:09:04,000 --> 00:09:09,000
Voila! நாம் தேடும் ரும மரத்தை ஒரு எண்ணை சேர்க்க.

176
00:09:09,000 --> 00:09:12,000
>> நாம் விஷயங்களை சேர்க்க முடியும் என்றால், நாங்கள் நல்ல நல்ல விஷயங்களை நீக்க முடியும்.

177
00:09:12,000 --> 00:09:14,000
துரதிருஷ்டவசமாக எங்களுக்கு, நீக்குதல் சற்று சிக்கலான இல்லை -

178
00:09:14,000 --> 00:09:16,000
மிக, ஆனால் ஒரு சிறிய பிட் இல்லை.

179
00:09:16,000 --> 00:09:18,000
நாம் கருத்தில் கொள்ள வேண்டும் என்று 3 வெவ்வேறு சூழல்களில் உள்ளன

180
00:09:18,000 --> 00:09:21,000
இரும தேடல் மரங்கள் கூறுகளை நீக்குவதற்கு போது.

181
00:09:21,000 --> 00:09:24,000
முதல், எளிதான வழக்கு உறுப்பு ஒரு இலை முனை உள்ளது.

182
00:09:24,000 --> 00:09:27,000
இந்த வழக்கில், நாம் வெறுமனே அதை நீக்க எங்கள் வணிக உடன் சென்று.

183
00:09:27,000 --> 00:09:30,000
நாம் தான் சேர்க்க வேண்டும் என்று 7 நீக்க வேண்டும் என்று.

184
00:09:30,000 --> 00:09:34,000
சரி, நாம் வெறுமனே அதை கண்டு, அதை நீக்க, அவ்வளவு தான்.

185
00:09:35,000 --> 00:09:37,000
முனை மட்டுமே 1 குழந்தை இருந்தால் அடுத்த விஷயம்.

186
00:09:37,000 --> 00:09:40,000
இங்கே நாம் முனை நீக்க முடியும், ஆனால் நாம் முதலில் உறுதி செய்ய வேண்டும்

187
00:09:40,000 --> 00:09:42,000
இப்போது பெற்றோர் விட்டு என்று உபப்படிநிலையின் இணைக்க

188
00:09:42,000 --> 00:09:44,000
கணு மூல நாம் மட்டும் நீக்கப்பட்டது.

189
00:09:44,000 --> 00:09:47,000
நாம் நம் மரத்தில் இருந்து 3 நீக்க வேண்டும் என்று.

190
00:09:47,000 --> 00:09:50,000
நாம் அந்த முனை குழந்தை உறுப்பு எடுத்து கணு மூல இணைக்கவும்.

191
00:09:50,000 --> 00:09:54,000
இந்த வழக்கில், நாம் இப்போது 5 1 இணைக்கிறேன்.

192
00:09:54,000 --> 00:09:57,000
எங்களுக்கு தெரியும் இந்த, பைனரி தேடல் மரம் சொத்து படி, ஒரு பிரச்சனையும் இல்லாமல் வேலை

193
00:09:57,000 --> 00:10:01,000
3 இடது உபப்படிநிலையின் என்று எல்லாவற்றையும் விட குறைவாக 5 இருந்தது.

194
00:10:01,000 --> 00:10:05,000
3 உபப்படிநிலையின் கவனித்துக்கொள்வதே இப்போது, நாம் அதை நீக்க முடியும்.

195
00:10:05,000 --> 00:10:08,000
மூன்றாவது மற்றும் இறுதி வழக்கு மிகவும் சிக்கலாக உள்ளது.

196
00:10:08,000 --> 00:10:11,000
நாங்கள் நீக்க வேண்டும் முனை 2 குழந்தைகள் இருக்கும் போது இந்த வழக்கு.

197
00:10:11,000 --> 00:10:15,000
இதை செய்ய வேண்டும், நாங்கள் முதல், அடுத்த பெரிய மதிப்பு கொண்ட முனை கண்டறிய வேண்டும்

198
00:10:15,000 --> 00:10:18,000
இரண்டு இடமாற்றம், பின்னர் கேள்வி கணு நீக்க.

199
00:10:18,000 --> 00:10:22,000
அடுத்த மிக பெரிய மதிப்பு 2 குழந்தைகள் தன்னை முடியாது என்று முனை அறிவிப்பு

200
00:10:22,000 --> 00:10:26,000
அதன் இடது குழந்தை அடுத்த மிக பெரிய ஒரு நல்ல வேட்பாளர் என்று இருந்து.

201
00:10:26,000 --> 00:10:30,000
எனவே, 2 குழந்தைகளுடன் ஒரு முனை நீக்குதல், 2 கணுக்களின் மாற்ற தொகை

202
00:10:30,000 --> 00:10:33,000
பின்னர் அழிப்பதை 2 மேற்கூறிய விதிகளின் 1 கையாளப்படுகிறது.

203
00:10:33,000 --> 00:10:37,000
உதாரணமாக, நாம் வேர் கணு, 13 நீக்க வேண்டும் என்று.

204
00:10:37,000 --> 00:10:39,000
நாம் முதலில் நாம் கிளையில் அடுத்த பெரிய மதிப்பை கண்டறிய உள்ளது

205
00:10:39,000 --> 00:10:41,000
இதில், இந்த வழக்கில், 21 ஆகும்.

206
00:10:41,000 --> 00:10:46,000
நாம் 13 ஒரு இலை மற்றும் 21 மத்திய குழு முனை செய்து, 2 முனைகளில் பரிமாறிக்கொள்ளலாம்.

207
00:10:46,000 --> 00:10:49,000
இப்போது நாம் வெறுமனே 13 நீக்க முடியும்.

208
00:10:50,000 --> 00:10:53,000
>> முந்தைய மறைமுகமாக, சரியான பைனரி தேடல் மரம் செய்ய பல வழிகள் உள்ளன.

209
00:10:53,000 --> 00:10:56,000
துரதிருஷ்டவசமாக நமக்கு, சில மற்றவர்களை விட மோசமாக உள்ளன.

210
00:10:56,000 --> 00:10:59,000
நாம் ஒரு பைனரி தேடல் மரம் கட்ட போது எடுத்துக்காட்டாக, என்ன நடக்கும்

211
00:10:59,000 --> 00:11:01,000
எண்கள் ஒரு வரிசையில் பட்டியலில் இருந்து?

212
00:11:01,000 --> 00:11:04,000
அனைத்து எண்கள் தான் ஒவ்வொரு படியிலும் வலது சேர்க்கப்படும்.

213
00:11:04,000 --> 00:11:06,000
நாம் ஒரு எண்ணை தேட வேண்டும் போது,

214
00:11:06,000 --> 00:11:08,000
நாம் வேறு வழியில்லை ஆனால் தான் ஒவ்வொரு படியிலும் உரிமை இருக்கும்.

215
00:11:08,000 --> 00:11:11,000
இந்த அனைத்து நேரியல் தேடல் விட முடியாது.

216
00:11:11,000 --> 00:11:13,000
நாம் இங்கே மறைக்க மாட்டேன் எனினும், மிகவும் சிக்கலான, மற்ற உள்ளன

217
00:11:13,000 --> 00:11:16,000
இந்த நடக்காது என்று உறுதி என்று தரவு கட்டமைப்புகள்.

218
00:11:16,000 --> 00:11:18,000
எனினும், இந்த தவிர்க்க முடியும் என்று ஒரு எளிமையான விஷயம்

219
00:11:18,000 --> 00:11:21,000
நான் தோராயமாக குலைப்பதை உள்ளீடு மதிப்புகளுக்கு.

220
00:11:21,000 --> 00:11:26,000
இது சீரற்ற வாய்ப்பு மூலம் எண்களை ஒரு மாற்றி மாற்றி கலக்கப்பட்டு பட்டியலை வரிசையாக்கம் என்று சாத்தியமே இல்லை.

221
00:11:26,000 --> 00:11:29,000
இந்த வழக்கு இருந்தால், கேசினோ நீண்ட வணிக தங்க முடியாது.

222
00:11:29,000 --> 00:11:31,000
>> அங்கு நீங்கள் இது.

223
00:11:31,000 --> 00:11:34,000
நீங்கள் இப்போது இரும தேடல் மற்றும் இரும தேடல் மரங்கள் பற்றி.

224
00:11:34,000 --> 00:11:36,000
நான் பேட்ரிக் ஷ்சூமிட்டின் நான், இந்த CS50 உள்ளது.

225
00:11:36,000 --> 00:11:38,000
[CS50.TV]

226
00:11:38,000 --> 00:11:43,000
ஒரு தெளிவான வழி இருந்து பட்டியல் ஸ்கேன் செய்ய வேண்டும் ... [பீப்]

227
00:11:43,000 --> 00:11:46,000
... உருப்படிகளின் எண்ணிக்கையை ... இங்கும்

228
00:11:46,000 --> 00:11:50,000
[சிரிக்கிறார்]

229
00:11:50,000 --> 00:11:55,000
... 234 ... augh ஒரு முனை பதிவு.

230
00:11:55,000 --> 00:11:58,000
>> ஆஹா! என்று -