1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Kiel vi reprezentas ĉiujn viajn familianojn en komputilo?

2
00:00:10,790 --> 00:00:12,390
Ni povus simple uzi listo,

3
00:00:12,390 --> 00:00:14,400
sed estas klara hierarkio tie.

4
00:00:14,400 --> 00:00:17,110
>> Diru ni komencante kun via praavino, Alice.

5
00:00:17,110 --> 00:00:19,030
Ŝi havas 2 filojn, Bob

6
00:00:19,030 --> 00:00:21,310
kaj via avo, Charlie.

7
00:00:21,310 --> 00:00:23,190
Charlie havas 3 infanojn,

8
00:00:23,190 --> 00:00:26,730
via onklo, Dave, via onklino, Eva, kaj via patro, Fred.

9
00:00:26,730 --> 00:00:28,750
Vi estas Fred nur infano.

10
00:00:28,750 --> 00:00:30,950
>> Kial organizi vian familianoj tiamaniere

11
00:00:30,950 --> 00:00:34,010
esti pli bona ol la simpla listo reprezento?

12
00:00:34,010 --> 00:00:36,630
Unu kialo estas ke tiu hierarkia strukturo,

13
00:00:36,630 --> 00:00:39,660
nomata 'arbo,' enhavas pli da informoj ol simpla listo.

14
00:00:40,540 --> 00:00:43,520
Ni konas la familiara interrilatoj inter ĉiuj

15
00:00:43,520 --> 00:00:45,440
nur ekzameni la arbo.

16
00:00:45,440 --> 00:00:47,250
Ankaŭ, ĝi povas akceli

17
00:00:47,250 --> 00:00:50,010
rigardo-supren tempo terure, se arbo datumoj ordo.

18
00:00:50,010 --> 00:00:53,850
>> Ni ne povas utiligi tiun ĉi tie, sed ni vidos ekzemplon de tiu baldaŭ.

19
00:00:53,850 --> 00:00:56,150
Ĉiu persono estas reprezentita de nodo en la arbo.

20
00:00:56,680 --> 00:00:58,370
Nodoj povas havi infano nodoj

21
00:00:58,370 --> 00:01:00,350
tiel kiel patro nodo.

22
00:01:00,350 --> 00:01:02,390
Tio estas la teknikaj terminoj,

23
00:01:02,390 --> 00:01:05,220
eĉ uzinte arboj por aĵoj krom familii.

24
00:01:05,220 --> 00:01:07,940
Alicia nodo havas 2 infanoj kaj ne gepatroj,

25
00:01:07,940 --> 00:01:11,500
dum Charlie nodo havas 3 filojn kaj 1 patro.

26
00:01:11,500 --> 00:01:14,330
>> Al folio nodo estas unu kiu ne havas ajnan infanoj

27
00:01:14,330 --> 00:01:16,410
sur la ekstera rando de la arbo.

28
00:01:16,410 --> 00:01:18,520
La plejsupra nodo de la arbo, la radiko nodo,

29
00:01:18,520 --> 00:01:20,240
ne havas patro.

30
00:01:20,240 --> 00:01:23,170
>> A duuma arbo estas specifa tipo de arbo,

31
00:01:23,170 --> 00:01:26,720
en kiu ĉiu vertico havas, maksimume, 2 infanojn.

32
00:01:26,720 --> 00:01:30,490
Jen la struct de nodo de duuma arbo en C.

33
00:01:31,560 --> 00:01:34,530
Ĉiu vertico havas iujn datumojn asociitaj al ĝi

34
00:01:34,530 --> 00:01:36,520
kaj 2 punteros al aliaj nodoj.

35
00:01:36,520 --> 00:01:38,110
>> En nia familio arbo,

36
00:01:38,110 --> 00:01:40,900
la asociita datumoj estis ĉiu persono nomo.

37
00:01:40,900 --> 00:01:43,850
Tie estas int, kvankam povus esti io.

38
00:01:44,510 --> 00:01:46,200
Ĉar ĝi rezultas,

39
00:01:46,200 --> 00:01:48,990
duuma arbo ne estus bona reprezento por familio,

40
00:01:48,990 --> 00:01:51,960
ekde homoj ofte havas pli ol 2 infanoj.

41
00:01:51,960 --> 00:01:53,510
>> A duuma serĉarbo

