1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] איך היית לייצג את כל בני המשפחה שלך במחשב?

2
00:00:10,790 --> 00:00:12,390
אנחנו יכולים פשוט להשתמש ברשימה,

3
00:00:12,390 --> 00:00:14,400
אבל יש היררכיה ברורה כאן.

4
00:00:14,400 --> 00:00:17,110
>> נניח שאנחנו מתחילים עם סבתא רבא שלך, אליס.

5
00:00:17,110 --> 00:00:19,030
יש לה 2 בנים, בוב

6
00:00:19,030 --> 00:00:21,310
והסבא שלך, צ'רלי.

7
00:00:21,310 --> 00:00:23,190
צ'רלי יש 3 ילדים,

8
00:00:23,190 --> 00:00:26,730
הדוד שלך, דייב, הדודה שלך, חווה, והאבא שלך, פרד.

9
00:00:26,730 --> 00:00:28,750
אתה הבן היחיד של פרד.

10
00:00:28,750 --> 00:00:30,950
>> למה שמארגן בני המשפחה שלך בדרך זו

11
00:00:30,950 --> 00:00:34,010
להיות טוב יותר מייצוג הרשימה הפשוטה?

12
00:00:34,010 --> 00:00:36,630
סיבה אחת היא שהמבנה ההיררכי הזה,

13
00:00:36,630 --> 00:00:39,660
שם "עץ", מכיל מידע רב יותר מרשימה פשוטה.

14
00:00:40,540 --> 00:00:43,520
אנחנו יודעים את היחסים המשפחתיים בין כולם

15
00:00:43,520 --> 00:00:45,440
רק על ידי בחינת העץ.

16
00:00:45,440 --> 00:00:47,250
כמו כן, זה יכול להאיץ

17
00:00:47,250 --> 00:00:50,010
זמן מראה, עד מאוד, אם נתונים של עץ ממוינים.

18
00:00:50,010 --> 00:00:53,850
>> אנחנו לא יכולים לנצל את זה כאן, אבל אנחנו נראה דוגמה לכך בקרוב.

19
00:00:53,850 --> 00:00:56,150
כל אדם מיוצג על ידי צומת בעץ.

20
00:00:56,680 --> 00:00:58,370
בלוטות יכולות להיות בלוטות ילד

21
00:00:58,370 --> 00:01:00,350
כמו גם צומת אב.

22
00:01:00,350 --> 00:01:02,390
אלה הם התנאים הטכניים,

23
00:01:02,390 --> 00:01:05,220
גם בעת שימוש עצים לדברים מלבד משפחות.

24
00:01:05,220 --> 00:01:07,940
הצומת של אליס יש 2 ילדים ולא הורים,

25
00:01:07,940 --> 00:01:11,500
תוך הצומת של צ'רלי יש 3 ילדים והוריים 1.

26
00:01:11,500 --> 00:01:14,330
>> צומת עלה היא אחד שאין לו ילדים

27
00:01:14,330 --> 00:01:16,410
בקצה החיצוני של העץ.

28
00:01:16,410 --> 00:01:18,520
הצומת העליונה של העץ, צומת השורש,

29
00:01:18,520 --> 00:01:20,240
אין הורה.

30
00:01:20,240 --> 00:01:23,170
>> עץ בינארי הוא סוג מסוים של עץ,

31
00:01:23,170 --> 00:01:26,720
בכל צומת שיש לו, לכל היותר, 2 ילדים.

32
00:01:26,720 --> 00:01:30,490
הנה struct של צומת של עץ בינארי בג

33
00:01:31,560 --> 00:01:34,530
בכל צומת יש כמה נתונים הקשורים אליו

34
00:01:34,530 --> 00:01:36,520
ו 2 מצביעים לצומת אחרים.

35
00:01:36,520 --> 00:01:38,110
>> בעץ המשפחה שלנו,

36
00:01:38,110 --> 00:01:40,900
את הנתונים הקשורים היה שמו של כל אדם.

37
00:01:40,900 --> 00:01:43,850
הנה הוא int, למרות שזה יכול להיות כל דבר.

38
00:01:44,510 --> 00:01:46,200
כפי שמתברר,

39
00:01:46,200 --> 00:01:48,990
עץ בינארי לא יהיה ייצוג טוב למשפחה,

