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
અહીં સી એક દ્વિસંગી વૃક્ષ એક નોડને સ્ટ્રક્ટ છે

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
>> આ રીતે તે જો આપણે સી સ્ટ્ર્ક્ટ્સ માં તમામ ગાંઠો ચાલુ લાગશે.

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
આ ઓ (એન) છે.

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
અંતે સૌથી ખરાબ,, (લોગ એન) ઓ સમય લેશે.

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 છે.