1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Jak można reprezentować wszystkich członków rodziny w komputerze?

2
00:00:10,790 --> 00:00:12,390
Możemy po prostu skorzystać z listy,

3
00:00:12,390 --> 00:00:14,400
ale istnieje wyraźna hierarchia tutaj.

4
00:00:14,400 --> 00:00:17,110
>> Załóżmy, że zaczynamy z prababki, Alice.

5
00:00:17,110 --> 00:00:19,030
Ona ma 2 synów, Bob

6
00:00:19,030 --> 00:00:21,310
a twój dziadek, Charlie.

7
00:00:21,310 --> 00:00:23,190
Charlie ma 3 dzieci,

8
00:00:23,190 --> 00:00:26,730
twój wujek, Dave, twoja ciocia, Eve, i ojciec, Fred.

9
00:00:26,730 --> 00:00:28,750
Jesteś jedynakiem Freda.

10
00:00:28,750 --> 00:00:30,950
>> Dlaczego miałby organizowanie członków rodziny w ten sposób

11
00:00:30,950 --> 00:00:34,010
lepiej niż prosta reprezentacji listy?

12
00:00:34,010 --> 00:00:36,630
Jednym z powodów tego jest fakt, że strukturę hierarchiczną,

13
00:00:36,630 --> 00:00:39,660
zwaną "drzewo", zawiera więcej informacji niż prosta lista.

14
00:00:40,540 --> 00:00:43,520
Znamy rodzinnych relacji między wszystkimi

15
00:00:43,520 --> 00:00:45,440
tylko badając drzewo.

16
00:00:45,440 --> 00:00:47,250
Ponadto, można przyspieszyć

17
00:00:47,250 --> 00:00:50,010
look-up time ogromnie, jeśli dane drzewo jest posortowana.

18
00:00:50,010 --> 00:00:53,850
>> Nie możemy wykorzystać, że tutaj, ale zobaczymy przykład tego wkrótce.

19
00:00:53,850 --> 00:00:56,150
Każdy jest reprezentowany przez element drzewa.

20
00:00:56,680 --> 00:00:58,370
Węzły mogą mieć węzły

21
00:00:58,370 --> 00:01:00,350
oraz węzeł nadrzędny.

22
00:01:00,350 --> 00:01:02,390
Są to warunki techniczne,

23
00:01:02,390 --> 00:01:05,220
nawet przy użyciu drzew rzeczy oprócz rodzin.

24
00:01:05,220 --> 00:01:07,940
Węzeł Alicji ma 2 dzieci i nie ma rodziców,

25
00:01:07,940 --> 00:01:11,500
natomiast węzeł Charlie ma 3 dzieci i 1 rodzica.

26
00:01:11,500 --> 00:01:14,330
>> Węzeł liścia jest, że nie ma żadnych dzieci

27
00:01:14,330 --> 00:01:16,410
na zewnętrznej krawędzi drzewa.

28
00:01:16,410 --> 00:01:18,520
Najwyższy węzeł drzewa, węzeł root,

29
00:01:18,520 --> 00:01:20,240
nie ma rodzica.

30
00:01:20,240 --> 00:01:23,170
>> Drzewo binarne to szczególny rodzaj drzewa,

31
00:01:23,170 --> 00:01:26,720
, w którym każdy węzeł ma co najwyżej 2 dzieci.

32
00:01:26,720 --> 00:01:30,490
Oto struktura węzła z drzewa binarnego w C.

33
00:01:31,560 --> 00:01:34,530
Każdy węzeł ma pewne dane związane

34
00:01:34,530 --> 00:01:36,520
i 2 wskaźniki do innych węzłów.

35
00:01:36,520 --> 00:01:38,110
>> W naszym drzewie genealogicznym,

36
00:01:38,110 --> 00:01:40,900
Związane było dane każdej osoby imię.

37
00:01:40,900 --> 00:01:43,850
Tutaj jest to int, choć to może być cokolwiek.

38
00:01:44,510 --> 00:01:46,200
Jak się okazuje,

39
00:01:46,200 --> 00:01:48,990
Drzewo binarne nie byłoby dobre przedstawienie dla rodziny,

40
00:01:48,990 --> 00:01:51,960
ponieważ ludzie często mają więcej niż 2 dzieci.

