Clasele 11-12 lecția 13 - 10 dec 2014

Întrucât aceasta este ultima lecție predată în anul 2014, nu intrăm în cuplaje și fluxuri, căci ne trebuie 2 lecții acolo, posibil 2,5. În schimb, discutăm despre arbori și ne pregătim pentru algoritmi de LCA/RMQ.

Arbori

Definiție, proprietăți

Definiția „oficială” este:

• un arbore neorientat este un graf neorientat conex aciclic

Următoarele cinci sunt definiții alternative și echivalente

• un arbore este un graf neorientat în care între oricare două noduri există exact o cale
• un arbore este un graf conex minimal
• un arbore este un graf aciclic maximal
• 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

Cum demonstrăm echivalența acestor 6 afirmații? Dorim să facem minim de efort. Indiciu: cum construim un graf tare conex cu 6 noduri și cu număr minim de muchii? :-) Vom încerca să demonstrăm câteva dintre implicații.

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ă)
  • vezi problema Lista (de la Campion)
• pentru arborii binari: oricare două din cele trei parcurgeri: preordine, inordine, postordine
  • vezi problema Prepost, dată anul trecut ca temă

Parcurgeri

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

Spre deosebire de grafuri, la arbori neorientați nu avem nevoie să menținem un vector caracteristic cu nodurile vizitate. Într-adevăr, cum putem „evada” dintr-un subarbore pentru a ajunge într-o zonă deja vizitată? Numai prin muchia către părinte. Deci fiecare apel dfs() va primi, pe lângă nodul u, și părintele p care a apelat acel nod. La iterarea prin vecini, u se va reapela pentru toți în afară de p.

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.

Iată o sursă: Media:arithmetic-expression-parser.cpp

(În limita timpului, întrebare suplimentară: este acesta un automat finit? Discuție despre automatele cu stivă).

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 proprietate î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).
• Problema 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 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.
• Problema Pom: Se dau o listă de nume de funcții și pentru fiecare se cunoaște numărul de argumente. Apoi se dă o expresie cu funcții, virgule și paranteze. Să se decidă dacă expresia este corectă.

Algoritmul LCA offline

(În limita timpului)

Problema LCA (Lowest Common Ancestor) spune: se dă un arbore cu rădăcină și M perechi de noduri de forma (x, y). Pentru fiecare pereche, să se tipărească cel mai jos strămoș comun al lui x și y.

Despre varianta online a problemei (în care nu cunoaștem de la început perechile) vom vorbi într-o lecție viitoare. Varianta offline, în care perechile se dau de la bun început, admite o soluție elegantă în O(n), bazată pe structuri de mulțimi disjuncte.

Există o observație care stă la baza algoritmului. Să considerăm că parcurgem arborele în adâncime. Să spunem că suntem undeva într-un nod u și deja am vizitat o parte din fiii lui și subarborii lor (dar nu pe toți). Atunci putem răspunde la unele interogări care îl conțin pe u, dar nu la toate. Dintre interogările (u, v), putem răspunde la cele în care nodul v a fost deja vizitat în parcurgere. Mai exact:

• Dacă v se află într-unul din subarborii deja vizitați ai lui u, răspunsul este u.
• Dacă v se află pe calea de la u la rădăcină, răspunsul este v.
• Altfel, pe măsură ce terminăm de traversat subarbori, îi unificăm (în sensul de union-find) cu rădăcina lor. Pentru acele noduri, răspunsul va fi rădăcina, cât timp continuăm să parcurgem ceilalți subarbori ai rădăcinii.

Temă

• Tema 10 seniori