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
אבל כשאתה קורא אלדין, אליס, אריאל, וכן הלאה,

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
היית מבין שM למיקי מגיע אחרי 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
ולראות שהוא מתחיל עם רפונזל.

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
ולבסוף מוצא את מיקי מסתתר בין מרלין ומיני.

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
>> בואו נדלג לחלק המעניין ראשון.

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
ולבסוף, שני עצי המשנה ימניים והשמאליים של כל צומת

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
עצי משנה הוא ימניים ושמאליים של כל צומת גם הם עצי חיפוש בינאריים.

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 הוא צומת עלה, אנו מוסיפים 7 לילד השמאלי של 8.

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
כדי לחבר את עץ המשנה שנותר עתה ללא הורים

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
במקרה זה, אנחנו מצרפים עכשיו 1 עד 5.

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
זה מאוד לא סביר כי במקרה אקראי רשימה דשדשה של מספרים ממוינת.

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
דרך ברורה אחת היא לסרוק את הרשימה מ... [צפצוף]

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
לפרסם ... צומת של 234 ... augh.

230
00:11:55,000 --> 00:11:58,000
>> יש! זה היה -