41
00:01:51,960 --> 00:01:53,510
>> Binary search tree

42
00:01:53,510 --> 00:01:56,380
Jest to specjalny, zamawianych typ drzewa binarnego

43
00:01:56,380 --> 00:01:58,090
która pozwala nam spojrzeć na wartości szybko.

44
00:01:58,740 --> 00:02:00,050
Można zauważyć,

45
00:02:00,050 --> 00:02:02,010
że każdy węzeł poniżej korzenia drzewa

46
00:02:02,010 --> 00:02:04,620
jest źródłem innego drzewa, zwany poddrzewa.

47
00:02:04,960 --> 00:02:07,090
Tutaj, korzeniem drzewa jest 6,

48
00:02:07,090 --> 00:02:09,860
i jej dziecko, 2, jest korzeniem poddrzewa.

49
00:02:09,860 --> 00:02:11,870
>> W binarnym drzewie poszukiwań

50
00:02:11,870 --> 00:02:15,790
wszystkie wartości węzła rację poddrzewa

51
00:02:15,790 --> 00:02:18,690
są większe niż węzła wartości. Tutaj: 6.

52
00:02:18,690 --> 00:02:22,640
Cóż, wartości z lewego poddrzewa węzła

53
00:02:24,540 --> 00:02:26,890
mniej niż węzła wartości.

54
00:02:26,890 --> 00:02:28,620
Jeżeli musimy obsługiwać zduplikowane wartości,

55
00:02:28,620 --> 00:02:31,760
możemy zmienić jeden z tych, do luźnej nierówności

56
00:02:31,760 --> 00:02:34,410
czyli identyczne wartości może spaść albo na lewo lub prawo,

57
00:02:34,410 --> 00:02:37,400
tak długo, jak są zgodne o nim całym.

58
00:02:37,400 --> 00:02:39,620
To drzewo jest drzewo binarne wyszukiwanie

59
00:02:39,620 --> 00:02:41,540
ponieważ wynika te zasady.

60
00:02:42,320 --> 00:02:46,020
>> Jest to, jak to będzie wyglądać, jeśli okazało wszystkie węzły do ​​struktur C.

61
00:02:46,880 --> 00:02:48,410
Zauważ, że jeśli dziecko nie ma,

62
00:02:48,410 --> 00:02:50,340
wskaźnik jest null.

63
00:02:50,340 --> 00:02:53,270
W jaki sposób sprawdzić, czy 7 jest w drzewie?

64
00:02:53,270 --> 00:02:55,020
Zaczynamy od korzenia.

65
00:02:55,020 --> 00:02:58,690
Siedem jest większa niż 6, jeśli jest to w drzewie, musi być w prawo.

66
00:02:59,680 --> 00:03:03,650
Następnie, nie jest mniejszy niż 8, więc należy pozostawić.

67
00:03:03,650 --> 00:03:06,210
Tutaj nie znaleziono 7.

68
00:03:06,210 --> 00:03:08,160
Teraz będziemy sprawdzać 5.

69
00:03:08,160 --> 00:03:11,500
Pięć jest mniejsza niż 6, tak więc musi być w lewo.

70
00:03:11,500 --> 00:03:13,460
Pięć jest większy niż 2,

71
00:03:13,460 --> 00:03:15,010
więc musi być w porządku,

72
00:03:15,010 --> 00:03:18,100
i to jest również większa niż 4, więc to musi być jeszcze raz w prawo.

73
00:03:18,100 --> 00:03:20,300
Jednakże, nie ma na dziecko.

74
00:03:20,300 --> 00:03:22,000
Wskaźnik jest null.

75
00:03:22,000 --> 00:03:24,270
Oznacza to, że nie jest w 5 naszego drzewa.

76
00:03:24,270 --> 00:03:27,250
>> Możemy przeszukiwać drzewo binarne z następującego kodu:

77
00:03:28,430 --> 00:03:31,140
Na każdym węźle, możemy sprawdzić, czy udało nam się znaleźć

78
00:03:31,140 --> 00:03:33,020
wartość szukamy.

79
00:03:33,020 --> 00:03:35,740
Jeśli nie znajdziemy, możemy ustalić, czy powinien on być

