1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [द्विआधारी खोज]

2
00:00:02,000 --> 00:00:04,000
[पैट्रिक Schmid हार्वर्ड विश्वविद्यालय]

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
मिकी रॅपन्ज़ेल से पहले आता है, लगता है कि हम अंतिम स्तंभ के रूप में अच्छी तरह से अनदेखा कर सकते हैं.

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
और अंत में मिकी मर्लिन और Minnie के बीच में छिपा पाते हैं.

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
एक पुनरावर्ती समारोह है कि द्विआधारी खोज को लागू करने के लिए कुछ pseudocode.

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
>> दिलचस्प हिस्सा 1 को छोड़ दो.

64
00:03:12,000 --> 00:03:14,000
पहली बात हम करते है midpoint खोजने के,

65
00:03:14,000 --> 00:03:19,000
सूचकांक कि मिनट और सरणी है कि हम अभी भी विचार कर रहे हैं के अधिकतम के बीच आधे रास्ते है.

66
00:03:19,000 --> 00:03:22,000
तो फिर हम कि midpoint स्थान पर सरणी के मूल्य में देखो

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
इस प्रकार, हम केवल वर्तमान midpoint सूचकांक वापसी कर सकते हैं, और हम कर रहे हैं.

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
या तो हम एक unsorted सूची ले और द्विआधारी खोज का उपयोग करने से पहले इसे सुलझा,

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
सबसे पहले, किसी भी नोड के बाईं subtree केवल मूल्यों है कि कम से कम कर रहे हैं शामिल

101
00:05:09,000 --> 00:05:11,000
या नोड के मूल्य के बराबर है.

102
00:05:11,000 --> 00:05:15,000
दूसरा, ठीक एक नोड के subtree केवल मूल्यों है कि अधिक से अधिक कर रहे हैं शामिल

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
एक subtree पेड़ कि पूरे ट्री की एक उपधारा पर देखने से बस का गठन किया है.

116
00:05:57,000 --> 00:06:03,000
>> उदाहरण के लिए, 3 नोड के बाईं subtree पेड़ नोड्स 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
केवल छोड़ दिया subtree मूल्यों है कि कम से कम या नोड के मूल्य के बराबर होता है;

120
00:06:15,000 --> 00:06:16,000
सभी नोड्स का सही subtree

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 चंक्रमण सब कुछ subtree में छोड़ बाहर प्रिंट का मतलब

147
00:07:35,000 --> 00:07:37,000
नोड ही मुद्रण द्वारा पीछा

148
00:07:37,000 --> 00:07:40,000
और फिर सब कुछ सही subtree में मुद्रण द्वारा पीछा किया.

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
subtree में छोड़ दिया सब कुछ.

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
तो हम सही subtree है, जो 2 है के लिए जाना है, और कहा कि बाहर प्रिंट.

157
00:08:03,000 --> 00:08:05,000
अब है कि हम कि subtree के साथ कर रहे हैं,

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
अब है कि हम पूरे पूरा कर लिया है subtree छोड़ दिया,

161
00:08:13,000 --> 00:08:17,000
हम बाहर 13 मुद्रित कर सकते हैं और सही subtree पर काम शुरू करते हैं.

162
00:08:17,000 --> 00:08:21,000
हम 34 के लिए नीचे हॉप, लेकिन 34 मुद्रण से पहले हम अपनी बाईं subtree प्रिंट है.

163
00:08:21,000 --> 00:08:27,000
इसलिए हम बाहर मुद्रित करने के लिए 21, तो हम बाहर 34 प्रिंट और इसकी सही subtree जाएँ.

164
00:08:27,000 --> 00:08:31,000
के बाद से 55 नहीं छोड़ दिया subtree है, हम इसे प्रिंट बाहर और पर इसकी सही subtree जारी.

165
00:08:31,000 --> 00:08:36,000
144 एक बाएं subtree है, और इसलिए हम बाहर मुद्रित करने के लिए 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
देखा! हम हमारे द्विआधारी खोज वृक्ष एक संख्या को जोड़ दिया है.

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
subtree है कि अब 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 के बाईं subtree में है कि सब कुछ कम से कम 5 था.

194
00:10:01,000 --> 00:10:05,000
अब जब कि 3 subtree ध्यान रखा जाता है, हम इसे हटा सकते हैं.

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 aforementioned नियमों के द्वारा नियंत्रित किया जाता है.

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
>> जैसा कि पहले के लिए alluded, वहाँ कई संभव करने के लिए एक वैध द्विआधारी खोज वृक्ष बनाने के तरीके हैं.

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
मैं पैट्रिक Schmid हूँ, और इस 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
>> हाँ! यही था -