1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Sut fyddech chi'n cynrychioli eich holl aelodau'r teulu mewn cyfrifiadur?

2
00:00:10,790 --> 00:00:12,390
Gallem syml defnyddio rhestr,

3
00:00:12,390 --> 00:00:14,400
ond mae yna hierarchaeth glir yma.

4
00:00:14,400 --> 00:00:17,110
>> Lets 'ddeud rydym yn dechrau gyda eich hen-nain, Alice.

5
00:00:17,110 --> 00:00:19,030
Mae ganddi 2 fab, Bob

6
00:00:19,030 --> 00:00:21,310
a'ch taid, Charlie.

7
00:00:21,310 --> 00:00:23,190
Charlie Mae 3 o blant,

8
00:00:23,190 --> 00:00:26,730
eich ewythr, Dave, eich modryb, Eve, a dy dad, Fred.

9
00:00:26,730 --> 00:00:28,750
Rydych chi Fred plentyn yn unig.

10
00:00:28,750 --> 00:00:30,950
>> Pam y byddai trefnu eich aelodau o'r teulu yn y ffordd hon

11
00:00:30,950 --> 00:00:34,010
fod yn well na'r cynrychiolaeth rhestr syml?

12
00:00:34,010 --> 00:00:36,630
Un rheswm yw bod y strwythur hierarchaidd,

13
00:00:36,630 --> 00:00:39,660
a elwir yn 'goeden,' yn cynnwys mwy o wybodaeth na rhestr syml.

14
00:00:40,540 --> 00:00:43,520
Rydym yn gwybod y berthynas deuluol rhwng pawb

15
00:00:43,520 --> 00:00:45,440
dim ond drwy edrych ar y goeden.

16
00:00:45,440 --> 00:00:47,250
Hefyd, gall gyflymu'r

17
00:00:47,250 --> 00:00:50,010
edrych i fyny amser hynod, os data goeden yn cael ei datrys.

18
00:00:50,010 --> 00:00:53,850
>> Ni allwn gymryd mantais o hynny yma, ond byddwn yn gweld enghraifft o hyn yn fuan.

19
00:00:53,850 --> 00:00:56,150
Mae pob person yn cael ei gynrychioli gan nod ar y goeden.

20
00:00:56,680 --> 00:00:58,370
Gall nodau gael nodau blant

21
00:00:58,370 --> 00:01:00,350
yn ogystal â nod rhiant.

22
00:01:00,350 --> 00:01:02,390
Y rhain yw'r termau technegol,

23
00:01:02,390 --> 00:01:05,220
hyd yn oed wrth ddefnyddio coed ar gyfer pethau ar wahân i deuluoedd.

24
00:01:05,220 --> 00:01:07,940
Alice Does gan y nod 2 o blant ac nid oes unrhyw rieni,

25
00:01:07,940 --> 00:01:11,500
tra bod Charlie yn nod gan 3 o blant ac 1 rhiant.

26
00:01:11,500 --> 00:01:14,330
>> Mae nod deilen yw un nad oes ganddo unrhyw blant

27
00:01:14,330 --> 00:01:16,410
ar ymyl allanol y goeden.

28
00:01:16,410 --> 00:01:18,520
Mae'r nod topmost y goeden, y nod gwraidd,

29
00:01:18,520 --> 00:01:20,240
Nid oes gan riant.

30
00:01:20,240 --> 00:01:23,170
>> Mae coeden ddeuaidd yn fath penodol o goed,

31
00:01:23,170 --> 00:01:26,720
lle mae pob Does gan y nod ar y mwyaf, 2 o blant.

32
00:01:26,720 --> 00:01:30,490
Dyma strwythur o nod o goeden ddeuaidd yn C.

33
00:01:31,560 --> 00:01:34,530
Mae pob nod rai data sy'n gysylltiedig ag ef

34
00:01:34,530 --> 00:01:36,520
a 2 awgrymiadau i nodau eraill.

35
00:01:36,520 --> 00:01:38,110
>> Yn ein coeden deulu,

36
00:01:38,110 --> 00:01:40,900
y data cysylltiedig yn enw pob person.

37
00:01:40,900 --> 00:01:43,850
Dyma hi yn int, er y gallai fod yn unrhyw beth.

38
00:01:44,510 --> 00:01:46,200
Fel mae'n digwydd,

39
00:01:46,200 --> 00:01:48,990
Ni fyddai goeden ddeuol fod cynrychiolaeth dda i deulu,

40
00:01:48,990 --> 00:01:51,960
gan fod pobl yn aml yn cael mwy na 2 o blant.

