Arbori

1x punct

categorie: Informatica

nota: 9.63

nivel: Liceu

     Fie G un graf orientat. G este un arbore cu radacina r, daca exista in G un varf r din care oricare alt varf poate fi ajuns printr-un drum unic.

     Definitia este valabila si pentru cazul unui graf neorientat, alegerea unei radacini fiind insa in acest caz arbitrara: orice arbore este un arbore cu radacina, iar radacina poate fi fixata in oricare varf al sau. Aceasta, deoarec[...]
DOWNLOAD REFERAT

Preview referat: Arbori

     Fie G un graf orientat. G este un arbore cu radacina r, daca exista in G un varf r din care oricare alt varf poate fi ajuns printr-un drum unic.

     Definitia este valabila si pentru cazul unui graf neorientat, alegerea unei radacini fiind insa in acest caz arbitrara: orice arbore este un arbore cu radacina, iar radacina poate fi fixata in oricare varf al sau. Aceasta, deoarece dintr-un varf oarecare se poate ajunge in oricare alt varf printr-un drum unic.

     Cand nu va fi pericol de confuzie, vom folosi termenul "arbore", in loc de termenul corect "arbore cu radacina". Cel mai intuitiv este sa reprezentam un arbore cu radacina, ca pe un arbore propriu-zis. In Figura 3.1, vom spune ca beta este tatal lui delta si fiul lui alpha, ca beta si gamma sunt frati, ca delta este un descendent al lui alpha, iar alpha este un ascendent al lui delta. Un varf terminal este un varf fara descendenti. Varfurile care nu sunt terminale sunt neterminale. De multe ori, vom considera ca exista o ordonare a descendentilor aceluiasi parinte: beta este situat la stanga lui gamma, adica beta este fratele mai varstnic al lui gamma.

     Orice varf al unui arbore cu radacina este radacina unui subarbore constand din varful respectiv si toti descendentii sai. O multime de arbori disjuncti formeaza o padure.

     Intr-un arbore cu radacina vom adopta urmatoarele notatii. Adancimea unui varf este lungimea drumului dintre radacina si acest varf; inaltimea unui varf este lungimea celui mai lung drum dintre acest varf si un varf terminal; inaltimea arborelui este inaltimea radacinii; nivelul unui varf este inaltimea arborelui, minus adancimea acestui varf.

     Reprezentarea unui arbore cu radacina se poate face prin adrese, ca si in cazul listelor inlantuite. Fiecare varf va fi memorat in trei locatii diferite, reprezentand informatia propriu-zisa a varfului (valoarea varfului), adresa celui mai varstnic fiu si adresa urmatorului frate. Pastrand analogia cu listele inlantuite, daca se cunoaste de la inceput numarul maxim de varfuri, atunci implementarea arborilor cu radacina se poate face prin tablouri paralele

     Au fost studiate diferite tipuri de arbori binari, adica arbori pentru care e-gradul fiecarui nod este mai mic sau egal cu 2. Arborii care au e-gradul mai mare sau egal cu 2 se numesc arbori multicai.

     Daca se doreste sa se prezinte descendenta unei persoane din punct de vedere al stramosilor, i se asociaza persoanei doi parinti, obtinându-se un arbore binar.

      Se considera problema construirii si explorarii informatiei continute în arbori de mari dimensiuni; se considera si operatiile executate unor astfel de arbori.

     Sa notam ca astfel de arbori sunt pastrati pe suporturi auxiliare; atunci nodurile arborelui sunt memorate pe un suport auxiliar si sunt transferate pe rând sau pe grupe în memoria centrala.

     Structurile dinamice sunt cele utilizate eficient pentru implementarea unor astfel de arbori. În acest caz pointerii nodurilor nu vor mai indica adrese de memorie.

     Utilizând un arbore cu 106 noduri, vor fi necesare aproximativ log2106 pasi pentru cautarea unor elemente.

     Deoarece fiecare pas necesita un acces la memoria auxiliara rezulta necesitatea unei organizari care sa reduca numarul de accese.

     Este stiut faptul ca dupa realizarea accesului la un anumit element al memoriei auxiliare este usor accesibil fiecare element al arborelui din zona respectiva. Acest lucru sugereaza ca un arbore poate fi divizat în subarbori ce pot fi reprezentati ca unitati la care accesul se realizeaza deodata. Subarborii în care sunt divizati arborii de mari dimensiuni si care au proprietatea de mai sus se numesc pagini.

     Pentru descompunerea în pagini a unui arbore binar trebuie avute în vedere urmatoarele aspecte:

     a) modul de grupare a cheilor într-un arbore multicai;

     b) modul de plasare a elementelor corespunzatoare diverselor chei;

     c) tehnica de inserare sau eliminare a unei chei;

     d) modul de aranjare a cheilor în cadrul unui nod.

      Dintre toate modurile de organizare a arborilor multicai cel mai eficient este arborele 3-2, care reprezinta o varianta de arbore echilibrat; un nod al unui astfel de arbore poate avea cel mult 3 descendenti directi.
DOWNLOAD REFERAT
« mai multe referate din Informatica

CAUTA REFERAT

TRIMITE REFERAT CERE REFERAT
Referatele si lucrarile oferite de E-referate.ro au scop educativ si orientativ pentru cercetare academica.
Confidentialitatea ta este importanta pentru noi

E-referate.ro utilizeaza fisiere de tip cookie pentru a personaliza si imbunatati experienta ta pe Website-ul nostru. Te informam ca ne-am actualizat termenii si conditiile de utilizare pentru a integra cele mai recente modificari privind protectia persoanelor fizice in ceea ce priveste prelucrarea datelor cu caracter personal. Inainte de a continua navigarea pe Website-ul nostru te rugam sa aloci timpul necesar pentru a citi si intelege continutul Politicii de Cookie. Prin continuarea navigarii pe Website-ul nostru confirmi acceptarea utilizarii fisierelor de tip cookie conform Politicii de Cookie. Nu uita totusi ca poti modifica in orice moment setarile acestor fisiere cookie urmarind instructiunile din Politica de Cookie.


Politica de Cookie
Am inteles