Arbori
Un arbore este un graf neorientat conex și aciclic.
- un arbore cu
nvârfuri aren - 1muchii - între oricare două vârfuri ale unui arbore există un lanț elementar unic
- un arbore este un graf aciclic și maximal are proprietatea că dacă s-ar mai adăuga o muchie, s-ar obține un ciclu
Arborilor li se poate alege o rădăcină, de care putem spune că „agățăm” arborele, iar restul nodurilor „cad”.
Terminologie
- două noduri care au același tată se numesc frați
- lungimea unui lanț de la rădăcina arborelui la un nod
x, se numeșteadâncimeasaunivelulnoduluix - nivelul maxim se numește
înălțimea arborelui - un nod al arborelui împreună cu toți copiii săi formează un
subarbore frunzelesunt nodurile care nu sunt tați
Reprezentare
Vectori de tați
O modalitate comună de a reprezenta un arbore este utilizând un vector de tați, în care fiecare poziție păstrează informații despre descendentul direct.
tati[r] = 0, undereste rădăcina arboreluitati[i] = tatăl nodului i
Arbori binari
Un arbore este binar dacă fiecare nod are cel mult 2 descendenți direcți, numiți și descendentul stâng și descendentul drept.
Arbori binari plini
Un arbore binar este plin, dacă pe fiecare nivel k de la 0 la h, unde h este înălțimea arborelui, are 2 ^ k noduri. Cu alte cuvinte, dacă are numărul maxim de noduri, pentru un h dat sau dacă toate frunzele sunt maximale și pe ultimul strat.
- un arbore binar plin cu înălțimea
hare(2 ^ h) - 1noduri
Arbori binari compleți
Un arbore binar este complet, dacă pe fiecare nivel k de la 0 la h - 1, unde h este înălțimea arborelui, conține 2 ^ k noduri, iar nivelul k conține 2 ^ h sau mai puține noduri, acestea fiind de regulă grupate în partea stângă.
- un
arbore binar plineste șiarbore binar complet