1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Kouman ou ta reprezante tout manm fanmi an ou a nan yon òdinatè?

2
00:00:10,790 --> 00:00:12,390
Nou te ka tou senpleman itilize yon lis,

3
00:00:12,390 --> 00:00:14,400
, men tou genyen yon yerachi klè isit la.

4
00:00:14,400 --> 00:00:17,110
>> Se pou nou di nou ap kòmanse ak grann gwo-ou a, Alice.

5
00:00:17,110 --> 00:00:19,030
Li te gen 2 Men pitit gason, Bob

6
00:00:19,030 --> 00:00:21,310
ak granpè ou a, Charlie.

7
00:00:21,310 --> 00:00:23,190
Charlie gen 3 timoun yo,

8
00:00:23,190 --> 00:00:26,730
tonton ou a, Dave, matant ou a, Èv, e papa ou, Fred.

9
00:00:26,730 --> 00:00:28,750
Ou yo, se sèlman pitit Fred a.

10
00:00:28,750 --> 00:00:30,950
>> Poukisa ta òganize manm fanmi ou nan fason sa a

11
00:00:30,950 --> 00:00:34,010
ka pi bon pase reprezantasyon nan lis ki senp?

12
00:00:34,010 --> 00:00:36,630
Youn nan rezon ki se ke estrikti sa a yerarchize,

13
00:00:36,630 --> 00:00:39,660
yo te rele yon 'pye bwa,' gen enfòmasyon pi plis pase yon lis ki senp.

14
00:00:40,540 --> 00:00:43,520
Nou konnen relasyon ki genyen ant familyal tout moun

15
00:00:43,520 --> 00:00:45,440
jis pa ekzamine pyebwa sa a.

16
00:00:45,440 --> 00:00:47,250
Epitou, li ka pi vit

17
00:00:47,250 --> 00:00:50,010
gade-up tan anpil, si done pyebwa se Klase.

18
00:00:50,010 --> 00:00:53,850
>> Nou pa kapab pran avantaj de ki isit la, men nou pral wè yon egzanp sou sa byento.

19
00:00:53,850 --> 00:00:56,150
Chak moun reprezante pa yon ne sou pyebwa sa a.

20
00:00:56,680 --> 00:00:58,370
Nœuds ka gen nœuds pitit

21
00:00:58,370 --> 00:01:00,350
kòm osi byen yon ne paran yo.

22
00:01:00,350 --> 00:01:02,390
Sa yo se kondisyon ki teknik,

23
00:01:02,390 --> 00:01:05,220
menm lè lè l sèvi avèk pye bwa pou bagay sa yo san konte fanmi yo.

24
00:01:05,220 --> 00:01:07,940
Ne Alice an gen 2 timoun yo ak pa gen okenn paran yo,

25
00:01:07,940 --> 00:01:11,500
pandan y ap ne Charlie a gen 3 timoun yo ak paran 1.

26
00:01:11,500 --> 00:01:14,330
>> Yon ne fèy se youn ki pa gen okenn timoun yo

27
00:01:14,330 --> 00:01:16,410
sou kwen deyò an nan pyebwa sa a.

28
00:01:16,410 --> 00:01:18,520
Ne nan topmost nan pyebwa a, ne nan rasin,

29
00:01:18,520 --> 00:01:20,240
pa gen okenn paran yo.

30
00:01:20,240 --> 00:01:23,170
>> Yon pye bwa binè se yon kalite espesifik nan pye bwa yo,

31
00:01:23,170 --> 00:01:26,720
kote chak ne gen, nan pi, 2 timoun yo.

32
00:01:26,720 --> 00:01:30,490
Isit la se struct a nan yon ne nan yon pyebwa binè nan C.

33
00:01:31,560 --> 00:01:34,530
Chak ne gen kèk done ki asosye ak li

34
00:01:34,530 --> 00:01:36,520
ak 2 endikasyon nœuds lòt.

35
00:01:36,520 --> 00:01:38,110
>> Nan pye bwa fanmi nou an,

36
00:01:38,110 --> 00:01:40,900
done ki asosye te non chak moun nan.

37
00:01:40,900 --> 00:01:43,850
Men li se yon int, menm si li te kapab anyen.

38
00:01:44,510 --> 00:01:46,200
Kòm li vire soti,

39
00:01:46,200 --> 00:01:48,990
yon pye bwa binè pa ta dwe yon reprezantasyon bon pou yon fanmi,

