Note de curs, clasele 11-12, 6 martie 2014

Arbori

Aceste note rezumă tot ce consider că merită povestit despre arbori. Probabil nu vom acoperi chiar tot în această lecție.

Definiție, proprietăți

Următoarele definiții pentru un arbore neorientat (fără rădăcină) sunt echivalente:

• un arbore este un graf neorientat în care între oricare două noduri există exact o cale;
• un arbore este un graf conex aciclic
• un arbore este un graf aciclic maximal
• un arbore este un graf conex minimal
• un arbore este un graf aciclic cu n vârfuri și n - 1 muchii
• un arbore este un graf conex cu n vârfuri și n - 1 muchii

O pădure este o colecție de arbori, respectiv un graf neorientat aciclic.

Într-un arbore cu rădăcină, un nod aparte este desemnat ca rădăcină, caz în care toate muchiile capătă o orientare.

Terminologie

• nod
• nod intern
• frunză
• părinte
• strămoș
• copil
• descendent (urmaș)
• subarbore
• rădăcină
• arbore binar / ternar / k-ar
• arbore binar strict: nodurile au fie zero fii, fie doi fii
• arbore binar complet: toate nivelurile, posibil cu excepția ultimului, sunt pline, iar pe ultimul nivel toate frunzele sunt în stânga
• arbore binar perfect: toate nivelurile sunt pline

Reprezentări

Presupunem că nodurile au numere de la 1 la n.

• vector de tați: cea mai compactă
• pointeri la fii (pentru cazul binar)
  • de vreme ce fiecare nod are 2 pointeri la fii, dar exact un părinte, această abordare risipește întotdeauna n pointeri.
  • problema se agravează pentru arbori ternari, cuaternari etc.
• pointeri la listă de fii (pentru cazul general)
• pointeri la primul fiu și la fratele din dreapta
• heap (pentru arborii binari compleți)
• cod Prüfer (mai mult ca problemă)
• pentru arborii binari: oricare două din cele trei parcurgeri: preordine, inordine, postordine

Parcurgeri

• în preordine
• în inordine (pentru arborii binari)
• în postordine
• Euler

Aplicații

Aplicațiile arborilor sunt nenumărate. Ei intervin, la nivel conceptual, pretutindeni în informatică, chiar dacă nu sunt întotdeauna stocați ca atare:

• expresii aritmetice
• arbori de joc (șah etc.)
• arborele unei parcurgeri de graf
• sistemul de fișiere (discuție despre symlinks)
• rețeaua de curent (până la un punct, căci există redundanță)
• arborele sintactic al unei fraze
• ierarhia militară sau a unei companii
• arborele genealogic
• arborii din parc :-)
• arborele de specii
• sintaxa HTML / XML

Expresii aritmetice. Notația poloneză

Scrierea uzuală a expresiilor aritmetice se numește notație infixată, căci operatorul stă între cei doi operanzi: 3 + 4. Există și alte două notații:

• 3 + 4: notație infixată
• + 4 3: notație prefixată sau notație poloneză (sau forma poloneză etc.)
• 4 3 +: notație postfixată sau notație poloneză inversă

Notațiile prefixată și postfixată au două mari avantaje:

1. Nu necesită paranteze. (3 + 4) * 5 se transcrie în notație prefixată ca * + 3 4 5, iar în notație postfixată ca 3 4 + 5 *
2. Se pot evalua ușor folosind doar o stivă
   • Pentru notația prefixată: de câte ori în vârful stivei apar două numere (iar înaintea lor se află un operator), se scot cele trei elemente de pe stivă, se evaluează expresia și se pune rezultatul în apoi pe stivă
   • Pentru notația postfixată: de câte ori în vârful stivei apare un operator (iar înaintea lui se află două numere), se scot cele trei elemente de pe stivă, se evaluează expresia și se pune rezultatul în apoi pe stivă

Conversia între cele trei notații. Discuție.

Arbori și recursivitate

