[Powered by Google Translate] Sut fyddech chi'n cynrychioli eich holl aelodau'r teulu mewn cyfrifiadur?
Gallem syml defnyddio rhestr,
ond mae yna hierarchaeth glir yma.
>> Lets 'ddeud rydym yn dechrau gyda eich hen-nain, Alice.
Mae ganddi 2 fab, Bob
a'ch taid, Charlie.
Charlie Mae 3 o blant,
eich ewythr, Dave, eich modryb, Eve, a dy dad, Fred.
Rydych chi Fred plentyn yn unig.
>> Pam y byddai trefnu eich aelodau o'r teulu yn y ffordd hon
fod yn well na'r cynrychiolaeth rhestr syml?
Un rheswm yw bod y strwythur hierarchaidd,
a elwir yn 'goeden,' yn cynnwys mwy o wybodaeth na rhestr syml.
Rydym yn gwybod y berthynas deuluol rhwng pawb
dim ond drwy edrych ar y goeden.
Hefyd, gall gyflymu'r
edrych i fyny amser hynod, os data goeden yn cael ei datrys.
>> Ni allwn gymryd mantais o hynny yma, ond byddwn yn gweld enghraifft o hyn yn fuan.
Mae pob person yn cael ei gynrychioli gan nod ar y goeden.
Gall nodau gael nodau blant
yn ogystal â nod rhiant.
Y rhain yw'r termau technegol,
hyd yn oed wrth ddefnyddio coed ar gyfer pethau ar wahân i deuluoedd.
Alice Does gan y nod 2 o blant ac nid oes unrhyw rieni,
tra bod Charlie yn nod gan 3 o blant ac 1 rhiant.
>> Mae nod deilen yw un nad oes ganddo unrhyw blant
ar ymyl allanol y goeden.
Mae'r nod topmost y goeden, y nod gwraidd,
Nid oes gan riant.
>> Mae coeden ddeuaidd yn fath penodol o goed,
lle mae pob Does gan y nod ar y mwyaf, 2 o blant.
Dyma strwythur o nod o goeden ddeuaidd yn C.
Mae pob nod rai data sy'n gysylltiedig ag ef
a 2 awgrymiadau i nodau eraill.
>> Yn ein coeden deulu,
y data cysylltiedig yn enw pob person.
Dyma hi yn int, er y gallai fod yn unrhyw beth.
Fel mae'n digwydd,
Ni fyddai goeden ddeuol fod cynrychiolaeth dda i deulu,
gan fod pobl yn aml yn cael mwy na 2 o blant.
>> Mae deuaidd coed chwilio
yn arbennig, math trefnus o goeden ddeuaidd
sy'n ein galluogi i edrych ar werthoedd yn gyflym.
Efallai eich bod wedi sylwi
bod pob nod yn is na gwreiddyn coeden
yw'r gwraidd goeden arall, a elwir yn 'Terfynau Chwilio.'
Yma, wrth wraidd y goeden yw 6,
a'i phlentyn, 2, yw gwraidd o Terfynau Chwilio.
>> Mewn coeden chwiliad deuaidd
holl werthoedd y nod yn iawn Terfynau Chwilio
yn fwy na gwerth y nod yn. Yma: 6.
Wel, y gwerthoedd mewn Terfynau Chwilio yn nod y chwith
yn llai na gwerth y nod yn.
Os bydd angen i ymdrin â gwerthoedd dyblyg,
gallwn ni newid naill ai o'r rhai anghydraddoldeb rhydd,
sy'n golygu y gall gwerthoedd union yr un fath yn syrthio naill ai ar y chwith neu i'r dde,
cyn belled ag yr ydym yn gyson yn ei gylch trwy gydol.
Mae'r goeden hon yn goeden chwiliad deuaidd
oherwydd ei fod yn dilyn y rheolau hyn.
>> Dyma sut y byddai'n edrych os byddwn yn troi pob un o'r nodau i mewn i structs C.
Sylwch fod os yw plentyn ar goll,
y pwyntydd yn null.
Sut rydym yn gwirio i weld os 7 ar y goeden?
Rydym yn dechrau yn y gwraidd.
Saith yn fwy na 6, felly os 'i' yn y goeden, rhaid iddo fod ar y dde.
Yna, mae'n llai nag 8, felly mae'n rhaid ei adael.
Yma, rydym wedi dod o hyd 7.
Yn awr, byddwn yn gwirio am 5.
Bump oed yn llai na 6, felly rhaid iddo fod ar y chwith.
Bump oed yn fwy na 2,
felly mae'n rhaid iddo fod yn iawn,
ac mae hefyd yn fwy na 4, felly mae'n rhaid iddo fod yn iawn eto.
Fodd bynnag, nid oes unrhyw blentyn yma.
Mae'r pwyntydd yn null.
Mae hyn yn golygu bod 5 nid yw yn ein coeden.
>> Gallwn chwilio y goeden ddeuaidd gyda'r cod canlynol:
Ar bob nod, rydym yn gwirio i weld os ydym wedi dod o hyd
y gwerth yr ydym yn chwilio amdano.
Os nad ydym yn ei chael yn, rydym yn penderfynu os dylai fod yn
ar y a chwith neu i'r dde gwirio bod Terfynau Chwilio.
Bydd y ddolen yn parhau i lawr y goeden
hyd nes nad oes nod blentyn naill ai ar y chwith neu i'r dde.
>> Cofiwch nad oedd 5 yn y goeden.
Sut ydym yn mewnosod ei?
Mae'r broses yn edrych yn debyg i chwilio.
Rydym yn ailadrodd i lawr y goeden sy'n dechrau o 6,
gadael i 2,
hawl i 4,
ac i'r dde eto, ond 4 Nid oes gan blentyn ar yr ochr hon.
Bydd hyn yn y sefyllfa newydd ar gyfer 5,
a bydd yn dechrau heb blant.
>> Pa mor gyflym mae gweithrediadau ar goeden chwiliad deuaidd?
Cofiwch fod Bigohnotation yn ceisio rhoi rwymo uchaf.
Yn yr achos gwaethaf,
gallai ein coeden yn syml fod yn rhestr cysylltiedig
sy'n golygu bod mewnosod, dileu, a chwilio
Gallai cymryd amser gymesur â nifer y nodau yn y goeden.
Mae hyn yn O (n).
>> Er enghraifft, mae'r canlynol yn goeden ddeuaidd chwilio dilys.
Fodd bynnag, os ydym yn ceisio dod o hyd i 9,
mae'n rhaid i ni deithio ar draws pob nod.
Nid yw'n well na rhestr cysylltiedig.
Yn ddelfrydol, byddem am i bob nod
o'n chwiliad deuaidd coed i 2 o blant.
Mae hyn yn ffordd, mewnosod, dileu a chwilio
Byddai cymryd, ar y gwaethaf, O (n log) amser.
Gallai'r goeden o flaen fod yn fwy cytbwys,
fel hyn.
Yn awr, gan edrych i fyny unrhyw werth cymryd, ar y mwyaf, 3 camau.
Mae'r goeden hon yn gytbwys,
ystyr bod ganddi dyfnder lleiaf posibl
o'i gymharu â nifer y nodau.
>> Chwilio am werth mewn coeden chwiliad deuaidd cytbwys
yn debyg i chwilio deuaidd ar amrywiaeth datrys.
Yn wir, os nad oes angen i ni mewnosod neu ddileu eitemau,
maent yn ymddwyn yn union yr un ffordd.
Fodd bynnag, mae strwythur coeden yn well
am fewnosodiadau a dileadau trin
>> Fy enw i yw Bannus Van der Kloot.
Mae hyn yn CS50.