40
00:01:48,990 --> 00:01:51,960
depi moun souvan gen plis pase 2 timoun yo.

41
00:01:51,960 --> 00:01:53,510
>> Yon pye bwa rechèch binè

42
00:01:53,510 --> 00:01:56,380
se yon espesyal, ki kalite lòd nan pyebwa binè

43
00:01:56,380 --> 00:01:58,090
ki pèmèt nou fè yon gade nan valè byen vit.

44
00:01:58,740 --> 00:02:00,050
Ou ka remake gen

45
00:02:00,050 --> 00:02:02,010
ke chak ne pi ba a rasin nan yon pye bwa

46
00:02:02,010 --> 00:02:04,620
se rasin lan yon lòt pye bwa yo, yo te rele yon 'subtree.

47
00:02:04,960 --> 00:02:07,090
Isit la, rasin pyebwa a se 6,

48
00:02:07,090 --> 00:02:09,860
ak pitit li yo, 2, se rasin lan nan yon subtree.

49
00:02:09,860 --> 00:02:11,870
>> Nan yon pyebwa rechèch binè

50
00:02:11,870 --> 00:02:15,790
tout valè sa yo nan yon ne nan dwa subtree

51
00:02:15,790 --> 00:02:18,690
se pi gran pase valè ne la. Mwen: 6.

52
00:02:18,690 --> 00:02:22,640
Oke, valè yo nan subtree gòch yon ne a

53
00:02:24,540 --> 00:02:26,890
yo gen mwens pase valè ne la.

54
00:02:26,890 --> 00:02:28,620
Si nou bezwen okipe valè kopi,

55
00:02:28,620 --> 00:02:31,760
nou kapab chanje swa nan sa yo nan yon inegalite ki lach,

56
00:02:31,760 --> 00:02:34,410
sa vle di valè idantik ka tonbe swa sou bò gòch la oswa dwa,

57
00:02:34,410 --> 00:02:37,400
osi lontan ke nou se konsistan sou li nan tout.

58
00:02:37,400 --> 00:02:39,620
Pyebwa sa a se yon pye bwa rechèch binè

59
00:02:39,620 --> 00:02:41,540
paske li swiv règleman sa yo.

60
00:02:42,320 --> 00:02:46,020
>> Sa a se li montre kouman li ta gade si nou vire tout nœuds yo nan C strukt.

61
00:02:46,880 --> 00:02:48,410
Remake si gen yon timoun ki manke,

62
00:02:48,410 --> 00:02:50,340
konsèy la se nil.

63
00:02:50,340 --> 00:02:53,270
Ki jan nou tcheke yo wè si 7 se nan pye bwa a?

64
00:02:53,270 --> 00:02:55,020
Nou kòmanse nan rasin lan.

65
00:02:55,020 --> 00:02:58,690
Sèt pi gran pase 6, kidonk si li nan nan pye bwa a, li dwe a dwat la.

66
00:02:59,680 --> 00:03:03,650
Lè sa a,, li se pi piti pase 8, ki fè li dwe kite.

67
00:03:03,650 --> 00:03:06,210
Isit la, nou te jwenn 7.

68
00:03:06,210 --> 00:03:08,160
Koulye a, nou pral tcheke pou 5.

69
00:03:08,160 --> 00:03:11,500
Senk gen mwens pase 6, se konsa li dwe a gòch la.

70
00:03:11,500 --> 00:03:13,460
Senk gen plis pouvwa pase 2,

71
00:03:13,460 --> 00:03:15,010
se konsa li dwe dwat,

72
00:03:15,010 --> 00:03:18,100
ak li se tou pi gran pase 4, se konsa li dwe dwe gen dwa ankò.

73
00:03:18,100 --> 00:03:20,300
Sepandan, pa gen okenn pitit isit la.

74
00:03:20,300 --> 00:03:22,000
Konsèy la se nil.

75
00:03:22,000 --> 00:03:24,270
Sa vle di ke 5 se pa nan pyebwa nou yo.

76
00:03:24,270 --> 00:03:27,250
>> Nou kapab fè rechèch pye bwa a binè ak kòd la sa yo:

77
00:03:28,430 --> 00:03:31,140
Nan chak ne, nou tcheke yo wè si nou jwenn

78
00:03:31,140 --> 00:03:33,020
valè a nou ap chèche pou.

79
00:03:33,020 --> 00:03:35,740
Si nou pa jwenn li, nou detèmine si li ta dwe