41
00:01:51,960 --> 00:01:53,510
>> Mae deuaidd coed chwilio

42
00:01:53,510 --> 00:01:56,380
yn arbennig, math trefnus o goeden ddeuaidd

43
00:01:56,380 --> 00:01:58,090
sy'n ein galluogi i edrych ar werthoedd yn gyflym.

44
00:01:58,740 --> 00:02:00,050
Efallai eich bod wedi sylwi

45
00:02:00,050 --> 00:02:02,010
bod pob nod yn is na gwreiddyn coeden

46
00:02:02,010 --> 00:02:04,620
yw'r gwraidd goeden arall, a elwir yn 'Terfynau Chwilio.'

47
00:02:04,960 --> 00:02:07,090
Yma, wrth wraidd y goeden yw 6,

48
00:02:07,090 --> 00:02:09,860
a'i phlentyn, 2, yw gwraidd o Terfynau Chwilio.

49
00:02:09,860 --> 00:02:11,870
>> Mewn coeden chwiliad deuaidd

50
00:02:11,870 --> 00:02:15,790
holl werthoedd y nod yn iawn Terfynau Chwilio

51
00:02:15,790 --> 00:02:18,690
yn fwy na gwerth y nod yn. Yma: 6.

52
00:02:18,690 --> 00:02:22,640
Wel, y gwerthoedd mewn Terfynau Chwilio yn nod y chwith

53
00:02:24,540 --> 00:02:26,890
yn llai na gwerth y nod yn.

54
00:02:26,890 --> 00:02:28,620
Os bydd angen i ymdrin â gwerthoedd dyblyg,

55
00:02:28,620 --> 00:02:31,760
gallwn ni newid naill ai o'r rhai anghydraddoldeb rhydd,

56
00:02:31,760 --> 00:02:34,410
sy'n golygu y gall gwerthoedd union yr un fath yn syrthio naill ai ar y chwith neu i'r dde,

57
00:02:34,410 --> 00:02:37,400
cyn belled ag yr ydym yn gyson yn ei gylch trwy gydol.

58
00:02:37,400 --> 00:02:39,620
Mae'r goeden hon yn goeden chwiliad deuaidd

59
00:02:39,620 --> 00:02:41,540
oherwydd ei fod yn dilyn y rheolau hyn.

60
00:02:42,320 --> 00:02:46,020
>> Dyma sut y byddai'n edrych os byddwn yn troi pob un o'r nodau i mewn i structs C.

61
00:02:46,880 --> 00:02:48,410
Sylwch fod os yw plentyn ar goll,

62
00:02:48,410 --> 00:02:50,340
y pwyntydd yn null.

63
00:02:50,340 --> 00:02:53,270
Sut rydym yn gwirio i weld os 7 ar y goeden?

64
00:02:53,270 --> 00:02:55,020
Rydym yn dechrau yn y gwraidd.

65
00:02:55,020 --> 00:02:58,690
Saith yn fwy na 6, felly os 'i' yn y goeden, rhaid iddo fod ar y dde.

66
00:02:59,680 --> 00:03:03,650
Yna, mae'n llai nag 8, felly mae'n rhaid ei adael.

67
00:03:03,650 --> 00:03:06,210
Yma, rydym wedi dod o hyd 7.

68
00:03:06,210 --> 00:03:08,160
Yn awr, byddwn yn gwirio am 5.

69
00:03:08,160 --> 00:03:11,500
Bump oed yn llai na 6, felly rhaid iddo fod ar y chwith.

70
00:03:11,500 --> 00:03:13,460
Bump oed yn fwy na 2,

71
00:03:13,460 --> 00:03:15,010
felly mae'n rhaid iddo fod yn iawn,

72
00:03:15,010 --> 00:03:18,100
ac mae hefyd yn fwy na 4, felly mae'n rhaid iddo fod yn iawn eto.

73
00:03:18,100 --> 00:03:20,300
Fodd bynnag, nid oes unrhyw blentyn yma.

74
00:03:20,300 --> 00:03:22,000
Mae'r pwyntydd yn null.

75
00:03:22,000 --> 00:03:24,270
Mae hyn yn golygu bod 5 nid yw yn ein coeden.

76
00:03:24,270 --> 00:03:27,250
>> Gallwn chwilio y goeden ddeuaidd gyda'r cod canlynol:

77
00:03:28,430 --> 00:03:31,140
Ar bob nod, rydym yn gwirio i weld os ydym wedi dod o hyd

78
00:03:31,140 --> 00:03:33,020
y gwerth yr ydym yn chwilio amdano.

79
00:03:33,020 --> 00:03:35,740
Os nad ydym yn ei chael yn, rydym yn penderfynu os dylai fod yn

