1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Jak byste reprezentovat všechny své rodinné příslušníky v počítači?

2
00:00:10,790 --> 00:00:12,390
Mohli bychom jednoduše použít seznam,

3
00:00:12,390 --> 00:00:14,400
ale je tu jasná hierarchie zde.

4
00:00:14,400 --> 00:00:17,110
>> Řekněme, že jsme začali s velký-babička, Alice.

5
00:00:17,110 --> 00:00:19,030
Má 2 syny, Bob

6
00:00:19,030 --> 00:00:21,310
a tvůj dědeček, Charlie.

7
00:00:21,310 --> 00:00:23,190
Charlie má 3 děti,

8
00:00:23,190 --> 00:00:26,730
tvůj strýc, Dave, tvoje teta, Eve, a tvůj otec, Fred.

9
00:00:26,730 --> 00:00:28,750
Jste Fredova jediné dítě.

10
00:00:28,750 --> 00:00:30,950
>> Proč by organizování své rodinné příslušníky tímto způsobem

11
00:00:30,950 --> 00:00:34,010
být lepší než jednoduchého seznamu reprezentaci?

12
00:00:34,010 --> 00:00:36,630
Jedním z důvodů je to, že tato hierarchická struktura,

13
00:00:36,630 --> 00:00:39,660
nazýván "strom," obsahuje více informací než jednoduchý seznam.

14
00:00:40,540 --> 00:00:43,520
Známe rodinné vztahy mezi všemi

15
00:00:43,520 --> 00:00:45,440
jen tím, že zkoumá strom.

16
00:00:45,440 --> 00:00:47,250
Také lze urychlit

17
00:00:47,250 --> 00:00:50,010
look-up čas ohromně, pokud strom data seřazena.

18
00:00:50,010 --> 00:00:53,850
>> Nemůžeme využít, že zde, ale uvidíme příklad tak brzy.

19
00:00:53,850 --> 00:00:56,150
Každý člověk je reprezentován uzlu stromu.

20
00:00:56,680 --> 00:00:58,370
Uzly mohou mít podřízené uzly

21
00:00:58,370 --> 00:01:00,350
stejně jako nadřazeného uzlu.

22
00:01:00,350 --> 00:01:02,390
Jedná se o technické termíny,

23
00:01:02,390 --> 00:01:05,220
i při použití stromy na věci, kromě rodiny.

24
00:01:05,220 --> 00:01:07,940
Alicin uzel má 2 děti a žádné rodiče,

25
00:01:07,940 --> 00:01:11,500
zatímco Charlie uzel má 3 děti a 1 rodič.

26
00:01:11,500 --> 00:01:14,330
>> Koncový uzel je ten, který nemá žádné děti

27
00:01:14,330 --> 00:01:16,410
na vnějším okraji stromu.

28
00:01:16,410 --> 00:01:18,520
Nejvyšší uzel stromu, kořenový uzel,

29
00:01:18,520 --> 00:01:20,240
nemá rodiče.

30
00:01:20,240 --> 00:01:23,170
>> Binární strom je specifický druh stromu,

31
00:01:23,170 --> 00:01:26,720
ve kterém každý uzel má nanejvýš 2 děti.

32
00:01:26,720 --> 00:01:30,490
Zde je struct z uzlu binárního stromu C.

33
00:01:31,560 --> 00:01:34,530
Každý uzel má nějaké údaje s ním spojené

34
00:01:34,530 --> 00:01:36,520
a 2 ukazatele na další uzly.

35
00:01:36,520 --> 00:01:38,110
>> V našem rodokmenu,

36
00:01:38,110 --> 00:01:40,900
přidružené data byla každé jméno osoby.

37
00:01:40,900 --> 00:01:43,850
Zde je to int, i když by to mohlo být cokoliv.

38
00:01:44,510 --> 00:01:46,200
Jak to dopadá,

39
00:01:46,200 --> 00:01:48,990
binární strom by nebylo dobré reprezentace pro rodinu,

