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.