10/10
</> Algoritmi & Structuri de Date
Structuri de Date Avansate
Structuri de Date Avansate¶
Union-Find (Disjoint Set Union)¶
Union-Find gestionează o colecție de mulțimi disjuncte, suportând două operații:
- find(x) — determină din ce mulțime face parte elementul $x$
- union(x, y) — unește mulțimile care conțin $x$ și $y$
Unde se folosește?¶
Detectarea ciclurilor în grafuri, algoritmul Kruskal pentru MST, componente conexe, rețele sociale (clusterizare), probleme de conectivitate.
Implementare naivă¶
class UnionFindNaive:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
while self.parent[x] != x:
x = self.parent[x]
return x
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x != root_y:
self.parent[root_x] = root_y
Problema: arborii pot degenera în liste, făcând find $O(n)$.
Implementare optimizată¶
Două optimizări care fac Union-Find aproape $O(1)$ amortizat:
- Union by rank — atașăm arborele mai mic la cel mai mare
- Path compression — la
find, legăm fiecare nod direct la rădăcină
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.components = n # numărul de componente conexe
def find(self, x):
"""Găsește rădăcina cu path compression"""
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
"""Unește două mulțimi cu union by rank"""
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False # deja în aceeași mulțime
# Atașăm arborele mai mic la cel mai mare
if self.rank[rx] < self.rank[ry]:
rx, ry = ry, rx
self.parent[ry] = rx
if self.rank[rx] == self.rank[ry]:
self.rank[rx] += 1
self.components -= 1
return True
def connected(self, x, y):
return self.find(x) == self.find(y)
Complexitate amortizată: $O(\alpha(n))$ per operație, unde $\alpha$ este funcția inversă Ackermann — practic constantă ($\alpha(n) \leq 4$ pentru orice $n$ practic).
Aplicație: Kruskal MST¶
def kruskal(n, edges):
"""
Arbore de acoperire minimă — sortăm muchiile după cost,
le adăugăm dacă nu formează ciclu.
"""
edges.sort(key=lambda e: e[2]) # (u, v, weight)
uf = UnionFind(n)
mst = []
total_cost = 0
for u, v, w in edges:
if uf.union(u, v): # nu formează ciclu
mst.append((u, v, w))
total_cost += w
if len(mst) == n - 1:
break
return mst, total_cost
edges = [(0,1,4), (0,2,3), (1,2,1), (1,3,2), (2,3,5)]
mst, cost = kruskal(4, edges)
print(f"MST cost: {cost}") # 6
print(f"Muchii: {mst}") # [(1,2,1), (1,3,2), (0,2,3)]
Trie (Arbore de Prefixe)¶
Un Trie este un arbore în care fiecare nod reprezintă un caracter. Calea de la rădăcină la un nod formează un prefix al unui cuvânt.
De ce Trie?¶
| Operație | Hash Map | Trie |
|---|---|---|
| Căutare exactă | $O(L)$ | $O(L)$ |
| Căutare prefix | $O(n \cdot L)$ | $O(L)$ |
| Autocompletare | Imposibil eficient | $O(L + k)$ |
unde $L$ = lungimea cuvântului, $k$ = rezultate returnate.
Implementare¶
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
self.count = 0 # câte cuvinte trec prin acest nod
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.count += 1
node.is_end = True
def search(self, word):
"""Verifică dacă cuvântul exact există"""
node = self._find_node(word)
return node is not None and node.is_end
def starts_with(self, prefix):
"""Verifică dacă există vreun cuvânt cu acest prefix"""
return self._find_node(prefix) is not None
def count_prefix(self, prefix):
"""Câte cuvinte au acest prefix?"""
node = self._find_node(prefix)
return node.count if node else 0
def _find_node(self, prefix):
node = self.root
for ch in prefix:
if ch not in node.children:
return None
node = node.children[ch]
return node
def autocomplete(self, prefix, limit=5):
"""Returnează cuvinte care încep cu prefix"""
node = self._find_node(prefix)
if not node:
return []
results = []
def dfs(current_node, current_word):
if len(results) >= limit:
return
if current_node.is_end:
results.append(current_word)
for ch in sorted(current_node.children):
dfs(current_node.children[ch], current_word + ch)
dfs(node, prefix)
return results
Exemplu de utilizare:
trie = Trie()
words = ["apple", "app", "application", "apply", "apt", "bat", "ball"]
for w in words:
trie.insert(w)
print(trie.search("app")) # True
print(trie.search("ap")) # False
print(trie.starts_with("app")) # True
print(trie.count_prefix("app")) # 4
print(trie.autocomplete("app")) # ['app', 'apple', 'application', 'apply']
Segment Tree¶
Un Segment Tree permite interogări și actualizări pe intervale dintr-un array în $O(\log n)$.
Problema motivatoare¶
Dat un array de $n$ numere, suportăm:
- query(l, r) — suma elementelor din intervalul $[l, r]$
- update(i, val) — schimbăm valoarea la poziția $i$
| Soluție | query | update |
|---|---|---|
| Array brut | $O(n)$ | $O(1)$ |
| Sume parțiale | $O(1)$ | $O(n)$ |
| Segment Tree | $O(\log n)$ | $O(\log n)$ |
Cum funcționează?¶
Arborele împarte array-ul recursiv în jumătăți. Fiecare nod stochează informația agregată (sumă, minim, maxim, etc.) pentru un interval.
Array: [2, 1, 5, 3, 4, 2]
[17] (sum 0..5)
/ \
[8] [9] (sum 0..2, 3..5)
/ \ / \
[3] [5] [7] [2] (sum 0..1, 2..2, 3..4, 5..5)
/ \ / \
[2] [1] [3] [4] (frunze)
Implementare¶
class SegmentTree:
def __init__(self, data):
self.n = len(data)
self.tree = [0] * (4 * self.n)
self._build(data, 1, 0, self.n - 1)
def _build(self, data, node, start, end):
if start == end:
self.tree[node] = data[start]
return
mid = (start + end) // 2
self._build(data, 2 * node, start, mid)
self._build(data, 2 * node + 1, mid + 1, end)
self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
def update(self, idx, val, node=1, start=0, end=None):
"""Actualizează elementul de la indexul idx cu valoarea val"""
if end is None:
end = self.n - 1
if start == end:
self.tree[node] = val
return
mid = (start + end) // 2
if idx <= mid:
self.update(idx, val, 2 * node, start, mid)
else:
self.update(idx, val, 2 * node + 1, mid + 1, end)
self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
def query(self, l, r, node=1, start=0, end=None):
"""Returnează suma pe intervalul [l, r]"""
if end is None:
end = self.n - 1
# Interval complet în afara range-ului
if r < start or end < l:
return 0
# Interval complet inclus
if l <= start and end <= r:
return self.tree[node]
# Interval parțial — split
mid = (start + end) // 2
left_sum = self.query(l, r, 2 * node, start, mid)
right_sum = self.query(l, r, 2 * node + 1, mid + 1, end)
return left_sum + right_sum
Exemplu:
data = [2, 1, 5, 3, 4, 2]
st = SegmentTree(data)
print(st.query(1, 4)) # 1 + 5 + 3 + 4 = 13
st.update(2, 10) # data[2] = 10 (era 5)
print(st.query(1, 4)) # 1 + 10 + 3 + 4 = 18
print(st.query(0, 5)) # 2 + 1 + 10 + 3 + 4 + 2 = 22
Generalizare¶
Segment Tree funcționează cu orice operație asociativă: sumă, minim, maxim, GCD, XOR, etc. Trebuie doar să schimbi operația de combinare:
# Pentru Range Minimum Query (RMQ):
self.tree[node] = min(self.tree[2*node], self.tree[2*node+1])
# Pentru Range Maximum Query:
self.tree[node] = max(self.tree[2*node], self.tree[2*node+1])
# Pentru Range GCD:
from math import gcd
self.tree[node] = gcd(self.tree[2*node], self.tree[2*node+1])
Recapitulare¶
| Structură | Operație cheie | Complexitate | Folosită pentru |
|---|---|---|---|
| Union-Find | union, find | $O(\alpha(n)) \approx O(1)$ | Conectivitate, MST |
| Trie | prefix search | $O(L)$ | Autocompletare, dicționare |
| Segment Tree | range query + update | $O(\log n)$ | Interogări pe intervale |
Exerciții¶
- Folosind Union-Find, detectați dacă adăugarea unei muchii într-un graf creează un ciclu
- Implementați delete într-un Trie, eliminând nodurile care nu mai sunt necesare
- Modificați Segment Tree pentru a suporta Lazy Propagation — actualizări pe întreg intervalul $[l, r]$ în $O(\log n)$
- Implementați un Trie care suportă wildcard search (
.înlocuiește orice caracter)
Pe această pagină