1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] நீங்கள் ஒரு கணினி அனைத்து உங்கள் குடும்ப உறுப்பினர்கள் எப்படி பிரதிபலிக்கும்?

2
00:00:10,790 --> 00:00:12,390
நாம் சாதாரணமாக, ஒரு பட்டியலை பயன்படுத்த முடியும்

3
00:00:12,390 --> 00:00:14,400
ஆனால் ஒரு தெளிவான வரிசைக்கு இங்கே இல்லை.

4
00:00:14,400 --> 00:00:17,110
>> நாம் உங்கள் பெரும் பாட்டி, ஆலிஸ் தொடங்கி சொல்கிறீர்கள்.

5
00:00:17,110 --> 00:00:19,030
அவர் 2 மகன்கள், பாப் உள்ளது

6
00:00:19,030 --> 00:00:21,310
உங்கள் தாத்தா, சார்லி.

7
00:00:21,310 --> 00:00:23,190
சார்லி, 3 குழந்தைகள் உள்ளனர்

8
00:00:23,190 --> 00:00:26,730
உங்கள் மாமா, டேவ், உங்கள் அத்தை, ஈவ், உங்கள் தந்தை, பிரெட்.

9
00:00:26,730 --> 00:00:28,750
நீங்கள் பிரெட் ஒரே குழந்தை.

10
00:00:28,750 --> 00:00:30,950
>> ஏன் இந்த வழியில், உங்கள் குடும்ப உறுப்பினர்கள் ஏற்பாடு

11
00:00:30,950 --> 00:00:34,010
எளிய பட்டியல் பிரதிநிதித்துவம் விட வேண்டும்?

12
00:00:34,010 --> 00:00:36,630
ஒரு காரணம் என்று இந்த படிநிலை கட்டமைப்பானது,

13
00:00:36,630 --> 00:00:39,660
ஒரு எனப்படும் 'மரம்,' ஒரு எளிய பட்டியல் விட தகவல்களை கொண்டுள்ளது.

14
00:00:40,540 --> 00:00:43,520
நாம் அனைவரும் இடையே குடும்ப உறவுகள் தெரியும்

15
00:00:43,520 --> 00:00:45,440
ஒரு மரம் ஆய்வு மூலம்.

16
00:00:45,440 --> 00:00:47,250
மேலும், அது வேகமாக முடியாது

17
00:00:47,250 --> 00:00:50,010
ஆனால் அப் நேரம் எனலாம், மரம் தரவு வரிசையாக்கம் என்றால்.

18
00:00:50,010 --> 00:00:53,850
>> நாம் இங்கே அந்த பயன்படுத்தி கொள்ள முடியாது, ஆனால் நாங்கள் விரைவில் இந்த ஒரு உதாரணம் பார்க்கலாம்.

19
00:00:53,850 --> 00:00:56,150
ஒருவர் மரத்தில் ஒரு முனை குறிப்பிடப்படுகின்றன.

20
00:00:56,680 --> 00:00:58,370
முனைகளில் குழந்தை முனைகளில் முடியும்

21
00:00:58,370 --> 00:01:00,350
அத்துடன் ஒரு தாய் முனை போன்ற.

22
00:01:00,350 --> 00:01:02,390
இந்த, தொழில்நுட்ப சொற்கள் உள்ளன

23
00:01:02,390 --> 00:01:05,220
குடும்பங்கள் தவிர விஷயங்கள் மரங்கள் பயன்படுத்தி கூட.

24
00:01:05,220 --> 00:01:07,940
ஆலிஸ் இன் முனை, 2 குழந்தைகள் மற்றும் பெற்றோர் உள்ளது

25
00:01:07,940 --> 00:01:11,500
சார்லியின் முனை 3 குழந்தைகள் மற்றும் 1 பெற்றோர் உள்ளன.

26
00:01:11,500 --> 00:01:14,330
>> ஒரு இலை கணு எந்த குழந்தைகள் இல்லை என்று ஒரு

27
00:01:14,330 --> 00:01:16,410
மரம் வெளியே விளிம்பில்.

28
00:01:16,410 --> 00:01:18,520
மரத்தின் மிக உயர்ந்த முனை, வேர் கணு,

29
00:01:18,520 --> 00:01:20,240
எந்த பெற்றோர் உள்ளது.

