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
પરંતુ તમે Aladdin, એલિસ, એરિયલ, વાંચી અને તેથી આગળ,

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
હવે તમે Tarzan, ભાતનો ટાંકો, સ્નો વ્હાઇટ, અને તેથી આગળ વાંચો.

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
મીન અને મહત્તમ લઘુત્તમ અને મહત્તમ સ્થિતિઓ ના સૂચકાંકમાં છે

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
જે 2 ના 5 અને 34 કિંમતો સાથે બાળકો ગાંઠો હોય છે.

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
બેક અપ સતત, અમે 5 એ છાપો અને પછી 8 ના.

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 ડાબા ઉપવૃક્ષ ધરાવે છે, અને તેથી અમે 89 એ છાપો, તો 144 અનુસરતા,

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
વોઇલા Query! અમે અમારા દ્વિસંગી શોધ વૃક્ષ એક નંબર ઉમેર્યા છે.

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
માટે ઉપવૃક્ષ કે હવે parentless બાકી છે કનેક્ટ

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
અને પછી કાઢી નાંખવાની 1 2 ને સૂચિત થયેલ નિયમો દ્વારા નિયંત્રિત થાય છે.

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
અમે પછી 2 ગાંઠો સ્વેપ, 13 પાંદડાના અને 21 કેન્દ્રિય જૂથ નોડ બનાવે છે.

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
તે અત્યંત ઓછી છે કે રેન્ડમ તક દ્વારા નંબરો એક shuffled યાદી સૉર્ટ થાય છે.

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
એક સ્પષ્ટ માર્ગ ના યાદી સ્કેન પ્રયત્ન ... હો [બીપ Comment]

227
00:11:43,000 --> 00:11:46,000
... વસ્તુઓની સંખ્યા ... હા

228
00:11:46,000 --> 00:11:50,000
[Laughs]

229
00:11:50,000 --> 00:11:55,000
... 234 ... augh ઓફ નોડ પોસ્ટ કરો.

230
00:11:55,000 --> 00:11:58,000
>> યે! કે હતી -