80
00:03:35,740 --> 00:03:38,990
ar y a chwith neu i'r dde gwirio bod Terfynau Chwilio.

81
00:03:38,990 --> 00:03:41,160
Bydd y ddolen yn parhau i lawr y goeden

82
00:03:41,160 --> 00:03:44,190
hyd nes nad oes nod blentyn naill ai ar y chwith neu i'r dde.

83
00:03:45,190 --> 00:03:48,600
>> Cofiwch nad oedd 5 yn y goeden.

84
00:03:48,600 --> 00:03:50,460
Sut ydym yn mewnosod ei?

85
00:03:50,460 --> 00:03:52,370
Mae'r broses yn edrych yn debyg i chwilio.

86
00:03:52,370 --> 00:03:54,830
Rydym yn ailadrodd i lawr y goeden sy'n dechrau o 6,

87
00:03:54,830 --> 00:03:57,040
gadael i 2,

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

89
00:03:59,140 --> 00:04:02,500
ac i'r dde eto, ond 4 Nid oes gan blentyn ar yr ochr hon.

90
00:04:02,500 --> 00:04:06,090
Bydd hyn yn y sefyllfa newydd ar gyfer 5,

91
00:04:06,090 --> 00:04:08,500
a bydd yn dechrau heb blant.

92
00:04:09,020 --> 00:04:12,220
>> Pa mor gyflym mae gweithrediadau ar goeden chwiliad deuaidd?

93
00:04:12,220 --> 00:04:15,410
Cofiwch fod Bigohnotation yn ceisio rhoi rwymo uchaf.

94
00:04:15,410 --> 00:04:17,390
Yn yr achos gwaethaf,

95
00:04:17,390 --> 00:04:19,480
gallai ein coeden yn syml fod yn rhestr cysylltiedig

96
00:04:19,480 --> 00:04:22,220
sy'n golygu bod mewnosod, dileu, a chwilio

97
00:04:22,220 --> 00:04:25,380
Gallai cymryd amser gymesur â nifer y nodau yn y goeden.

98
00:04:25,380 --> 00:04:27,380
Mae hyn yn O (n).

99
00:04:27,380 --> 00:04:30,690
>> Er enghraifft, mae'r canlynol yn goeden ddeuaidd chwilio dilys.

100
00:04:31,850 --> 00:04:34,020
Fodd bynnag, os ydym yn ceisio dod o hyd i 9,

101
00:04:34,020 --> 00:04:36,760
mae'n rhaid i ni deithio ar draws pob nod.

102
00:04:36,760 --> 00:04:39,120
Nid yw'n well na rhestr cysylltiedig.

103
00:04:39,120 --> 00:04:41,410
Yn ddelfrydol, byddem am i bob nod

104
00:04:41,410 --> 00:04:44,120
o'n chwiliad deuaidd coed i 2 o blant.

105
00:04:44,120 --> 00:04:46,370
Mae hyn yn ffordd, mewnosod, dileu a chwilio

106
00:04:46,370 --> 00:04:50,190
Byddai cymryd, ar y gwaethaf, O (n log) amser.

107
00:04:50,190 --> 00:04:52,470
Gallai'r goeden o flaen fod yn fwy cytbwys,

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

109
00:04:54,140 --> 00:04:57,980
Yn awr, gan edrych i fyny unrhyw werth cymryd, ar y mwyaf, 3 camau.

110
00:04:57,980 --> 00:04:59,460
Mae'r goeden hon yn gytbwys,

111
00:04:59,460 --> 00:05:01,190
ystyr bod ganddi dyfnder lleiaf posibl

112
00:05:01,190 --> 00:05:03,680
o'i gymharu â nifer y nodau.

113
00:05:03,680 --> 00:05:06,300
>> Chwilio am werth mewn coeden chwiliad deuaidd cytbwys

114
00:05:06,300 --> 00:05:09,540
yn debyg i chwilio deuaidd ar amrywiaeth datrys.

115
00:05:09,540 --> 00:05:12,290
Yn wir, os nad oes angen i ni mewnosod neu ddileu eitemau,

116
00:05:12,290 --> 00:05:15,150
maent yn ymddwyn yn union yr un ffordd.

117
00:05:15,150 --> 00:05:17,600
Fodd bynnag, mae strwythur coeden yn well

118
00:05:17,600 --> 00:05:19,530
am fewnosodiadau a dileadau trin

119
00:05:20,360 --> 00:05:22,670
>> Fy enw i yw Bannus Van der Kloot.

120
00:05:22,670 --> 00:05:24,030
Mae hyn yn CS50.