30
00:01:20,240 --> 00:01:23,170
>> ஒரு பைனரி மரம், மரத்தின் ஒரு குறிப்பிட்ட வகை

31
00:01:23,170 --> 00:01:26,720
இதில் ஒவ்வொரு கணு, அதிகபட்சம், 2 குழந்தைகள் உள்ளன.

32
00:01:26,720 --> 00:01:30,490
இங்கே சி ஒரு பைனரி மரம் ஒரு முனையத்தின் struct உள்ளது

33
00:01:31,560 --> 00:01:34,530
ஒவ்வொரு முனையும் அது தொடர்புடைய சில தரவு

34
00:01:34,530 --> 00:01:36,520
மற்ற முனைகள் மற்றும் 2 சுட்டிகள்.

35
00:01:36,520 --> 00:01:38,110
>> எங்கள் குடும்பம் மரம்,

36
00:01:38,110 --> 00:01:40,900
தொடர்புடைய தரவு ஒவ்வொரு நபரின் பெயர் இருந்தது.

37
00:01:40,900 --> 00:01:43,850
இது ஒன்றும் இருக்க முடியும் என்று இங்கே அது ஒரு முழு எண்ணாக இருக்கிறது.

38
00:01:44,510 --> 00:01:46,200
அதை திருப்பி என,

39
00:01:46,200 --> 00:01:48,990
ஒரு பைனரி மரம், ஒரு குடும்பத்தில் ஒரு நல்ல பிரதிநிதித்துவம் இருக்க மாட்டேன்

40
00:01:48,990 --> 00:01:51,960
மக்கள் அடிக்கடி மேற்பட்ட 2 குழந்தைகள் நடத்திவருகிறோம்.

41
00:01:51,960 --> 00:01:53,510
>> ஒரு பைனரி தேடல் மரம்

42
00:01:53,510 --> 00:01:56,380
பைனரி மரம் ஒரு சிறப்பு, உத்தரவின் வகை

43
00:01:56,380 --> 00:01:58,090
என்று நம்மை விரைவில் மதிப்புகள் பார்க்க அனுமதிக்கிறது.

44
00:01:58,740 --> 00:02:00,050
நீங்கள் கவனித்தீர்களா

45
00:02:00,050 --> 00:02:02,010
ஒரு மரத்தின் வேர் கீழே ஒவ்வொரு கணு

46
00:02:02,010 --> 00:02:04,620
மற்றொரு மரத்தின் வேர், ஒரு 'உபப்படிநிலையின்.' என்று அழைக்கப்படுகிறது

47
00:02:04,960 --> 00:02:07,090
இங்கே, மரத்தின் வேர், 6

48
00:02:07,090 --> 00:02:09,860
அதன் குழந்தை, 2, உபப்படிநிலையின் வேர்.

49
00:02:09,860 --> 00:02:11,870
>> ஒரு பைனரி தேடல் கிளையில்

50
00:02:11,870 --> 00:02:15,790
ஒரு முனை அனைத்து மதிப்புகள் சரியான உபப்படிநிலையின் தான்

51
00:02:15,790 --> 00:02:18,690
கணு மதிப்பு அதிகமாக இருக்கும். இங்கே: 6.

52
00:02:18,690 --> 00:02:22,640
சரி, ஒரு முனை இடது உபப்படிநிலையின் மதிப்புகள்

53
00:02:24,540 --> 00:02:26,890
கணு மதிப்பு குறைவாக இருக்கும்.

54
00:02:26,890 --> 00:02:28,620
நாங்கள் போலி மதிப்புகள் கையாள வேண்டும் என்றால்,

55
00:02:28,620 --> 00:02:31,760
நாம், ஒரு தளர்வான சமத்துவமின்மை வேண்டும் அல்லது அந்த மாற்றலாம்

56
00:02:31,760 --> 00:02:34,410
ஒரே மதிப்புகள் இடது அல்லது வலது அல்லது கீழ் அதாவது,

57
00:02:34,410 --> 00:02:37,400
நீண்ட நாம் முழுவதும் இது பற்றி உறுதியான உள்ளன.

58
00:02:37,400 --> 00:02:39,620
இந்த மரம் ஒரு பைனரி தேடல் மரம்

59
00:02:39,620 --> 00:02:41,540
இந்த விதிகள் பின்வருமாறு காரணம்.