80
00:03:35,740 --> 00:03:38,990
na prawo lub w lewo i sprawdź, poddrzewa.

81
00:03:38,990 --> 00:03:41,160
Pętla ta będzie nadal w dół drzewa

82
00:03:41,160 --> 00:03:44,190
dopóki nie ma węzeł dziecko na lewo lub prawo.

83
00:03:45,190 --> 00:03:48,600
>> Pamiętaj, że 5 nie był w drzewie.

84
00:03:48,600 --> 00:03:50,460
Jak możemy włożyć?

85
00:03:50,460 --> 00:03:52,370
Proces wygląda podobnie do wyszukiwania.

86
00:03:52,370 --> 00:03:54,830
Mamy iteracyjne w dół drzewa, począwszy od 6,

87
00:03:54,830 --> 00:03:57,040
lewej do 2,

88
00:03:57,040 --> 00:03:59,140
prawo do 4,

89
00:03:59,140 --> 00:04:02,500
i znowu w prawo, a dzieci nie 4 po tej stronie.

90
00:04:02,500 --> 00:04:06,090
Będzie nową pozycję 5,

91
00:04:06,090 --> 00:04:08,500
i rozpocznie się bez dzieci.

92
00:04:09,020 --> 00:04:12,220
>> Jak szybko to operacje na drzewa binarnego wyszukiwania?

93
00:04:12,220 --> 00:04:15,410
Pamiętaj, że Bigohnotation ma zapewnić ograniczenie górne.

94
00:04:15,410 --> 00:04:17,390
W najgorszym przypadku,

95
00:04:17,390 --> 00:04:19,480
nasze drzewo może być po prostu połączonej listy

96
00:04:19,480 --> 00:04:22,220
co oznacza, że ​​wstawiania, usuwania i wyszukiwania

97
00:04:22,220 --> 00:04:25,380
może czasu jest proporcjonalny do liczby węzłów w drzewie.

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

99
00:04:27,380 --> 00:04:30,690
>> Na przykład poniższe nie jest ważne drzewo wyszukiwania binarnego.

100
00:04:31,850 --> 00:04:34,020
Jednakże, jeśli staramy się znaleźć 9,

101
00:04:34,020 --> 00:04:36,760
musimy przemierzać każdy węzeł.

102
00:04:36,760 --> 00:04:39,120
Nie jest lepsza niż połączonej listy.

103
00:04:39,120 --> 00:04:41,410
Idealnie, chcielibyśmy każdy węzeł

104
00:04:41,410 --> 00:04:44,120
z naszego drzewa wyszukiwania binarnego mieć 2 dzieci.

105
00:04:44,120 --> 00:04:46,370
W ten sposób, wstawiania, usuwania i wyszukiwania

106
00:04:46,370 --> 00:04:50,190
weźmie, co gorsza, O (log n) czasu.

107
00:04:50,190 --> 00:04:52,470
Drzewo z przed może być bardziej zrównoważony,

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

109
00:04:54,140 --> 00:04:57,980
Teraz, patrząc na jakąkolwiek wartość trwa najwyżej 3 kroki.

110
00:04:57,980 --> 00:04:59,460
To drzewo jest zrównoważone,

111
00:04:59,460 --> 00:05:01,190
co oznacza, że ​​ma minimalne jest głębokość

112
00:05:01,190 --> 00:05:03,680
w stosunku do liczby węzłów.

113
00:05:03,680 --> 00:05:06,300
>> Szukasz wartości w zrównoważonym drzewie wyszukiwania binarnego

114
00:05:06,300 --> 00:05:09,540
jest podobny do binarnego wyszukiwania w posortowanej tablicy.

115
00:05:09,540 --> 00:05:12,290
W rzeczywistości, jeśli nie musimy wstawić lub usunąć elementy,

116
00:05:12,290 --> 00:05:15,150
zachowują się dokładnie tak samo.

117
00:05:15,150 --> 00:05:17,600
Jednak struktura drzewa jest lepiej

118
00:05:17,600 --> 00:05:19,530
do wstawienia i usunięcia obsługi

119
00:05:20,360 --> 00:05:22,670
>> Nazywam się Bannus Van der Kloot.

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