Pe scurt
Structurile de date neliniare (arbori binari, arbori generali, grafuri) modelează relații complexe între elemente, spre deosebire de structurile liniare. Arborii binari de căutare permit căutări eficiente (O(log n) în caz echilibrat), iar grafurile sunt cele mai generale structuri, reprezentate prin matrice sau liste de adiacență. Pentru Bacalaureat, accentul cade pe operații de bază în BST și pe algoritmi de parcurgere BFS/DFS pentru grafuri.
Definiții și proprietăți fundamentale
Arbori binari
- Arbore binar: structură ierarhică în care fiecare nod are cel mult doi copii (stânga și dreapta)
- Proprietăți cheie:
-
Înălțimea: numărul maxim de muchii de la rădăcină la o frunză
- Numărul de noduri: maximum 2^h - 1 pentru un arbore binar complet
- În adâncime: preordine, inordine, postordine
- În lățime: pe niveluri
Arbori binari de căutare (BST)
- Proprietatea fundamentală: pentru orice nod, toate valorile din subarborele stâng sunt mai mici, iar cele din dreapta sunt mai mari
- Căutări eficiente: O(log n) în cazul echilibrat
- Operații de bază: inserare, ștergere, căutare
Arbori generali
- Definiție: permit oricărui nod să aibă oricâți copii
- Aplicații: reprezentarea ierarhiilor (sisteme de fișiere, organizații)
- Parcurgere: similară cu arborii binari, dar fără limită de copii
Grafurile
- Definiție: set de noduri (vârfuri) conectate prin muchii (orientate sau neorientate)
- Reprezentare:
-
Matrice de adiacență: O(n^2) memorie
- Liste de adiacență: O(n+m)
-
BFS (breadth-first search): parcurgere pe nivel, găsirea celui mai scurt drum în grafuri neponderate
- DFS (depth-first search): detectarea ciclurilor și componentelor conexe
Exemple practice
Exemplul 1: Arbore binar de căutare - inserare și parcurgere inordine
- Valori de inserat: [7, 3, 9, 1, 5] într-un BST inițial gol
- Pași:
- Se inserează 7 (rădăcina)
- 3 se plasează în stânga
- 9 în dreapta
- 1 în stânga lui 3
- 5 în dreapta lui 3
- Parcurgerea inordine (stânga, rădăcină, dreapta): 1, 3, 5, 7, 9 (șir sortat)
Exemplul 2: Graf neorientat - parcurgere BFS și detecție componentă conexă
- Graful: nodurile 1-6, muchiile: (1,2), (1,3), (2,4), (3,4), (5,6)
- BFS pornind din nodul 1:
- Vizitează 1
- Apoi vecinii 2 și 3
- Apoi vecinul lui 2 = 4
- Apoi vecinul lui 4 (deja vizitat)
- Rezultat: componenta conexă {1,2,3,4}; nodurile 5 și 6 formează o altă componentă
- Implementare BFS: cu o coadă; ajută la aflarea distanțelor minime
Exemplul 3: Arbore general - reprezentare cu liste de copii
- Modelare director cu fișiere:
- Rădăcina = 'C:'
- Copii = ['Programs', 'Users', 'Windows']
- 'Users' are copiii ['Alice', 'Bob']
- 'Alice' are fișierul 'document.txt'
- Parcurgerea în adâncime (DFS) folosind stivă implicită (recursiv): C:, Programs, Users, Alice, document.txt, Bob, Windows
Concepte cheie pentru Bacalaureat
- Arbore binar de căutare (BST) și proprietățile sale
- Parcurgeri în adâncime (preordine, inordine, postordine) și în lățime (BFS)
- Reprezentarea grafurilor (matrice și liste de adiacență)
- Componente conexe și algoritmi BFS/DFS
- Arbori generali și aplicații ierarhice
Verifică-te!
- Care este proprietatea fundamentală a unui arbore binar de căutare (BST)?
- Ce diferență există între reprezentarea unui graf prin matrice de adiacență și prin liste de adiacență?
- Ce algoritm de parcurgere se folosește pentru a găsi cel mai scurt drum într-un graf neponderat?