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
এবং আপনি Mickey মাউস খুঁজে জিজ্ঞাসা,

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
এবং যদি এটা দেখতে Mickey প্রতি নাম চেক.

9
00:00:18,000 --> 00:00:22,000
কিন্তু হিসাবে আপনি Aladdin, এলিস, Ariel, পড়া এবং তাই ঘোষণা,

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
এবং যদি Mickey মাউস আগে বা পরে এই নামটি চেক.

19
00:00:49,000 --> 00:00:51,000
দ্বিতীয় কলামের নামের শেষ সময়ে খুঁজছি

20
00:00:51,000 --> 00:00:54,000
আপনি যে Mickey জন্য এম Jasmine জন্য J অবস্থার পর আসে বুঝতে চাই,

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
Mickey Rapunzel আগে আসে; দেখে মনে হচ্ছে আমরা শেষ কলাম উপেক্ষা হিসাবে ভাল করতে পারেন.

25
00:01:06,000 --> 00:01:08,000
অনুসন্ধান অব্যাহত কৌশল, দ্রুত আপনি দেখতে পাবেন যে Mickey

26
00:01:08,000 --> 00:01:11,000
নামের অবশিষ্ট তালিকার প্রথম অর্ধেক হয়

27
00:01:11,000 --> 00:01:14,000
এবং পরিশেষে Mickey Merlin এবং 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
একটি recursive ফাংশন যে বাইনারি অনুসন্ধান কার্যকরী জন্য কিছু 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
>> যাক আকর্ষণীয় অংশ প্রথমে এর লাফালাফি করা.

64
00:03:12,000 --> 00:03:14,000
প্রথম জিনিস আমরা না হয় মিডপয়েন্ট খুঁজে,

65
00:03:14,000 --> 00:03:19,000
সূচক halfway অ্যারের যে আমরা এখনও বিবেচনা করা হয় এবং কমপক্ষে সবের্াচ্চ মধ্যে যে হয়.

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
প্রথমত, কোনো নোডের মধ্যে বাম 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
যা মান 2 5 34 এবং শিশুদের নোড আছে.

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 root-এ শুরু, কিন্তু আমরা আউট মুদ্রণ মুদ্রণ 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 থেকে প্রস্থান করে, কিন্তু আমরা তার বাম subtree প্রিন্ট আউট মুদ্রণ 34 আগে আছে.

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
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
যাও subtree যে এখন হয় মাতাপিতৃহীন বাকি সংযোগ

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
দুই, swap এবং তারপর প্রশ্ন নোড মুছে দিন.

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
আমরা তখন 2 নোড, swap 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
আমি প্যাট্রিক 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
[Laughs]

229
00:11:50,000 --> 00:11:55,000
... 234 ... augh নোডের মধ্যে পোষ্ট.

230
00:11:55,000 --> 00:11:58,000
>> ইয়ে! যে ছিল -