42
00:01:53,510 --> 00:01:56,380
estas speciala, ordigita tipo de duuma arbo

43
00:01:56,380 --> 00:01:58,090
kiu nin permesas rigardi valoroj rapide.

44
00:01:58,740 --> 00:02:00,050
Vi eble rimarkis

45
00:02:00,050 --> 00:02:02,010
ke ĉiu nodo sub la radiko de arbo

46
00:02:02,010 --> 00:02:04,620
estas la radiko de alia arbo, nomata 'subárbol.'

47
00:02:04,960 --> 00:02:07,090
Ĉi tie, la radiko de la arbo estas 6,

48
00:02:07,090 --> 00:02:09,860
kaj lia filo, 2, estas la radiko de subarbo.

49
00:02:09,860 --> 00:02:11,870
>> En duuma serĉarbo

50
00:02:11,870 --> 00:02:15,790
ĉiuj valoroj de nodo pravas subárbol

51
00:02:15,790 --> 00:02:18,690
estas pli grandaj ol la nodo valoron. Ĉi tie: 6.

52
00:02:18,690 --> 00:02:22,640
Nu, la valoroj en nodo la maldekstra subarbo

53
00:02:24,540 --> 00:02:26,890
estas malpli ol la nodo valoron.

54
00:02:26,890 --> 00:02:28,620
Se ni bezonas manipuli duplikatajn valoroj,

55
00:02:28,620 --> 00:02:31,760
ni povas ŝanĝi aŭ de tiuj al malfiksas neegaleco,

56
00:02:31,760 --> 00:02:34,410
signifas identa valoroj povas fali ĉu sur la maldekstra aŭ dekstra,

57
00:02:34,410 --> 00:02:37,400
tiel longe kiel ni estas konsekvenca pri tio tra la tuto.

58
00:02:37,400 --> 00:02:39,620
Ĉi tiu arbo estas duuma serĉarbo

59
00:02:39,620 --> 00:02:41,540
ĉar ĝi sekvas ĉi tiujn regulojn.

60
00:02:42,320 --> 00:02:46,020
>> Tiel estas kiel ĝi aspektus se ni turnis ĉiuj nodoj en C structs.

61
00:02:46,880 --> 00:02:48,410
Rimarku ke se infano mankas,

62
00:02:48,410 --> 00:02:50,340
la puntero estas nula.

63
00:02:50,340 --> 00:02:53,270
Kiel ni kontrolu vidi se 7 estas en la arbo?

64
00:02:53,270 --> 00:02:55,020
Ni komencu ĉe la radiko.

65
00:02:55,020 --> 00:02:58,690
Sep estas pli granda ol 6, do se estas en la arbo, ĝi devas esti por la rajto.

66
00:02:59,680 --> 00:03:03,650
Tiam, ĝi estas malpli ol 8, do ĝi devas esti forlasita.

67
00:03:03,650 --> 00:03:06,210
Jen, ni trovis 7.

68
00:03:06,210 --> 00:03:08,160
Nun, ni kontrolu por 5.

69
00:03:08,160 --> 00:03:11,500
Kvin estas malpli ol 6, do ĝi devas esti al la maldekstra.

70
00:03:11,500 --> 00:03:13,460
Kvin estas pli granda ol 2,

71
00:03:13,460 --> 00:03:15,010
do ĝi devas esti ĝuste,

72
00:03:15,010 --> 00:03:18,100
kaj ĝi estas ankaŭ pli granda ol 4, do ĝi devas esti ĝuste denove.

73
00:03:18,100 --> 00:03:20,300
Tamen, ne estas infano tie.

74
00:03:20,300 --> 00:03:22,000
La montrilo estas nula.

75
00:03:22,000 --> 00:03:24,270
Tio signifas ke 5 ne estas en niaj arbo.

76
00:03:24,270 --> 00:03:27,250
>> Ni povas serĉi la duuma arbo kun la sekva kodo:

77
00:03:28,430 --> 00:03:31,140
Je ĉiu vertico, ni kontrolu vidi se ni trovis

78
00:03:31,140 --> 00:03:33,020
la valoron ni serĉas.

79
00:03:33,020 --> 00:03:35,740
Se ni ne trovos ĝin, ni determini se ĝi devus esti

