copaci binar de căutare - studopediya

Un arbore binar este comandat, dacă pentru orice nod x este adevărat o astfel de proprietate: toate elementele stocate în subarborele stâng este mai mică decât elementul depozitat la x. și toate elementele stocate în dreapta subramificație mai mare element de depozitat la x.

Important proprietate copac a ordonat: toate elementele sale sunt diferite. Dacă există aceleași elemente în copac, copacul este parțial ordonată.

În viitor, va exista fi comandate numai arbori binari, cuvântul „armonizare“ va fi omisă.

Arborele de căutare (arbori de căutare) vă permit să efectuați următoarele operații cu Dean
seturi nomic: Căutare (căutare), minim (cel puțin), Maxim (macro-
maxima a), predecesor (anterior), Succesor (următor), Insert (vsta-
VIT) și Delete (șterge). Astfel, arborele de căutare poate fi Utilizarea
Chemarea și ca un dicționar, și ca o coadă de prioritate.

timpul de funcționare de bază este proporțională cu înălțimea copacului. dacă
arbore binar „dens umplut“ (toate nivelurile sale au maxim posibil
Numărul de vârfuri Noe), înălțimea sa (și, prin urmare, executarea operațiunilor)
este proporțională cu logaritmul numărului de noduri. Dimpotrivă, în cazul în care predstavlya- copac
un lanț drept de n noduri, de data aceasta creste.

Desigur, apar în practică arbori de căutare binare pot fi
departe de a fi aleatoare. Cu toate acestea, prin adoptarea unor măsuri speciale pentru echilibrarea de-
revev, vă puteți asigura că înălțimea unui arbore cu n noduri este O (log n).

Punerea în aplicare a operațiunilor vor fi luate în considerare pentru arborele binar reprezentat ca o structură dinamică.

Realizarea acest lucru poate fi găsit sub forma unor proceduri corespunzătoare.

Algoritmul de căutare poate fi scris într-o formă recursiv. Dacă valoarea este mai mică Element arbore ^ .data, căutarea continuă în subarborele stâng în cazul în care este - căutare este considerat de succes în cazul în care mai mult - căutare continuă în subarborele din dreapta; căutare este considerat un eșec în cazul în care a ajuns la subramificație gol, iar elementul nu a fost găsit.

funcționează TreeSearch (Postul: TypeElement; Arbore: PTree): Boolean;

în cazul în copac <> nil apoi începe

în cazul în curent ^ .data = Postul atunci

TreeSearch: = TreeSearch (Articol, curent ^ .Left)

TreeSearch: = TreeSearch (Articol, curent ^ .Right);

Listarea 3.15 - Procesul de căutare într-un arbore binar în Pascal

Listarea 3,24 - procedura de căutare recursiv într-un arbore binar de căutare

Listarea 3.25 - nonrecursive (iterativă) căutare procedură într-un arbore binar de căutare

Minimă și maximă

cheie minimă în arborele de căutare pot fi găsite urmând semnele lăsate
de la rădăcină (până când vom ajunge la NIL). Procedura returnează un pointer
un element de minim subarborelui cu radacina x.

Listarea 3.26 - Procedura de căutare elementul minim într-un arbore binar de căutare

facilitate de comanda asigură procedurile corecte

Tree-
Minimum. În cazul în care nodurile x nici un copil din stânga, elementul minim
subarbore cu radacina x este x. din moment ce orice cheie în subarborele drept nu este
mai puțin tasta [x]. Dacă subarborele stâng al unui nod x nu este gol, atunci minimul
subarbore element rădăcină x este situat în subarborele stâng (ca
el toate elementele mai mare de subramificație din dreapta).

Tree-maximă algoritm simetric:

Listarea 3.27 - procedura de căutare element de maximă într-un arbore binar de căutare

Ambii algoritmi necesită timp O (h), în cazul în care h - înălțimea copacului (deoarece copacul se deplaseze numai în jos).

Elementele următoare și anterioare

Cum de a găsi într-un element de arbore binar urmând datele? proprietate
ordonare vă permite să faceți acest lucru prin mutarea copac. Aici este procedura,
care returnează un pointer la următorul element x (dacă toate cheile
sunt diferite, acesta conține următoarea cea mai mare cheie) sau NIL, în cazul în care elementul -
ultimul în copac:

Listarea 3,28 - procedurile de căutare ar trebui să fie (în sensul de ordine pe tastele) într-un arbore binar de căutare

Procedura Arbore-Succesor ia în considerare separat două cazuri. Dacă pra-
urlând subarbore vertex x gol, elementul următor al elementului x minim în subarbore și egal de arbore minim (dreapta [x]).

Să presupunem acum că subarborelui drept al unui nod x este gol. Apoi vom merge de la x pana
până când vom găsi vârful, care este copilul stâng al părinților săi (linii
3 - 7). Acest părinte (dacă există) este elementul dorit. formal
vorbind, bucla pe liniile perioada 4 - 6 reține o proprietate: y = p [z]; element de căutare
elemente urmează imediat subarborelui înrădăcinate la x.

In timp ce procedurile de lucru Arbore-succesoare la copac înălțimea h are O (h),
pentru că suntem în mișcare sau numai în sus sau în jos numai.

