curs07.txt

STRUCTURI DE DATE SI ALGORITMI

				     Curs 7

   Arbori
Exemplu de structura de arbore:

                                 a
                               /    \
                            b         c
                         /    \     /    \
                        d       e  f      g
                      /    \        \
                     h      i        j 
Exemple de arbori:

                               poligoane
                               /       \
                         triunghi    patrulatere
                             /    \     \
                    dreptunghi   romb   oarecare
Definitie
Se numeste arbore cuplul format din V si E : T= (V,E) cu V  o multime de noduri
si E  VxV  o multime de arce, cu proprietatile:

1)   nodul r  V (nodul radacina) astfel 宯c僼  j  V,  (j, r)  E
2)   x  V\{r} ,  y  V unic , astfel 宯c僼 (y, x)  E (Cu alte cuvinte, pentru
toate nodurile radacina,  un singur arc ce intra 宯 nodul respectiv)
3)   y  V,  un drum { r = x0, x1, x2, ... ,xn= y} , cu xi  V si (xi, xi+1)
 E (Sau arborele trebuie sa fie un graf conex: nu exista noduri izolate sau
grupuri de noduri izolate).

Proprietate a arborelui

Daca T, T= (V, E) este un arbore si r  V este radacina arborelui, atunci
multimea T\{r} = (V', E'), cu 
V' = V -{r} si E' = E -{ (r, x)/(r, x)  E } poate fi partitionata astfel
宯c僼 sa avem mai multi arbori, a caror reuniune sa fie T\{r}, si oricare
ar fi doi arbori intersectati, sa dea multimea vida:
			T\{r}= T1  T2  ...  Tk , Ti  Tj =  .


Definitii

1) Daca avem (x, y)  E ,   x  predecesorul lui y (tata),  y  succesorul
lui x (fiu)
                                                                x
                                                                /
                                                              y 

2)  Fie E(x) = { y, (x, y)  E } multimea succesorilor lui x.

Definim gradul lui x: degree(x) =