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
>> თუ მივეცი თქვენ სიაში Disney ხასიათი სახელები ანბანის მიხედვით

5
00:00:09,000 --> 00:00:11,000
და გთხოვეთ მოძიების Mickey Mouse,

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, Alice, Ariel, და ა.შ.,

10
00:00:22,000 --> 00:00:25,000
თქვენ სწრაფად გააცნობიეროს, რომ დაწყებული წინაშე სიაში არ იყო კარგი იდეა.

11
00:00:25,000 --> 00:00:29,000
Okay, იქნებ თქვენ უნდა დაიწყოს მუშაობა უკან ბოლოდან სიაში.

12
00:00:29,000 --> 00:00:33,000
თქვენ ახლა Tarzan, Stitch, თოვლი თეთრი და სხვ.

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 Mouse მანამდე ან მის შემდეგ ამ სახელით.

19
00:00:49,000 --> 00:00:51,000
ეძებს გვარი მეორე სვეტი

20
00:00:51,000 --> 00:00:54,000
ნეტავ გააცნობიეროს, რომ მ მიკი უძღოდა J ამისთვის Jasmine,

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
და ბოლოს იპოვის მიკი იმალებოდა შორის 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
Say ვეძებთ ნომერი 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
Okay. ერთხელ, 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
თუ ჩვენ არ გამოიყენება წრფივი ძებნა აქ, ეს იქნებოდა მიღებული us 12 ნაბიჯები.

49
00:02:24,000 --> 00:02:28,000
როგორც ფაქტობრივად, რადგან ამ ძებნის მეთოდი halves ელემენტთა რაოდენობა

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
გასაღები, array, მინ და მაქს.

56
00:02:47,000 --> 00:02:51,000
გასაღები არის ნომერი, რომელიც ჩვენ ვეძებთ, ასე რომ 144 წელს წინა მაგალითი.

57
00:02:51,000 --> 00:02:54,000
Array არის სიაში ნომრები, რომ ჩვენ ძებნას.

58
00:02:54,000 --> 00:02:57,000
მინ და მაქს are მაჩვენებლების მინიმალური და მაქსიმალური პოზიციები

59
00:02:57,000 --> 00:02:59,000
რომ ჩვენ გაკეთებული ეძებს.

60
00:02:59,000 --> 00:03:03,000
ასე რომ, როდესაც ჩვენ ვიწყებთ, მინ იქნება ნულოვანი და max იქნება მაქსიმალური მაჩვენებელი მასივი.

61
00:03:03,000 --> 00:03:07,000
როგორც ჩვენ ვიწრო ძებნა down, ჩვენ განაახლებს min და max

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
ინდექსი, რომ არის შუა ნაწილამდე იყვნენ შორის min და max of მასივი, რომ ჩვენ ჯერ კიდევ გათვალისწინებით.

66
00:03:19,000 --> 00:03:22,000
მაშინ შევხედავთ ღირებულება array იმ შუაში საიდან

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
მაგრამ ამ დროს განახლებაზე min და max პარამეტრების წაკითხვის მხოლოდ ნახევარი

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
ერთხელ, ჩვენ მოვუწოდებთ ორობითი ძებნა მაგრამ ამ დროს სპექტრს min და max განახლება

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 of node შეიცავს მხოლოდ ღირებულებები რომ მეტი

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
ასე root ამ ხე კვანძის ღირებულების ღირებულების 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
>> მაგალითად, მარცხენა subtree of კვანძის 3 არის ხის მიერ შექმნილი კვანძების 0, 1, და 2.

117
00:06:03,000 --> 00:06:06,000
ასე რომ, თუ ჩვენ დავუბრუნდებით თვისებები ორობითი ძებნა ხე,

118
00:06:06,000 --> 00:06:09,000
ჩვენ ვხედავთ, რომ თითოეული კვანძის in ხე შეესაბამება ყველა 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
მიუხედავად იმისა, რომ ამ ხის გამოიყურება სხვადასხვა, ეს არის სწორი ორობითი ძებნა tree

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
>> Finding ნებისმიერი სხვა ნომრით, რომელიც არ არის მინიმალური და მაქსიმალური

134
00:06:56,000 --> 00:06:58,000
ისეთივე ადვილი.

135
00:06:58,000 --> 00:07:00,000
Say ჩვენ ვეძებთ ნომერი 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
Lo და აჰა, 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
მაგალითად, ავიღოთ ჩვენი საყვარელი ორობითი ძებნა tree

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
ჩვენ hop ქვემოთ 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
და ბოლოს მარჯვენა საუკეთესო კვანძის of 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, ამიტომ ჩვენ traverse მარჯვნივ.

174
00:09:01,000 --> 00:09:04,000
რადგან არანაკლებ 8 და 8 არის ფოთოლი კვანძში, დავუმატებთ 7 მარცხნივ ბავშვი 8.

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
Say გვინდა წაშლა 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
to მშობელი კვანძი ჩვენ უბრალოდ მკვდარია.

189
00:09:44,000 --> 00:09:47,000
Say გვინდა წაშლა 3 ჩვენი ხე.

190
00:09:47,000 --> 00:09:50,000
ჩვენ ვიღებთ ბავშვის ელემენტს, რომ კვანძის და დაურთოს მშობელი კვანძი.

191
00:09:50,000 --> 00:09:54,000
ამ შემთხვევაში, ჩვენ ახლა ვამაგრებ 1 დან 5.

192
00:09:54,000 --> 00:09:57,000
ეს მუშაობს უპრობლემოდ, რადგან ჩვენ ვიცით, შესაბამისად ორობითი ძებნა ხე ქონება,

193
00:09:57,000 --> 00:10:01,000
რომ ყველაფერი მარცხენა subtree 3 ნაკლები იყო 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 of 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
მაგალითად, რა ხდება, როდესაც ჩვენ ვაშენებთ ორობითი ძებნა tree

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
უბრალოდ შემთხვევით shuffle შეყვანის ღირებულებები.

220
00:11:21,000 --> 00:11:26,000
ეს ძალზედ ნაკლებად სავარაუდოა, რომ შემთხვევითი შანსი აჩეხვა სიაში ნომრები დალაგებულია.

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
ერთი აშკარა გზა იქნებოდა სკანირებას სიის ... [beep]

227
00:11:43,000 --> 00:11:46,000
... ელემენტთა რაოდენობა ... yep

228
00:11:46,000 --> 00:11:50,000
[იცინის]

229
00:11:50,000 --> 00:11:55,000
პოსტი ... კვანძის of 234 ... augh.

230
00:11:55,000 --> 00:11:58,000
>> YAY! ეს იყო -