[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.