Multe probleme pe arbore se rezolvă recursiv. Pornim din rădăcină sau, dacă arborele nu are rădăcină, alegem un nod drept rădăcină. Pentru a afla valoarea proprietății P pentru un nod u, calculăm acea proprietatea în fiecare dintre fii, apoi folosim valorile fiilor pentru a afla valoarea nodului u. În frunze, care sunt cazuri terminale, valoarea lui P poate fi aflată direct.

Codul generic este

int aflăCevaDespre(u) {
  if (u este frunză) {
    return valoareaPentruFrunze;
  }
  int răspuns;
  for (v in copii(u)) {
    int x = aflăCevaDespre(v);
    răspuns = combină(răspuns, x);
  }
  return răspuns;
}

Probleme

• Să se afle înălțimea unui arbore cu rădăcină, adică distanța maximă de la oricare din frunze la rădăcină
• Să se afle, pentru fiecare nod, adâncimea, adică distanța de la el la rădăcină
• Să se afle diametrul unui arbore fără rădăcină, adică distanța maximă între oricare două frunze
• Să se afle centrul sau bicentrele unui arbore, adică nodul sau nodurile care minimizează distanța maximă până la oricare dintre frunze
• Din două parcurgeri ale unui arbore, să se reconstituie muchiile lui
  • Arbore general: preordine + postordine
  • Arbore binar: oricare dintre preordine, inordine, postordine
• Să se construiască codificarea Prüfer (nu m-am gândit la complexitate)
• Să se reconstituie arborele dându-se complexitatea Prüfer, în O(n).
• Problemă de arbori + pointeri: dându-se un arbore binar de căutare, construit clasic, cu pointeri, să se convertească la o listă dublu înlănțuită sortată
  • Problema cere să faceți aceasta doar prin manipularea pointerilor, nu prin crearea unei liste noi
  • Problema este bine definită, deoarece fiecare nod din arbore are doi pointeri (la fii), la fel ca într-o listă dublu înlănțuită.
• Se dă un arbore în care nodurile sunt codificate pe un singur caracter ASCII (pot exista duplicate). Să se tipărească arborele în mod ASCII, cu / și \ pentru muchii. De exemplu:

    4 
   / \ 
  2   5 
 / \ 
1   3

• Se dă un arbore cu rădăcină și un număr X. Să se spună dacă există o cale de la oricare frunză până la rădăcină pentru care suma nodurilor să fie X.
• Se dă un arbore fără rădăcină și un număr X. Să se spună dacă există o cale între oricare două frunze pentru care suma nodurilor să fie X.
• Se dă un arbore cu rădăcină cu n noduri și o listă de m interogări de tipul (x y). Pentru fiecare interogare să se spună dacă (1) x este strămoș al lui y, (2) y este strămoș al lui x sau (3) x și y nu se află într-o relație de strămoș/descendent.

Structuri de mulțimi disjuncte

O structură de mulțimi disjuncte (SMD) este o structură care menține în mod dinamic o partiție a mulțimii {1, 2, ..., n} sub următoarele operații:

• inițializează: pune fiecare element de la 1 la n într-o mulțime proprie cu un singur element;
• reunește(x, y): unifică mulțimile din care fac parte elementele x și y. Dacă x și y fac parte din aceeași mulțime, nu face nimic.
• găsește(x): găsește mulțimea din care face parte elementul x.

Această structură se mai numește și union-find după numele în engleză ale funcțiilor.

Pentru ca operațiile reunește și găsește să aibă sens, vom alege pentru fiecare mulțime un reprezentant, adică unul dintre numerele din mulțime. Inițial, fiecare element este singur în mulțimea lui, deci este propriul său reprezentant. La unificare, vom calcula reprezentantul reuniunii pe baza reprezentanților celor două mulțimi, după reguli pe care le vom explica.

Funcția găsește returnează reprezentantul mulțimii din care face parte x. În general ne interesează mai ales să aflăm dacă două elemente x și y fac parte din aceeași mulțime. De aceea, este important ca operația găsește să fie consecventă, adică să returneze mereu același reprezentant.

Implementare naivă cu vector

