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
Она има 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
Овде је струцт од чвор бинарног стабла у Ц.

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
>> Ово је како би то изгледало да смо се окренули све чворове у Ц Структуре.

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
Запамтите да Бигохнотатион настоји да обезбеди горњи граница.

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
Ово је О (н).

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
би предузети, у најгорем случају, О (лог н) времена.

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
>> Моје име је Баннус Ван дер Клоот.

120
00:05:22,670 --> 00:05:24,030
Ово је ЦС50.