Procedura Arbore-predecesor este simetrică. Astfel, am demonstrat următoarea teoremă.

Teorema. Operațiunea de căutare, minim, maxim, continuatorul și înălțimea predecesor h pe copac sunt executate într-un timp O (h).

Adăugarea și eliminarea

În continuare vor fi luate în considerare algoritm non-recursiv pentru adăugarea unui element în copac. În primul rând, trebuie să găsiți în partea de sus, la care, ca un copil, trebuie să adăugați un nou nod (de fapt, pentru a căuta) și apoi atașați la găsit un nou nod care conține valoarea articol (procedura este scris cu presupunerea că elementul adăugat în arborele nu este prezent).

Procedura TreeAdd (Postul: TypeElement; var copac: PTree);

NewNode, curent: PTree;

dacă copac = zero începe apoi

Listarea 3.31 - Procedura pentru eliminarea unui element dintr-un arbore binar de căutare

Listarea 3,32 - Procedura pentru eliminarea unui element dintr-un arbore binar de căutare

Figura 3.14 - Eliminarea unui element dintr-un arbore binar de căutare

Ștergerea unui nod z dintr-un arbore binar de căutare. (A) În cazul în care nodul z nu are copii poate fi îndepărtat fără probleme. (6) În cazul în care nodul z are un copil, l-am pus în locul nod z. (C) Dacă vertex z are doi copii, procesul este redus
în cazul precedent, și anume, în loc să-l eliminați din partea de sus la imediat următor
Valoarea cheie (în acest copil vârfuri unul) și plasarea tasta KEU [y] (și conexe
date suplimentare) pentru a plasa vârful z.

Procesul de tratare a lemnului se aplică o metodă traversal inversă. Utilizarea workaround inversă asigură că va fi mai întâi vizitate și a îndepărtat toți descendenții strămoș înainte de a scoate el însuși strămoș.

Procedura TreeClear (Arborele var: PTree);

în cazul în copac <> nil apoi începe

Listarea 3.33 - Procedura de compensare binar de căutare copac

Complexitatea timp a acestei operații este O (n).

Aleatoare Copaci căutare

arbori de căutare aleatoare sunt ordonate arbori binari de căutare, crearea care se introduc elementele (de chei), în ordine aleatorie.

Stabilirea unor astfel de copaci, folosind același algoritm ca și atunci când adăugați noduri într-un arbore binar de căutare. Va crea un copac la întâmplare sau nu, depinde de ordinea în care elementele de vin pentru a adăuga. Exemple de copaci diferiți create în diferite elemente FIFO sunt prezentate mai jos.

Figura 3.15 - aleatoare și arbori de căutare degenerate

Ca elemente ajung la întâmplare a obține un copac cu o înălțime minimă h (vezi. Fig. 3.12.a), și minimizează în mod corespunzător căutarea elementului timp într-un astfel de arbore, care este proporțională cu O (log n). La sosirea elementelor într-o manieră ordonată (vezi. Fig. 3.12.b) sau într-o manieră oarecum neobișnuită (vezi. Fig. 3.12.v) arborii de căutare construi degenerat (l degenera într-o listă liniară), care nu reduce timpul de căutare, care este O (n).

arbori de căutare optimă

Atunci când căutați într-un arbore binar unele elemente pot fi căutate mai des decât ceilalți, adică, există o probabilitate de căutare k pk element și elemente diferite mii, aceste probabilități nu sunt aceleași. Puteți doar presupune că în căutarea copac în mijloc va fi mai rapid, în cazul în care aceste elemente care sunt căutate mai des, va fi mai aproape de rădăcina copacului.

pi - probabilitatea ca argumentul de căutare este Ki;

Q0 - probabilitatea ca argumentul de căutare este mai mică decât K1;

Qn - probabilitatea ca argumentul de căutare este mai mare decât Kn;

Apoi căutarea prețul copac C va fi determinată după cum urmează:

în cazul în care levelrootj - nivel de nod j. și levellistk - nivel de foaie k.

căutare copac se numește optimă în cazul în care prețul este minim sau, cu alte cuvinte, optim arbore binar de căutare - este un arbore binar de căutare construit bazată pe maximizarea performanței pentru o anumită distribuție a datelor necesare probabilități de căutare.

Există o abordare de construire a arborilor de căutare optime în care sunt inserate elemente în ordinea frecvenței descrescătoare, care dă o medie de arbori de căutare bune. Cu toate acestea, această abordare poate oferi un copac degenerat de căutare, care este departe de a fi optim.

O altă abordare este de a selecta rădăcina k, astfel încât suma maximă a probabilităților pentru nodurile subarborelui stâng și subarborelui drept a fost atât de mic posibil. Această abordare poate fi, de asemenea, scăzute în cazul de selectare, ca element rădăcină, cu o mică valoare de pk.

Există algoritmi care vă permit să construiască un arbore de căutare optimă. Acestea includ, de exemplu, algoritmul Garcia Vocii. Cu toate acestea, acești algoritmi au o complexitate timp de ordinul O (n 2), iar unele au chiar aceeași complexitate spațială. Astfel, crearea de arbori de căutare optimă necesită o mulțime de costuri de regie, care nu justifică întotdeauna câștigurile în căutarea rapidă.