40
00:01:48,990 --> 00:01:51,960
מאחר שאנשים לעתים קרובות יש יותר מ 2 ילדים.

41
00:01:51,960 --> 00:01:53,510
>> עץ חיפוש

42
00:01:53,510 --> 00:01:56,380
הוא סוג מיוחד, המסודרת בעץ בינארי

43
00:01:56,380 --> 00:01:58,090
שמאפשר לנו להסתכל על ערכים במהירות.

44
00:01:58,740 --> 00:02:00,050
ייתכן שתהיו לב

45
00:02:00,050 --> 00:02:02,010
שכל צומת שמתחת לשורש של עץ

46
00:02:02,010 --> 00:02:04,620
הוא שורש של עץ אחר, הנקרא "תת עץ".

47
00:02:04,960 --> 00:02:07,090
הנה, השורש של העץ הוא 6,

48
00:02:07,090 --> 00:02:09,860
והילד שלה, 2, הוא השורש של עץ משנה.

49
00:02:09,860 --> 00:02:11,870
>> בעץ חיפוש

50
00:02:11,870 --> 00:02:15,790
כל הערכים של צומת נכונה עץ משנה

51
00:02:15,790 --> 00:02:18,690
גדולים יותר מערכו של הצומת. הנה: 6.

52
00:02:18,690 --> 00:02:22,640
ובכן, ערכים בתת העץ השמאלי של צומת

53
00:02:24,540 --> 00:02:26,890
הם פחות מהערך של הצומת.

54
00:02:26,890 --> 00:02:28,620
אם אנחנו צריכים לטפל בערכים כפולים,

55
00:02:28,620 --> 00:02:31,760
אנחנו יכולים לשנות אף אחד מזה לאי שוויון רופף,

56
00:02:31,760 --> 00:02:34,410
כלומר ערכים זהים יכולים לנפול גם על שמאל או ימין,

57
00:02:34,410 --> 00:02:37,400
כל עוד אנחנו עולים בקנה אחד על זה לאורך כל דרך.

58
00:02:37,400 --> 00:02:39,620
העץ הזה הוא עץ חיפוש

59
00:02:39,620 --> 00:02:41,540
כי זה כדלקמן כללים אלה.

60
00:02:42,320 --> 00:02:46,020
>> כך זה היה נראה אם ​​פנינו לכל צומת structs C.

61
00:02:46,880 --> 00:02:48,410
שים לב שאם ילד נעדר

62
00:02:48,410 --> 00:02:50,340
המצביע הוא ריק.

63
00:02:50,340 --> 00:02:53,270
איך לבדוק אם 7 הם בעץ?

64
00:02:53,270 --> 00:02:55,020
אנחנו מתחילים בשורש.

65
00:02:55,020 --> 00:02:58,690
שבע הם יותר מ 6, אז אם זה בעץ, זה חייב להיות לצד ימין.

66
00:02:59,680 --> 00:03:03,650
ואז, זה פחות מ 8, ולכן הוא חייב להישאר.

67
00:03:03,650 --> 00:03:06,210
הנה, מצאו 7.

68
00:03:06,210 --> 00:03:08,160
עכשיו, תבדקו עבור 5.

69
00:03:08,160 --> 00:03:11,500
חמש הם פחות מ 6, אז זה חייב להיות בצד השמאל.

70
00:03:11,500 --> 00:03:13,460
חמש גדולים מ 2,

71
00:03:13,460 --> 00:03:15,010
אז זה חייב להיות נכון,

72
00:03:15,010 --> 00:03:18,100
והוא גם עולה על 4, אז זה חייב להיות נכון שוב.

73
00:03:18,100 --> 00:03:20,300
עם זאת, אין כאן ילדה.

74
00:03:20,300 --> 00:03:22,000
המצביע הוא ריק.

75
00:03:22,000 --> 00:03:24,270
משמעות הדבר הוא כי 5 הם לא בעץ שלנו.

76
00:03:24,270 --> 00:03:27,250
>> אנחנו יכולים לחפש את העץ בינארי עם את הקוד הבא:

77
00:03:28,430 --> 00:03:31,140
בכל צומת, אנחנו בודקים כדי לראות אם שמצאנו

78
00:03:31,140 --> 00:03:33,020
הערך שאנחנו מחפשים.

79
00:03:33,020 --> 00:03:35,740
אם אנחנו לא מוצאים אותו, אנו קובעים אם זה צריך להיות

