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
Тя има два сина, Боб

6
00:00:19,030 --> 00:00:21,310
и дядо ти, Чарли.

7
00:00:21,310 --> 00:00:23,190
Чарли има три деца,

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
Възел Алис има две деца и не родители,

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
, в която всеки възел има най-много две деца.

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
Ето това е едно цяло число, въпреки че тя може да бъде всичко.

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
Five е по-малко от 6, така че трябва да бъде отляво.

70
00:03:11,500 --> 00:03:13,460
Five е по-голямо от 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
право на четири,

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
на нашето дърво за двоично търсене, за да имат две деца.

105
00:04:44,120 --> 00:04:46,370
По този начин, вмъкване, изтриване и търсене

106
00:04:46,370 --> 00:04:50,190
ще отнеме, в най-лошия случай, O (дневник н) време.

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
Сега, каквато и да е стойност отнема най-много три стъпки.

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.