1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Wie würden Sie repräsentieren alle Mitglieder Ihrer Familie in einem Computer?

2
00:00:10,790 --> 00:00:12,390
Wir könnten einfach eine Liste,

3
00:00:12,390 --> 00:00:14,400
aber es gibt eine klare Hierarchie hier.

4
00:00:14,400 --> 00:00:17,110
>> Lassen Sie uns sagen, dass wir mit Ihrer Urgroßmutter Alice beginnt.

5
00:00:17,110 --> 00:00:19,030
Sie hat 2 Söhne, Bob

6
00:00:19,030 --> 00:00:21,310
und dein Großvater, Charlie.

7
00:00:21,310 --> 00:00:23,190
Charlie hat 3 Kinder,

8
00:00:23,190 --> 00:00:26,730
Ihr Onkel, Dave, Ihre Tante, Eve, und dein Vater, Fred.

9
00:00:26,730 --> 00:00:28,750
Sie sind Fred einziges Kind.

10
00:00:28,750 --> 00:00:30,950
>> Warum sollte die Organisation Ihrer Familienmitglieder auf diese Weise

11
00:00:30,950 --> 00:00:34,010
besser sein als die einfache Liste Repräsentation?

12
00:00:34,010 --> 00:00:36,630
Ein Grund dafür ist, dass dieser hierarchischen Struktur,

13
00:00:36,630 --> 00:00:39,660
genannt "tree" enthält mehr Informationen als eine einfache Liste.

14
00:00:40,540 --> 00:00:43,520
Wir kennen die familiären Beziehungen zwischen allen

15
00:00:43,520 --> 00:00:45,440
nur durch die Untersuchung der Baum.

16
00:00:45,440 --> 00:00:47,250
Außerdem kann es zu beschleunigen

17
00:00:47,250 --> 00:00:50,010
Look-up-Zeit enorm, wenn Baum Daten sortiert.

18
00:00:50,010 --> 00:00:53,850
>> Wir können nicht die Vorteile, dass hier, aber wir werden ein Beispiel dafür bald zu sehen.

19
00:00:53,850 --> 00:00:56,150
Jede Person wird durch einen Knoten auf dem Baum dargestellt.

20
00:00:56,680 --> 00:00:58,370
Knoten können über untergeordnete Knoten

21
00:00:58,370 --> 00:01:00,350
sowie einer übergeordneten Knoten.

22
00:01:00,350 --> 00:01:02,390
Dies sind die technischen Begriffe,

23
00:01:02,390 --> 00:01:05,220
auch bei Verwendung von Bäumen für Dinge neben Familien.

24
00:01:05,220 --> 00:01:07,940
Alices Knoten hat 2 Kinder und keine Eltern,

25
00:01:07,940 --> 00:01:11,500
, während Charlie Knoten hat 3 Kinder und 1 Elternteil.

26
00:01:11,500 --> 00:01:14,330
>> Ein Blattknoten ist einer, der keine Kinder

27
00:01:14,330 --> 00:01:16,410
am Außenrand des Baumes.

28
00:01:16,410 --> 00:01:18,520
Der oberste Knoten des Baumes, der Wurzelknoten,

29
00:01:18,520 --> 00:01:20,240
hat keine Eltern.

30
00:01:20,240 --> 00:01:23,170
>> Ein binärer Baum ist eine bestimmte Art des Baumes,

31
00:01:23,170 --> 00:01:26,720
in denen jeder Knoten, höchstens zwei Kinder.

32
00:01:26,720 --> 00:01:30,490
Hier ist die Struktur eines Knotens eines binären Baums in C.

33
00:01:31,560 --> 00:01:34,530
Jeder Knoten hat einige Daten zugeordnet

34
00:01:34,530 --> 00:01:36,520
und zwei Zeiger zu anderen Knoten.

35
00:01:36,520 --> 00:01:38,110
>> In unserem Stammbaum,

36
00:01:38,110 --> 00:01:40,900
die zugehörigen Daten wurde jede Person den Namen.

37
00:01:40,900 --> 00:01:43,850
Hier ist es ein int, obwohl es nichts sein könnte.

38
00:01:44,510 --> 00:01:46,200
Wie es sich herausstellt,

39
00:01:46,200 --> 00:01:48,990
ein binärer Baum wäre keine gute Darstellung für eine Familie zu sein,