40
00:01:48,990 --> 00:01:51,960
protože lidé mají často více než 2 děti.

41
00:01:51,960 --> 00:01:53,510
>> Binární vyhledávací strom

42
00:01:53,510 --> 00:01:56,380
je zvláštní, objednané typ binárního stromu

43
00:01:56,380 --> 00:01:58,090
, který nám umožňuje podívat se na hodnoty rychle.

44
00:01:58,740 --> 00:02:00,050
Možná jste si všimli,

45
00:02:00,050 --> 00:02:02,010
že každý uzel pod kořen stromu

46
00:02:02,010 --> 00:02:04,620
je kořen jiného stromu, tzv. "podstromu."

47
00:02:04,960 --> 00:02:07,090
Zde je kořen stromu je 6,

48
00:02:07,090 --> 00:02:09,860
a její dítě, 2, je kořen podstromu.

49
00:02:09,860 --> 00:02:11,870
>> V binární vyhledávací strom

50
00:02:11,870 --> 00:02:15,790
všechny hodnoty uzlu je pravého podstromu

51
00:02:15,790 --> 00:02:18,690
jsou větší než uzlu hodnoty. Tady: 6.

52
00:02:18,690 --> 00:02:22,640
No, hodnoty v uzlu je levého podstromu

53
00:02:24,540 --> 00:02:26,890
méně než uzlu hodnoty.

54
00:02:26,890 --> 00:02:28,620
Pokud potřebujeme zvládnout duplicitní hodnoty,

55
00:02:28,620 --> 00:02:31,760
můžeme změnit buď z těch, na volné nerovnosti,

56
00:02:31,760 --> 00:02:34,410
což znamená, stejné hodnoty mohou spadat buď na levé nebo pravé,

57
00:02:34,410 --> 00:02:37,400
tak dlouho, jak jsme důslední o tom celé.

58
00:02:37,400 --> 00:02:39,620
Tento strom je binární vyhledávací strom

59
00:02:39,620 --> 00:02:41,540
protože to vyplývá těchto pravidel.

60
00:02:42,320 --> 00:02:46,020
>> To je, jak by to vypadalo, kdyby jsme se obrátili všechny uzly do structs C.

61
00:02:46,880 --> 00:02:48,410
Všimněte si, že pokud dítě chybí,

62
00:02:48,410 --> 00:02:50,340
ukazatel je null.

63
00:02:50,340 --> 00:02:53,270
Jak jsme zkontrolovat, zda 7 je ve stromu?

64
00:02:53,270 --> 00:02:55,020
Začneme u kořene.

65
00:02:55,020 --> 00:02:58,690
Sedm je větší než 6, takže v případě, že je to ve stromu, musí být na pravé straně.

66
00:02:59,680 --> 00:03:03,650
Pak, to je méně než 8, takže musí být vlevo.

67
00:03:03,650 --> 00:03:06,210
Zde jsme zjistili, 7.

68
00:03:06,210 --> 00:03:08,160
Nyní, budeme kontrolovat 5.

69
00:03:08,160 --> 00:03:11,500
Pět je nižší než 6, takže musí být na levé straně.

70
00:03:11,500 --> 00:03:13,460
Pět je větší než 2,

71
00:03:13,460 --> 00:03:15,010
tak to musí být pravda,

72
00:03:15,010 --> 00:03:18,100
a je také větší než 4, takže musí být zase v pořádku.

73
00:03:18,100 --> 00:03:20,300
Je zde však žádné dítě zde.

74
00:03:20,300 --> 00:03:22,000
Ukazatel je null.

75
00:03:22,000 --> 00:03:24,270
To znamená, že 5 není v našem stromu.

76
00:03:24,270 --> 00:03:27,250
>> Můžeme hledat binární strom s následujícím kódem:

77
00:03:28,430 --> 00:03:31,140
Na každém uzlu, můžeme zkontrolovat, zda jsme našli

78
00:03:31,140 --> 00:03:33,020
hodnota, kterou hledáte.

