[Powered by Google Translate] Si do të përfaqësojë të gjithë anëtarët e familjes tuaj në një kompjuter?
Ne thjesht mund të përdorni një listë,
por ka një hierarki të qartë këtu.
>> Le të thonë se ne jemi duke filluar me gjyshen tuaj të madhe-, Alice.
Ajo ka 2 djem, Bob
dhe gjyshi juaj, Charlie.
Charlie ka 3 fëmijë,
xhaxhai juaj, Dave, halla juaj, Eva, dhe babai yt, Fred.
Ju jeni fëmijë i vetëm Fred s.
>> Pse do të organizimit anëtarët e familjes tuaj në këtë mënyrë
të jetë më mirë se përfaqësimi listë e thjeshtë?
Një arsye është se kjo strukturë hierarkike,
quajtur një 'pemë', përmban informacione më shumë se një listë të thjeshtë.
Ne e dimë marrëdhëniet familjare ndërmjet të gjithë
vetëm me shqyrtimin e pemë.
Gjithashtu, ajo mund të përshpejtojë
look-up kohë të jashtëzakonshme, nëse të dhënat pemë është e renditura.
>> Ne nuk mund të përfitojnë nga se këtu, por ne do të shohim një shembull të kësaj së shpejti.
Çdo person është i përfaqësuar nga një nyje në pemë.
Nyje nyje mund të ketë fëmijë
si dhe një nyje mëmë.
Këto janë kushtet teknike,
edhe kur duke përdorur pemë për gjëra përveç familjeve.
Nyja Alice ka 2 fëmijë dhe jo prindërit,
ndërsa nyja Charlie ka 3 fëmijë dhe 1 prind.
>> Një nyjë është një fletë që nuk kanë ndonjë fëmijë
në skajin e jashtme e pema.
Nyja larti e pemës, nyja rrënjë,
nuk ka prind.
>> Një pemë binare është një lloj specifik i pemës,
në të cilën çdo nyje ka, më së shumti, 2 fëmijë.
Këtu është struct e një nyje e një pemë binare në C.
Çdo nyje ka disa të dhëna që lidhen me të
dhe 2 pointers në nyjet e tjera.
>> Në pemën tonë familjare,
të dhënat që lidhen ishte emri i secilit person.
Këtu ajo është një int, edhe pse ajo mund të jetë çdo gjë.
Siç rezulton,
një pemë binare nuk do të jetë një përfaqësim të mirë për një familje,
që njerëzit shpesh kanë më shumë se 2 fëmijë.
>> Një kërkim binar pemë
është një e veçantë, lloji i urdhëroi pemë binare
që na lejon të shikojmë në vlerat shpejt.
Ju mund të keni vënë re
se çdo nyje nën rrënjët e një pemë
është rrënja e pemës tjetër, i quajtur një 'subtree.'
Këtu, rrënja e pemës është 6,
dhe fëmijë saj, 2, është rrënja e një subtree.
>> Në një pemë binare e kërkimit
të gjitha vlerat e një nyje e drejtë subtree
janë më të mëdha se vlera nyjen së. Këtu: 6.
E pra, vlerat në subtree majtë një nyje e
janë më pak se vlera nyjen së.
Nëse ne kemi nevojë për të trajtuar vlerat kopjuar,
Ne mund të ndryshojë ose të atyre me një pabarazi të lirshme,
që do të thotë vlera identike mund të bjerë as në të majtë apo të djathtë,
për aq kohë sa ne jemi konsistente në lidhje me të gjithë.
Kjo pemë është një pemë binare kërko
për shkak se ajo ndjek këto rregulla.
>> Kjo është se si do të dukej në qoftë se ne u kthye të gjitha nyjet në structs C.
Vini re se në qoftë se një fëmijë është zhdukur,
tregues është i pavlefshëm.
Si nuk kemi të kontrolloni për të parë nëse është i 7 në pemë?
Ne të fillojë në rrënjë.
Shtatë është më e madhe se 6, kështu që nëse kjo është në pemë, ajo duhet të jetë në të djathtë.
Pastaj, ajo është më pak se 8, kështu që ajo duhet të lihet.
Këtu, ne kemi gjetur 7.
Tani, ne do të kontrolloni për 5.
Pesë është më pak se 6, kështu që ajo duhet të jetë në të majtë.
Pesë është më e madhe se 2,
kështu që ajo duhet të jetë e drejtë,
dhe kjo është edhe më e madhe se 4, kështu që ajo duhet të jetë e drejtë përsëri.
Megjithatë, nuk ka fëmijë këtu.
Tregues është i pavlefshëm.
Kjo do të thotë se 5 nuk është në pemë tonë.
>> Ne mund të kërkoni në pemë binare me kodin e mëposhtëm:
Në çdo nyje, ne kontrolloni për të parë nëse ne kemi gjetur
vlera ne jemi duke kërkuar për të.
Nëse ne nuk e gjeni atë, ne të përcaktuar nëse ajo duhet të jetë
në dhe të majtë apo të djathtë të kontrolloni se subtree.
Kjo lak do të vazhdojë poshtë pemë
derisa nuk ka asnjë nyjë fëmijë në të dyja të majtë apo të djathtë.
>> Mos harroni se 5 nuk ishte në pemë.
Si nuk kemi futur atë?
Procesi duket e ngjashme për të kërkuar.
Ne iterate poshtë pemë duke filluar nga 6,
e majta në të 2,
drejtën për 4,
dhe të drejtën përsëri, por 4 nuk ka fëmijë në këtë anë.
Kjo do të jetë pozita e re për 5,
dhe ajo do të fillojë me pa fëmijë.
>> Sa shpejt janë operacione në një pemë binare e kërkimit?
Mos harroni se Bigohnotation kërkon të sigurojë një lidhur sipërme.
Në rastin më të keq,
pema jonë mund të jetë thjesht një listë e lidhur
thotë se futje, fshirje, dhe kërko
mund të marrë kohë proporcional me numrin e nyjeve në pemë.
Kjo është O (n).
>> Për shembull, në vijim është një vlefshëm kërkimit binar pemë.
Megjithatë, nëse ne përpiqemi të gjejmë 9,
ne duhet të kaloj çdo nyje.
Ajo nuk është më e mirë se një listë e lidhur.
Teorikisht, ne do të duan çdo nyje
e pemë binare e kërkimit tonë që të ketë 2 fëmijë.
Në këtë mënyrë, futje, fshirje dhe kërko
do të marrë, në më të keq, O (log n) kohë.
Pema e para mund të jetë më e balancuar,
si kjo.
Tani, duke kërkuar deri ndonjë vlerë merr, më së shumti, 3 hapa.
Kjo pemë është i balancuar,
do të thotë se është ka një thellësi minimale
në lidhje me numrin e nyjeve.
>> Duke kërkuar për një vlerë në një pemë binare e kërkimit të ekuilibruar
është i ngjashëm me kërkimin binar në një grup të renditura.
Në fakt, në qoftë se ne nuk kemi nevojë për të futur apo fshij artikuj,
ata sillen pikërisht të njëjtën mënyrë.
Megjithatë, një strukturë pemë është më e mirë
për insertions trajtimin dhe fshirjeve
>> Emri im është Bannus Van der Kloot.
Kjo është CS50.