60
00:02:42,320 --> 00:02:46,020
>> இந்த நாங்கள் சி structs அனைத்து முனைகளில் திரும்பி அது இருக்கும் என்று எப்படி இருக்கும்.

61
00:02:46,880 --> 00:02:48,410
கவனிக்க ஒரு குழந்தை இல்லை என்றால்,

62
00:02:48,410 --> 00:02:50,340
சுட்டிக்காட்டி பூஜ்ய உள்ளது.

63
00:02:50,340 --> 00:02:53,270
எப்படி நாம் 7 மரம் இருக்கிறது என்று பார்?

64
00:02:53,270 --> 00:02:55,020
நாம் ரூட் துவங்க.

65
00:02:55,020 --> 00:02:58,690
அது மரம் என்றால் ஏழு 6 அதிகமாக உள்ளது, எனவே, அதை சரி செய்ய வேண்டும்.

66
00:02:59,680 --> 00:03:03,650
பின்னர், அது 8 விட குறைவாக இருக்கும், அதனால் அதை விட்டு வேண்டும்.

67
00:03:03,650 --> 00:03:06,210
இங்கே, நாங்கள் 7 கிடைத்தது.

68
00:03:06,210 --> 00:03:08,160
இப்போது, நாங்கள் 5 பார்க்கிறேன்.

69
00:03:08,160 --> 00:03:11,500
ஐந்து 6 குறைவாக உள்ளது, எனவே அது இடது இருக்க வேண்டும்.

70
00:03:11,500 --> 00:03:13,460
ஐந்து, 2 விட அதிகமாக இருக்கும்

71
00:03:13,460 --> 00:03:15,010
அதனால், சரியான இருக்க வேண்டும்

72
00:03:15,010 --> 00:03:18,100
மேலும் 4 விட, அதை சரி மீண்டும் இருக்க வேண்டும்.

73
00:03:18,100 --> 00:03:20,300
ஆனால், எந்த குழந்தை இங்கே இருக்கிறது.

74
00:03:20,300 --> 00:03:22,000
சுட்டிக்காட்டி பூஜ்ய உள்ளது.

75
00:03:22,000 --> 00:03:24,270
இந்த 5 எங்கள் மரம் இல்லை என்று அர்த்தம்.

76
00:03:24,270 --> 00:03:27,250
>> நாம் பின்வரும் குறியீடு இரும மரம் தேடலாம்:

77
00:03:28,430 --> 00:03:31,140
ஒவ்வொரு முனையும் போது, நாம் காண வேண்டும் என்பதை பார்க்கவும்

78
00:03:31,140 --> 00:03:33,020
நாம் தேடும் மதிப்பு.

79
00:03:33,020 --> 00:03:35,740
நாம் அது கிடைக்கவில்லை என்றால் அது இருக்க வேண்டும் என்றால், நாம் தீர்மானிக்க

80
00:03:35,740 --> 00:03:38,990
இடது அல்லது வலது மற்றும் அந்த உபப்படிநிலையின் சரிபார்க்கவும்.

81
00:03:38,990 --> 00:03:41,160
இந்த வட்டத்திற்கு மரம் கீழே வரும்

82
00:03:41,160 --> 00:03:44,190
இடது அல்லது வலது அல்லது எந்த குழந்தை முனை உள்ளது வரை.

83
00:03:45,190 --> 00:03:48,600
>> 5 மரம் இல்லை என்பதை நினைவில் கொள்ளுங்கள்.

84
00:03:48,600 --> 00:03:50,460
எப்படி நாம் அதை செருகுவது?

85
00:03:50,460 --> 00:03:52,370
செயல்முறை தேட போன்ற தோற்றம்.

86
00:03:52,370 --> 00:03:54,830
நாம், 6 இருந்து தொடங்கி மரம் கீழே கூறு

87
00:03:54,830 --> 00:03:57,040
2 விட்டு,

88
00:03:57,040 --> 00:03:59,140
4 உரிமை,

89
00:03:59,140 --> 00:04:02,500
வலது மீண்டும், ஆனால் 4 இந்த பக்கத்தில் எந்த குழந்தையும் உள்ளது.

90
00:04:02,500 --> 00:04:06,090
இந்த, 5 புதிய நிலை இருக்கும்