79
00:03:33,020 --> 00:03:35,740
Pokud nenajdeme, jsme zjistit, zda by měl být

80
00:03:35,740 --> 00:03:38,990
vlevo nebo vpravo a zkontrolujte, zda podstromu.

81
00:03:38,990 --> 00:03:41,160
Tato smyčka bude pokračovat na strom

82
00:03:41,160 --> 00:03:44,190
dokud není podřízený uzel buď doleva nebo doprava.

83
00:03:45,190 --> 00:03:48,600
>> Pamatujte si, že 5 není ve stromu.

84
00:03:48,600 --> 00:03:50,460
Jak jsme vložte ji?

85
00:03:50,460 --> 00:03:52,370
Proces vypadá podobně jako vyhledávání.

86
00:03:52,370 --> 00:03:54,830
Jsme iterovat dolů stromem od 6,

87
00:03:54,830 --> 00:03:57,040
ponecháno na 2,

88
00:03:57,040 --> 00:03:59,140
právo na 4,

89
00:03:59,140 --> 00:04:02,500
a znovu doprava, ale 4 nemá dítě na této straně.

90
00:04:02,500 --> 00:04:06,090
To bude nová pozice pro 5,

91
00:04:06,090 --> 00:04:08,500
a začne s žádnými dětmi.

92
00:04:09,020 --> 00:04:12,220
>> Jak rychle se operace binární vyhledávací strom?

93
00:04:12,220 --> 00:04:15,410
Pamatujte si, že Bigohnotation se snaží poskytnout horní mez.

94
00:04:15,410 --> 00:04:17,390
V nejhorším případě,

95
00:04:17,390 --> 00:04:19,480
náš strom by mohl být jednoduše propojený seznam

96
00:04:19,480 --> 00:04:22,220
což znamená, že vkládání, mazání a hledání

97
00:04:22,220 --> 00:04:25,380
může trvat úměrný počtu uzlů ve stromu.

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

99
00:04:27,380 --> 00:04:30,690
>> Například, je následující platné binární vyhledávací strom.

100
00:04:31,850 --> 00:04:34,020
Nicméně, pokud se snažíme najít 9,

101
00:04:34,020 --> 00:04:36,760
musíme přejít každý uzel.

102
00:04:36,760 --> 00:04:39,120
Není to lepší než propojeného seznamu.

103
00:04:39,120 --> 00:04:41,410
V ideálním případě bychom chtěli každý uzel

104
00:04:41,410 --> 00:04:44,120
našeho binárního vyhledávacího stromu mít 2 děti.

105
00:04:44,120 --> 00:04:46,370
Tímto způsobem, vložení, mazání a vyhledávání

106
00:04:46,370 --> 00:04:50,190
by se v nejhorším případě O (log n) času.

107
00:04:50,190 --> 00:04:52,470
Strom z doby před mohly být vyrovnanější,

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

109
00:04:54,140 --> 00:04:57,980
Nyní, hledá nějaké hodnoty trvá nanejvýš 3 kroky.

110
00:04:57,980 --> 00:04:59,460
Tento strom je vyvážený,

111
00:04:59,460 --> 00:05:01,190
to znamená, že je má minimální hloubku

112
00:05:01,190 --> 00:05:03,680
vzhledem k počtu uzlů.

113
00:05:03,680 --> 00:05:06,300
>> Hledáte pro hodnotu ve vyváženém stromu binární hledání

114
00:05:06,300 --> 00:05:09,540
je podobný binární vyhledávání na tříděném poli.

115
00:05:09,540 --> 00:05:12,290
Ve skutečnosti, pokud nebudeme muset vložit nebo odstranit položky,

116
00:05:12,290 --> 00:05:15,150
se chovají úplně stejně.

117
00:05:15,150 --> 00:05:17,600
Nicméně, stromová struktura je lepší

118
00:05:17,600 --> 00:05:19,530
manipulačních vložení a vymazání

119
00:05:20,360 --> 00:05:22,670
>> Mé jméno je Bannus Van der Kloot.

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