40
00:01:48,990 --> 00:01:51,960
da die Menschen haben oft mehr als 2 Kinder.

41
00:01:51,960 --> 00:01:53,510
>> Ein binärer Suchbaum

42
00:01:53,510 --> 00:01:56,380
ist eine spezielle, geordnete Art von binären Baum

43
00:01:56,380 --> 00:01:58,090
das ermöglicht es uns, auf die Werte schnell zu suchen.

44
00:01:58,740 --> 00:02:00,050
Sie haben vielleicht bemerkt haben

45
00:02:00,050 --> 00:02:02,010
dass jeder Knoten unter der Wurzel eines Baums

46
00:02:02,010 --> 00:02:04,620
ist die Wurzel eines anderen Baumes, eine so genannte "Teilbaum.

47
00:02:04,960 --> 00:02:07,090
Hier ist die Wurzel des Baumes 6,

48
00:02:07,090 --> 00:02:09,860
und ihr Kind, 2, ist die Wurzel eines Teilbaums.

49
00:02:09,860 --> 00:02:11,870
>> In einem binären Suchbaum

50
00:02:11,870 --> 00:02:15,790
alle Werte eines Knotens ist richtig Teilbaum

51
00:02:15,790 --> 00:02:18,690
größer sind als die des Knotens Wert. Hier: 6.

52
00:02:18,690 --> 00:02:22,640
Nun, die Werte in einem Knoten der linken Teilbaum

53
00:02:24,540 --> 00:02:26,890
weniger als Wert des Knotens.

54
00:02:26,890 --> 00:02:28,620
Wenn wir brauchen, um doppelte Werte zu behandeln,

55
00:02:28,620 --> 00:02:31,760
können wir entweder derjenigen ändern, um eine lose Ungleichheit,

56
00:02:31,760 --> 00:02:34,410
dh identische Werte können entweder fallen auf der linken oder rechten,

57
00:02:34,410 --> 00:02:37,400
Solange wir konsequent darüber sind überall.

58
00:02:37,400 --> 00:02:39,620
Dieser Baum ist ein binärer Suchbaum

59
00:02:39,620 --> 00:02:41,540
weil es folgt diesen Regeln.

60
00:02:42,320 --> 00:02:46,020
>> Dies ist, wie es aussehen würde, wenn wir alle Knoten verwandelte sich in C Strukturen.

61
00:02:46,880 --> 00:02:48,410
Beachten Sie, dass, wenn ein Kind fehlt,

62
00:02:48,410 --> 00:02:50,340
der Zeiger ist null.

63
00:02:50,340 --> 00:02:53,270
Wie können wir überprüfen, ob 7 ist in dem Baum?

64
00:02:53,270 --> 00:02:55,020
Wir beginnen an der Wurzel.

65
00:02:55,020 --> 00:02:58,690
Seven ist größer als 6, also wenn es in dem Baum ist, muss es auf der rechten Seite.

66
00:02:59,680 --> 00:03:03,650
Dann ist es weniger als 8 ist, so muss es überlassen bleiben.

67
00:03:03,650 --> 00:03:06,210
Hier haben wir 7 gefunden.

68
00:03:06,210 --> 00:03:08,160
Jetzt werden wir für 5 zu überprüfen.

69
00:03:08,160 --> 00:03:11,500
Fünf kleiner als 6, so wird sie auf der linken Seite.

70
00:03:11,500 --> 00:03:13,460
Fünf größer als 2 ist,

71
00:03:13,460 --> 00:03:15,010
so muss es sein Recht,

72
00:03:15,010 --> 00:03:18,100
und es ist auch größer als 4, so muss es wieder gut.

73
00:03:18,100 --> 00:03:20,300
Es besteht jedoch kein Kind hier.

74
00:03:20,300 --> 00:03:22,000
Der Zeiger ist null.

75
00:03:22,000 --> 00:03:24,270
Dies bedeutet, dass 5 nicht in unserem Baum.

76
00:03:24,270 --> 00:03:27,250
>> Wir können die binären Baum mit dem folgenden Code suchen:

77
00:03:28,430 --> 00:03:31,140
An jedem Knoten, prüfen wir, ob wir gefunden haben,

78
00:03:31,140 --> 00:03:33,020
der Wert, den wir suchen.

79
00:03:33,020 --> 00:03:35,740
Wenn wir es nicht finden, bestimmen wir, wenn es sein sollte

