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
>> Скажімо, ми починаємо з вашої прабабусі, Alice.

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
Ось структура вузла в бінарному дереві в C.

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
>> Ось як це буде виглядати, якщо ми повернули всіх вузлів в структурах 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 (журнал N) часу.

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.