91
00:04:06,090 --> 00:04:08,500
அது எந்த குழந்தைகள் ஆரம்பிக்கும்.

92
00:04:09,020 --> 00:04:12,220
>> எப்படி வேகமாக ஒரு பைனரி தேடல் மரத்தில் நடவடிக்கைகள் என்ன?

93
00:04:12,220 --> 00:04:15,410
Bigohnotation ஒரு மேல் வரம்பையே வழங்க முயற்சிக்கின்றது என்பதை நினைவில் கொள்ளுங்கள்.

94
00:04:15,410 --> 00:04:17,390
மோசமான நிலையில்,

95
00:04:17,390 --> 00:04:19,480
எங்கள் மரம் வெறுமனே ஒரு இணைக்கப்பட்ட பட்டியலில் இருக்க முடியும்

96
00:04:19,480 --> 00:04:22,220
அந்த உட்புகுத்தல், நீக்குதல், மற்றும் தேடல் பொருள்

97
00:04:22,220 --> 00:04:25,380
மரம் முனைகளுக்கிடையே எண்ணிக்கை விகிதாசார நேரம் ஆகலாம்.

98
00:04:25,380 --> 00:04:27,380
இந்த ஓ (n) ஆகும்.

99
00:04:27,380 --> 00:04:30,690
>> எடுத்துக்காட்டாக, பின்வரும் சரியான பைனரி தேடல் மரம்.

100
00:04:31,850 --> 00:04:34,020
எனினும், நாம் 9 கண்டுபிடிக்க முயற்சி என்றால்,

101
00:04:34,020 --> 00:04:36,760
நாம் ஒவ்வொரு கணு தொடரவேண்டும்.

102
00:04:36,760 --> 00:04:39,120
இது ஒரு இணைக்கப்பட்ட பட்டியலில் விட சிறந்தது.

103
00:04:39,120 --> 00:04:41,410
வெறுமனே, நாம் ஒவ்வொரு கணு வேண்டும்

104
00:04:41,410 --> 00:04:44,120
எங்கள் இரும தேடல் மரத்தின் 2 குழந்தைகள் வேண்டும்.

105
00:04:44,120 --> 00:04:46,370
இந்த வழியில், புகுத்தியது, நீக்கல் மற்றும் தேடல்

106
00:04:46,370 --> 00:04:50,190
, மோசமான நிலையில், O (log n) நேரம் எடுக்கும்.

107
00:04:50,190 --> 00:04:52,470
முன் இருந்து மரம், இன்னும் சீரான இருக்க முடியும்

108
00:04:52,470 --> 00:04:54,140
இந்த மாதிரி.

109
00:04:54,140 --> 00:04:57,980
இப்போது, எந்த மதிப்பு தேடும் 3 படிகள், அதிகபட்சம், எடுக்கிறது.

110
00:04:57,980 --> 00:04:59,460
இந்த மரம், சமச்சீர் உள்ளது

111
00:04:59,460 --> 00:05:01,190
என்று பொருள் குறைந்த பட்ச ஆழம் உள்ளது

112
00:05:01,190 --> 00:05:03,680
முனைகளில் எண்ணிக்கையை ஒப்பிடும்போது.

113
00:05:03,680 --> 00:05:06,300
>> ஒரு சீரான இரும தேடல் மரம் ஒரு மதிப்பு திருமணம் செய்ய

114
00:05:06,300 --> 00:05:09,540
ஒரு வரிசைப்படுத்தப்பட்ட வரிசையில் இரும தேடல் போல.

115
00:05:09,540 --> 00:05:12,290
உண்மையில், நாம் பொருட்களை சேர்க்க அல்லது நீக்க வேண்டும் என்றால்,

116
00:05:12,290 --> 00:05:15,150
அவர்கள் அதே வழியில் நடந்து.

117
00:05:15,150 --> 00:05:17,600
எனினும், ஒரு மரம் அமைப்பு நல்லது

118
00:05:17,600 --> 00:05:19,530
கையாளுதல் புகுத்தல் மற்றும் நீக்கங்கள் இடம்

119
00:05:20,360 --> 00:05:22,670
>> என் பெயர் Bannus வான் டெர் Kloot உள்ளது.

120
00:05:22,670 --> 00:05:24,030
இந்த CS50 உள்ளது.