80
00:03:35,740 --> 00:03:38,990
sur la maldekstra aŭ dekstra kaj kontroli, ke subárbol.

81
00:03:38,990 --> 00:03:41,160
Ĉi buklo daŭrigos laŭ la arbo

82
00:03:41,160 --> 00:03:44,190
ĝis estas ne infano nodo sur ĉu la maldekstra aŭ dekstra.

83
00:03:45,190 --> 00:03:48,600
>> Memoru ke 5 ne estis en la arbo.

84
00:03:48,600 --> 00:03:50,460
Kiel ni enŝovu ĝin?

85
00:03:50,460 --> 00:03:52,370
La procezo aspektas simila al serĉi.

86
00:03:52,370 --> 00:03:54,830
Ni persisti malsupren la arbo ekde 6,

87
00:03:54,830 --> 00:03:57,040
forlasis al 2,

88
00:03:57,040 --> 00:03:59,140
rajton 4,

89
00:03:59,140 --> 00:04:02,500
kaj dekstra denove, sed 4 havas ne infanon sur tiu flanko.

90
00:04:02,500 --> 00:04:06,090
Ĉi tiu estos la nova pozicio por 5,

91
00:04:06,090 --> 00:04:08,500
kaj komencos sen infanoj.

92
00:04:09,020 --> 00:04:12,220
>> Kiel rapida estas la operacioj en duuma serĉo arbo?

93
00:04:12,220 --> 00:04:15,410
Memoru ke Bigohnotation celas provizi supera baro.

94
00:04:15,410 --> 00:04:17,390
En la plej malbona kazo,

95
00:04:17,390 --> 00:04:19,480
nia arbo eblus simple lerta kunligita

96
00:04:19,480 --> 00:04:22,220
signifante ke inserción, forigo, kaj serĉo

97
00:04:22,220 --> 00:04:25,380
povus preni tempon proporcia al la nombro de nodoj en la arbo.

98
00:04:25,380 --> 00:04:27,380
Tiu estas O (n).

99
00:04:27,380 --> 00:04:30,690
>> Ekzemple, jeno estas valida duuma serĉarbo.

100
00:04:31,850 --> 00:04:34,020
Tamen, se ni provos trovi 9,

101
00:04:34,020 --> 00:04:36,760
ni devas trairi ĉiu nodo.

102
00:04:36,760 --> 00:04:39,120
Ĝi estas pli bona ol ligitaj listo.

103
00:04:39,120 --> 00:04:41,410
Ideale, ni volus ĉiu nodo

104
00:04:41,410 --> 00:04:44,120
de nia duuma serĉarbo havi 2 idoj.

105
00:04:44,120 --> 00:04:46,370
Tiamaniere, inserción, forigo kaj serĉo

106
00:04:46,370 --> 00:04:50,190
prenus, en la plej malbona, O (logo n) tempo.

107
00:04:50,190 --> 00:04:52,470
La arbo de antaŭ povus esti pli ekvilibrigita,

108
00:04:52,470 --> 00:04:54,140
kiel ĉi tio.

109
00:04:54,140 --> 00:04:57,980
Nun, supren rigardante neniun valoron portas, maksimume, 3 paŝoj.

110
00:04:57,980 --> 00:04:59,460
Ĉi tiu arbo estas ekvilibra,

111
00:04:59,460 --> 00:05:01,190
signifo kiu estas havas minimuman profundo

112
00:05:01,190 --> 00:05:03,680
relativa al la nombro de nodoj.

113
00:05:03,680 --> 00:05:06,300
>> Serĉante valoro en ekvilibran duuma serĉarbo

114
00:05:06,300 --> 00:05:09,540
estas simila al duuma serĉo sur ordo tabelo.

115
00:05:09,540 --> 00:05:12,290
Fakte, se ni ne bezonas enmeti aŭ forviŝi erojn,

116
00:05:12,290 --> 00:05:15,150
ili kondutas ekzakte la sama maniero.

117
00:05:15,150 --> 00:05:17,600
Tamen, arbo strukturo estas pli bona

118
00:05:17,600 --> 00:05:19,530
por uzado inserciones kaj forigoj

119
00:05:20,360 --> 00:05:22,670
>> Mia nomo estas Bannus Van der Kloot.

120
00:05:22,670 --> 00:05:24,030
Ĉi tiu estas CS50.