80
00:03:35,740 --> 00:03:38,990
בצד שמאל או ימין ולבדוק שעץ משנה.

81
00:03:38,990 --> 00:03:41,160
לולאה זו תמשיך במורד העץ

82
00:03:41,160 --> 00:03:44,190
עד שלא יהיה צומת ילד על שמאל או ימין.

83
00:03:45,190 --> 00:03:48,600
>> זכור כי 5 לא היו בעץ.

84
00:03:48,600 --> 00:03:50,460
איך להכניס אותו?

85
00:03:50,460 --> 00:03:52,370
התהליך דומה במראו לביצוע חיפוש.

86
00:03:52,370 --> 00:03:54,830
שנעמיק את העץ החל מ 6,

87
00:03:54,830 --> 00:03:57,040
נותר 2,

88
00:03:57,040 --> 00:03:59,140
זכות ל4,

89
00:03:59,140 --> 00:04:02,500
ושוב ימינה, אבל 4 אין ילד בצד הזה.

90
00:04:02,500 --> 00:04:06,090
זה יהיה התפקיד החדש עבור 5,

91
00:04:06,090 --> 00:04:08,500
וזה יתחיל ללא ילדים.

92
00:04:09,020 --> 00:04:12,220
>> כמה מהר הן פעולות על עץ חיפוש?

93
00:04:12,220 --> 00:04:15,410
זכור כי Bigohnotation מבקש לספק גבול עליון.

94
00:04:15,410 --> 00:04:17,390
במקרה הגרוע ביותר,

95
00:04:17,390 --> 00:04:19,480
העץ שלנו יכול להיות פשוט רשימה מקושרת

96
00:04:19,480 --> 00:04:22,220
כלומר הכנסה ש, מחיקה, וחיפוש

97
00:04:22,220 --> 00:04:25,380
יכול לקחת זמן פרופורציונלי למספר צומת בעץ.

98
00:04:25,380 --> 00:04:27,380
זה O (n).

99
00:04:27,380 --> 00:04:30,690
>> לדוגמה, להלן עץ חיפוש חוקי.

100
00:04:31,850 --> 00:04:34,020
עם זאת, אם אנו מנסים למצוא 9,

101
00:04:34,020 --> 00:04:36,760
יש לנו לחצות כל צומת.

102
00:04:36,760 --> 00:04:39,120
אין זה טוב יותר מאשר רשימה מקושרת.

103
00:04:39,120 --> 00:04:41,410
באופן אידיאלי, הייתי רוצה שכל צומת

104
00:04:41,410 --> 00:04:44,120
של עץ החיפוש שלנו יש 2 ילדים.

105
00:04:44,120 --> 00:04:46,370
בדרך זו, הכנסה, מחיקה וחיפוש

106
00:04:46,370 --> 00:04:50,190
היה לוקח, במקרה הגרוע, O (logn) זמן.

107
00:04:50,190 --> 00:04:52,470
העץ מקודם יכול להיות יותר מאוזן,

108
00:04:52,470 --> 00:04:54,140
כמו זה.

109
00:04:54,140 --> 00:04:57,980
כעת, במבט את כל ערך לוקח לכל היותר 3 שלבים.

110
00:04:57,980 --> 00:04:59,460
עץ זה הוא מאוזן,

111
00:04:59,460 --> 00:05:01,190
משמעות היא שיש לו עומק מינימאלי

112
00:05:01,190 --> 00:05:03,680
ביחס למספר צומת.

113
00:05:03,680 --> 00:05:06,300
>> מחפש ערך בעץ חיפוש מאוזן

114
00:05:06,300 --> 00:05:09,540
דומה לחיפוש בינארי במערך ממוין.

115
00:05:09,540 --> 00:05:12,290
למעשה, אם אנחנו לא צריכים להוסיף או למחוק פריטים,

116
00:05:12,290 --> 00:05:15,150
הם מתנהגים בדיוק באותו אופן.

117
00:05:15,150 --> 00:05:17,600
עם זאת, מבנה עץ הוא טוב יותר

118
00:05:17,600 --> 00:05:19,530
לטיפול הוספות ומחיקות

119
00:05:20,360 --> 00:05:22,670
>> השם שלי הוא Bannus אן דר Kloot.

120
00:05:22,670 --> 00:05:24,030
זה CS50.