[Powered by Google Translate] Cum ti-ar reprezenta toți membrii familiei dumneavoastră într-un calculator?
Am putea folosi pur și simplu o listă,
dar există o ierarhie clară aici.
>> Să spunem că te începând cu stră-bunica, Alice.
Ea are 2 fii, Bob
și bunicul tău, Charlie.
Charlie are 3 copii,
unchiul tău, Dave, mătușa ta, Eva, și tatăl tău, Fred.
Sunteți singurul copil lui Fred.
>> De ce ar fi organizarea de membrii familiei dumneavoastră în acest mod
fi mai bine decât reprezentarea simplă listă?
Unul dintre motive este faptul că această structură ierarhică,
numit "copac," conține mai multe informații decât o simplă listă.
Știm că relațiile familiale dintre toți
doar prin examinarea copac.
De asemenea, se poate accelera
Look-up timp foarte mult, în cazul în care datele de arbori este sortat.
>> Noi nu putem profita de asta aici, dar vom vedea un exemplu în acest sens în curând.
Fiecare persoană este reprezentată de un nod în arbore.
Nodurile pot avea noduri copilului
precum și un nod parinte.
Acestea sunt condițiile tehnice,
chiar și atunci când se utilizează arbori de lucruri în afară de familii.
Nod lui Alice are 2 copii si nici parintii,
în timp ce nodul lui Charlie are 3 copii și 1-mamă.
>> Un nod frunză este una care nu are nici un copil
pe marginea exterioară a arborelui.
Nodul cel mai important al arborelui, nodul rădăcină,
nu are nici un părinte.
>> Un arbore binar este un tip specific de copac,
în care fiecare nod are, cel mult, 2 copii.
Aici este struct de un nod al unui arbore binar în C.
Fiecare nod are unele date asociate cu acesta
și 2 pointeri la alte noduri.
>> În arborele familiei noastre,
datele asociate era numele fiecărei persoane.
Aici este un int, deși ar putea fi orice.
După cum se dovedește,
un arbore binar nu ar fi o reprezentare buna pentru o familie,
din moment ce oamenii au în mod frecvent mai mult de 2 copii.
>> Un copac binar de căutare
este un tip special, ordonată de arbore binar
care ne permite sa se uite la valori mai repede.
Este posibil să fi observat
că fiecare nod sub rădăcina unui copac
este rădăcina alt copac, numit "subarbore."
Aici, rădăcina arborelui este de 6,
și copilul său, 2, este rădăcina unui subarbore.
>> Într-un arbore binar de căutare
toate valorile unui nod e drept subarborele
sunt mai mari decât valoarea nodului. Aici: 6.
Ei bine, valorile din subarborele un nod de stânga
sunt mai mici decât valoarea nodului.
Dacă avem nevoie să se ocupe de valori dublură,
putem schimba oricare dintre cele la o inegalitate în vrac,
ceea ce înseamnă valori identice poate cădea fie pe stânga sau dreapta,
atâta timp cât suntem consecvenți cu privire la aceasta de-a lungul.
Acest arbore este un arbore binar de căutare
deoarece urmează aceste reguli.
>> Acesta este modul în care ar arăta dacă ne-am întors toate nodurile în struct C.
Observați că, dacă un copil este dispărut,
indicatorul este nul.
Cum vom verifica pentru a vedea dacă 7 este în copac?
Vom începe de la rădăcină.
Șapte este mai mare de 6, așa că dacă e în copac, acesta trebuie să fie dreaptă.
Apoi, aceasta este mai mică de 8, așa că trebuie să fie lăsat.
Aici, am gasit 7.
Acum, vom verifica pentru 5.
Cinci este mai mică de 6, așa că trebuie să fie la stânga.
Cinci este mai mare de 2,
așa că trebuie să fie corect,
și este, de asemenea, mai mare de 4, deci trebuie să fie corect din nou.
Cu toate acestea, nu există nici un copil aici.
Cursorul este nul.
Acest lucru înseamnă că 5 nu este în copacul nostru.
>> Noi putem căuta arbore binar cu codul de mai jos:
La fiecare nod, vom verifica pentru a vedea dacă ne-am gasit
valoarea pe care o cautati.
Dacă nu vom găsi, vom determina dacă acesta ar trebui să fie
pe stânga sau dreapta și verificați dacă subarborele.
Această buclă va continua în jos copac
până când nu există nici un nod copil fie pe stânga sau la dreapta.
>> Amintiți-vă că 5 nu a fost în copac.
Cum l-am introduce?
Procesul este asemănător pentru a căuta.
Noi repeta în jos arborele începând de la 6,
a plecat la 2,
dreptul la 4,
și din nou la dreapta, dar nu are nici un copil 4 pe partea asta.
Acest lucru va fi noua poziție timp de 5,
și va începe fără copii.
>> Cât de repede sunt operații pe un arbore binar de căutare?
Amintiți-vă că Bigohnotation încearcă să ofere o legat de sus.
În cel mai rău caz,
copacul nostru ar putea fi pur și simplu o listă legat
sensul că inserare, ștergere, căutare și
ar putea avea nevoie de timp proporțional cu numărul de noduri din arbore.
Acest lucru este O (n).
>> De exemplu, următorul este un arbore binar de căutare validă.
Cu toate acestea, în cazul în care vom încerca să găsim 9,
avem de a traversa fiecare nod.
Nu este nici mai bună decât o listă legată.
În mod ideal, ne-ar dori fiecare nod
nostru binar arbore de căutare pentru a avea 2 copii.
În acest fel, inserare, ștergere și căutare
ar lua, în cel mai rău, O (log n) timp.
Arbore de dinainte ar putea fi mai echilibrată,
ca asta.
Acum, uita în sus orice valoare are, cel mult, 3 trepte.
Acest copac este echilibrat,
sensul că are o adâncime minimă
în raport cu numărul de noduri.
>> Cauti o valoare într-un copac echilibrată binar de căutare
este similar cu cautarea binara pe o matrice sortate.
De fapt, în cazul în care nu avem nevoie pentru a insera sau șterge elemente,
acestea se comportă exact același mod.
Cu toate acestea, o structură de arbore este mai bine
pentru insertii de manipulare și ștergeri
>> Numele meu este Bannus Van der Kloot.
Acest lucru este CS50.