80
00:03:35,740 --> 00:03:38,990
sou yo ak sou gòch la oswa dwa tcheke ki subtree.

81
00:03:38,990 --> 00:03:41,160
Sa a riban ap kontinye desann pye bwa a

82
00:03:41,160 --> 00:03:44,190
jiskaske pa genyen okenn ne timoun ki sou swa bò gòch la oswa dwa.

83
00:03:45,190 --> 00:03:48,600
>> Sonje ke 5 pa t 'nan pyebwa sa a.

84
00:03:48,600 --> 00:03:50,460
Ki jan nou insert li?

85
00:03:50,460 --> 00:03:52,370
Pwosesis la sanble menm jan nan rechèch.

86
00:03:52,370 --> 00:03:54,830
Nou répétèr desann pye bwa a kòmanse nan 6,

87
00:03:54,830 --> 00:03:57,040
kite a 2,

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

89
00:03:59,140 --> 00:04:02,500
e yo gen dwa ankò, men 4 pa gen okenn timoun ki sou bò sa a.

90
00:04:02,500 --> 00:04:06,090
Sa a pral pozisyon nan nouvo pou 5,

91
00:04:06,090 --> 00:04:08,500
epi li pral kòmanse ki pa gen okenn timoun yo.

92
00:04:09,020 --> 00:04:12,220
>> Konbyen vit yo se operasyon a nan yon pyebwa rechèch binè?

93
00:04:12,220 --> 00:04:15,410
Sonje ke Bigohnotation ap chèche bay yon mare anwo kay la.

94
00:04:15,410 --> 00:04:17,390
Nan ka ki pi mal la,

95
00:04:17,390 --> 00:04:19,480
pyebwa nou te kapab tou senpleman gen yon lis lye

96
00:04:19,480 --> 00:04:22,220
sa vle di ensèsyon, sipresyon, ak rechèch

97
00:04:22,220 --> 00:04:25,380
te kapab pran tan pwopòsyonèl ak kantite nœuds nan pyebwa sa a.

98
00:04:25,380 --> 00:04:27,380
Sa a se O (n).

99
00:04:27,380 --> 00:04:30,690
>> Pou egzanp, sa ki annapre yo se yon binè pyebwa ki valab rechèch.

100
00:04:31,850 --> 00:04:34,020
Sepandan, si nou eseye jwenn 9,

101
00:04:34,020 --> 00:04:36,760
nou dwe Traverse chak ne.

102
00:04:36,760 --> 00:04:39,120
Li pa gen okenn pi bon pase yon lis lye.

103
00:04:39,120 --> 00:04:41,410
Idealman, nou ta vle chak ne

104
00:04:41,410 --> 00:04:44,120
nan pyebwa rechèch binè nou yo gen 2 timoun yo.

105
00:04:44,120 --> 00:04:46,370
Fason sa a, ensèsyon, sipresyon ak rechèch

106
00:04:46,370 --> 00:04:50,190
ta pran, nan pi move, O (boutèy demi lit n) tan.

107
00:04:50,190 --> 00:04:52,470
Pyebwa ki sou devan ka pi balanse,

108
00:04:52,470 --> 00:04:54,140
tankou sa a.

109
00:04:54,140 --> 00:04:57,980
Koulye a, leve je l 'nenpòt ki valè pran, nan pifò, 3 etap.

110
00:04:57,980 --> 00:04:59,460
Pyebwa sa a se balanse,

111
00:04:59,460 --> 00:05:01,190
siyifikasyon bagay ki se gen yon pwofondè minimòm

112
00:05:01,190 --> 00:05:03,680
relatif nan ki kantite nœuds.

113
00:05:03,680 --> 00:05:06,300
>> Ap chèche pou yon valè nan yon pyebwa rechèch binè balanse

114
00:05:06,300 --> 00:05:09,540
se menm jan ak rechèch binè sou yon etalaj Ranje.

115
00:05:09,540 --> 00:05:12,290
An reyalite, si nou pa bezwen insert oswa efase atik,

116
00:05:12,290 --> 00:05:15,150
yo konpòte egzakteman menm jan an.

117
00:05:15,150 --> 00:05:17,600
Sepandan, yon estrikti pye bwa se pi bon

118
00:05:17,600 --> 00:05:19,530
pou parusyon manyen ak reyur

119
00:05:20,360 --> 00:05:22,670
>> Non mwen se Bannus van der Kloot.

120
00:05:22,670 --> 00:05:24,030
Sa a se CS50.