Alegem ca reprezentant al unei mulțimi elementul său minim. Stocăm aceste valori într-un vector min.

• Funcția inițializează() setează min[i] = i, căci fiecare element este singur în mulțimea lui.
• Funcția găsește(x) returnează pur și simplu min[x].
• Funcția reunește(x, y) compară min[x] cu min[y]. Dacă, de exemplu, min[x] < min[y], atunci în tot vectorul min valoarea min[y] trebuie înlocuită cu min[x].

Complexitatea este O(1) pentru găsește, dar O(n) pentru reunește.

Implementare naivă cu liste

Stocăm fiecare mulțime într-o listă înlănțuită. Reprezentantul unei mulțimi este primul element din listă. Fiecare element din listă reține un pointer către reprezentant (și, evident, un pointer către următorul element din listă).

• Funcția găsește(x) urmează pointerul lui x către reprezentant și îl returnează.
• Funcția reunește(x, y) unește ultimul element al mulțimii lui x cu primul element (reprezentantul) mulțimii lui y. Apoi redirectează toți pointerii de la reprezentantul lui y spre reprezentantul lui x.

Complexitatea este în continuare O(n) pentru reunește din cauza schimbării pointerilor.

Putem îmbunătăți operația reunește la O(log n) amortizat dacă anexăm întotdeauna mulțimea mai mică la cea mai mare. Atunci un pointer spre reprezentant poate fi redirectat de cel mult log n ori.

Implementare cu păduri

Stocăm fiecare mulțime într-un arbore cu rădăcină. Reprezentantul unei mulțimi este rădăcina arborelui.

• Funcția inițializează() creează n frunze izolate.
• Funcția găsește(x) urmează calea de la x la rădăcina arborelui său și returnează această rădăcină.
• Funcția reunește(x, y) creează o muchie de la rădăcina lui x la rădăcina lui y.

Și această structură atinge timpi de O(n) atât pentru găsește(), cât și pentru reunește(). Dați un exemplu! Totuși, există două optimizări care reduc timpii aproape la O(1).

• Comprimarea căii: în funcția găsește(x), după ce parcurgem calea de la x la rădăcina r, o mai parcurgem o dată și facem fiecare nod de pe cale să pointeze direct la r.
• Unificarea după înălțime: întotdeauna facem arborele mai turtit să pointeze la cel mai înalt.

Pentru a implementa unificarea după înălțime, nu este necesar să menținem înălțimea exactă a arborilor, ceea ce ar fi scump, ci doar o limită superioară. Mai exact:

• Inițial h[x] = 1, căci arborii sunt doar frunze izolate.
• Dacă h[x] < h[y] atunci facem rădăcina lui x fiu al rădăcinii lui y, iar h[y] rămâne nemodificat.
• Similar dacă h[x] > h[y].
• Dacă h[x] = h[y] atunci facem rădăcina lui x fiu al rădăcinii lui y, iar h[y] crește cu 1.

Oricare dintre aceste optimizări, luată separat, reduce complexitatea la O(log n) per operație. Luate împreună, ele reduc complexitatea (amortizată) la O(α(n)). Nu definim exact funcția α, dar ea crește extrem de lent, având valoarea cel mult 4 pentru toate valorile practice.

Aplicații

• conexitate dinamică: Putem adăuga muchii într-un graf, menținând dinamic lista componentelor conexe
• algoritmul lui Kruskal: Cheia algoritmului lui Kruskal pentru arbori parțiali de cost minim este să adauge muchii în arbore, în ordinea crescătoare a costului, cu condiția ca ele să nu închidă cicluri. Așadar, algoritmul se bazează pe răspunsuri rapide la întrebări de tipul „ar închide muchia (x, y) un ciclu?” sau, echivalent, „sunt x și y în aceeași componentă conexă?”.
• algoritmul de Lowest Common Ancestor (offline) al lui Tarjan (îl vom discuta în lecția următoare).

Probleme

Categoria infoarena despre mulțimi disjuncte conține 6 probleme. Categoria varena conține 3 probleme.