80
00:03:35,740 --> 00:03:38,990
auf der linken oder rechten und prüfen Sie, ob Teilbaum.

81
00:03:38,990 --> 00:03:41,160
Diese Schleife wird weiterhin den Baum

82
00:03:41,160 --> 00:03:44,190
bis kein Kindknoten entweder an der linken oder rechten Seite.

83
00:03:45,190 --> 00:03:48,600
>> Beachten Sie, dass 5 nicht in den Baum.

84
00:03:48,600 --> 00:03:50,460
Wie setzen wir das?

85
00:03:50,460 --> 00:03:52,370
Der Prozess ähnelt suchen.

86
00:03:52,370 --> 00:03:54,830
Wir durchlaufen den Baum ab 6,

87
00:03:54,830 --> 00:03:57,040
links bis 2,

88
00:03:57,040 --> 00:03:59,140
rechts bis 4,

89
00:03:59,140 --> 00:04:02,500
und gleich wieder rechts, aber 4 hat kein Kind auf dieser Seite.

90
00:04:02,500 --> 00:04:06,090
Dies wird die neue Position für 5 sein kann,

91
00:04:06,090 --> 00:04:08,500
und es wird ohne Kinder beginnen.

92
00:04:09,020 --> 00:04:12,220
>> Wie schnell sind Operationen auf einem binären Suchbaum?

93
00:04:12,220 --> 00:04:15,410
Beachten Sie, dass Bigohnotation um eine obere Schranke erbringen will.

94
00:04:15,410 --> 00:04:17,390
Im ungünstigsten Fall,

95
00:04:17,390 --> 00:04:19,480
unser Baum könnte einfach eine verknüpfte Liste sein

96
00:04:19,480 --> 00:04:22,220
was bedeutet, dass Einfügen, Löschen und Suchen

97
00:04:22,220 --> 00:04:25,380
könnte Zeit proportional zu der Anzahl von Knoten im Baum zu nehmen.

98
00:04:25,380 --> 00:04:27,380
Dies ist O (n).

99
00:04:27,380 --> 00:04:30,690
>> Zum Beispiel ist das Folgende eine gültige binäre Suchbaum.

100
00:04:31,850 --> 00:04:34,020
Allerdings, wenn wir versuchen, 9 zu finden,

101
00:04:34,020 --> 00:04:36,760
wir müssen jeden Knoten durchqueren.

102
00:04:36,760 --> 00:04:39,120
Es ist nicht besser als eine verknüpfte Liste.

103
00:04:39,120 --> 00:04:41,410
Idealerweise würden wir wollen, dass jeder Knoten

104
00:04:41,410 --> 00:04:44,120
unserer binären Suchbaum zu haben 2 Kinder.

105
00:04:44,120 --> 00:04:46,370
Auf diese Weise, Einfügen, Löschen und suchen

106
00:04:46,370 --> 00:04:50,190
dauern würde, im schlimmsten Fall O (log n) Zeit.

107
00:04:50,190 --> 00:04:52,470
Der Baum aus der Zeit vor könnte ausgeglichener,

108
00:04:52,470 --> 00:04:54,140
wie diese.

109
00:04:54,140 --> 00:04:57,980
Nun blickte jeden Wert nimmt, höchstens 3 Schritten.

110
00:04:57,980 --> 00:04:59,460
Dieser Baum ist ausgeglichen,

111
00:04:59,460 --> 00:05:01,190
Bedeutung, ist eine minimale Tiefe

112
00:05:01,190 --> 00:05:03,680
bezogen auf die Anzahl von Knoten.

113
00:05:03,680 --> 00:05:06,300
>> Suche nach einem Wert in einem ausgewogenen binären Suchbaum

114
00:05:06,300 --> 00:05:09,540
ist ähnlich wie binäre Suche auf einem sortierten Array.

115
00:05:09,540 --> 00:05:12,290
In der Tat, wenn wir nicht brauchen, einfügen oder löschen,

116
00:05:12,290 --> 00:05:15,150
sie verhalten sich genau die gleiche Weise.

117
00:05:15,150 --> 00:05:17,600
Jedoch ist eine Baumstruktur bessere

118
00:05:17,600 --> 00:05:19,530
für den Umgang mit Insertionen und Deletionen

119
00:05:20,360 --> 00:05:22,670
>> Mein Name ist Bannus Van der Kloot.

120
00:05:22,670 --> 00:05:24,030
Dies ist CS50.