Ağırlıklı Birleştirme ile Dengeli Ağaçlar
Quick-Union'ın problemi uzun ağaçlardı. Çözüm basit: Union yaparken küçük ağacı büyük ağaca bağla.
Bu basit değişiklik, ağaç yüksekliğini O(N)'den O(log N)'e düşürüyor!
İddia: Weighted Quick-Union'da, N düğümlü bir ağacın yüksekliği en fazla lg(N)'dir.
Kanıt:
Sonuç: Herhangi bir düğümün derinliği ≤ lg(N) ✓
class WeightedQuickUnion:
"""
Weighted Quick-Union Implementasyonu
İyileştirme: Union sırasında küçük ağacı büyüğe bağla.
Bu sayede ağaç yüksekliği O(log N)'de kalır.
Veri yapısı:
- parent[i]: i'nin ebeveyni
- size[i]: i root ise, ağacın toplam düğüm sayısı
"""
def __init__(self, n: int):
"""
N düğüm ile başlat.
Her düğüm kendi ağacı, boyut = 1.
"""
self.parent = list(range(n))
self.size = [1] * n # Her ağacın boyutu
self.n = n
self._count = n
def find(self, p: int) -> int:
"""
p'nin root'unu bul.
Zaman: O(log N) - ağaç yüksekliği garantili
"""
while self.parent[p] != p:
p = self.parent[p]
return p
def connected(self, p: int, q: int) -> bool:
"""p ve q aynı ağaçta mı?"""
return self.find(p) == self.find(q)
def union(self, p: int, q: int) -> None:
"""
p ve q'nun ağaçlarını birleştir.
ÖNEMLI: Küçük ağacı büyüğe bağla!
Zaman: O(log N)
"""
root_p = self.find(p)
root_q = self.find(q)
if root_p == root_q:
return
# ★ WEIGHTED: Küçük ağacı büyüğe bağla
if self.size[root_p] < self.size[root_q]:
# p'nin ağacı daha küçük → p'yi q'ya bağla
self.parent[root_p] = root_q
self.size[root_q] += self.size[root_p]
else:
# q'nun ağacı daha küçük (veya eşit) → q'yu p'ye bağla
self.parent[root_q] = root_p
self.size[root_p] += self.size[root_q]
self._count -= 1
def count(self) -> int:
return self._count
def tree_height(self, root):
"""Belirli bir ağacın yüksekliğini hesapla"""
max_depth = 0
for i in range(self.n):
depth = 0
p = i
while self.parent[p] != p:
p = self.parent[p]
depth += 1
if p == root:
max_depth = max(max_depth, depth)
return max_depth
# ===== DEMO =====
print("=" * 60)
print("WEIGHTED QUICK-UNION DEMO")
print("=" * 60)
wqu = WeightedQuickUnion(10)
# İşlemler - Quick-Union'da kötü olan sıra
operations = [
(4, 3), (3, 8), (6, 5), (9, 4), (2, 1),
(5, 0), (7, 2), (6, 1), (8, 0)
]
print("\nUnion işlemleri:")
for p, q in operations:
wqu.union(p, q)
print(f"\nparent[]: {wqu.parent}")
print(f"size[]: {wqu.size}")
print(f"Küme sayısı: {wqu.count()}")
# Ağaç yüksekliklerini hesapla
roots = [i for i in range(10) if wqu.parent[i] == i]
print(f"\nAğaç yükseklikleri:")
for root in roots:
h = wqu.tree_height(root)
members = [i for i in range(10) if wqu.find(i) == root]
print(f" Root {root}: yükseklik={h}, üyeler={members}")
# Teorik maksimum
import math
print(f"\nTeorik maksimum yükseklik: lg(10) = {math.log2(10):.2f}")
print("Gerçek yükseklikler bunun altında ✓")class QuickUnion:
"""Normal Quick-Union (karşılaştırma için)"""
def __init__(self, n):
self.parent = list(range(n))
self.find_cost = 0
def find(self, p):
while self.parent[p] != p:
p = self.parent[p]
self.find_cost += 1
return p
def union(self, p, q):
root_p, root_q = self.find(p), self.find(q)
if root_p != root_q:
self.parent[root_p] = root_q
class WeightedQuickUnion:
"""Weighted Quick-Union"""
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
self.find_cost = 0
def find(self, p):
while self.parent[p] != p:
p = self.parent[p]
self.find_cost += 1
return p
def union(self, p, q):
root_p, root_q = self.find(p), self.find(q)
if root_p != root_q:
if self.size[root_p] < self.size[root_q]:
self.parent[root_p] = root_q
self.size[root_q] += self.size[root_p]
else:
self.parent[root_q] = root_p
self.size[root_p] += self.size[root_q]
def worst_case_test(n):
"""En kötü durum senaryosu"""
qu = QuickUnion(n)
wqu = WeightedQuickUnion(n)
# Kötü sırayla union (zincir oluşturma)
for i in range(n - 1):
qu.union(i, i + 1)
wqu.union(i, i + 1)
# Tüm elemanlar için find
for i in range(n):
qu.find(i)
wqu.find(i)
return qu.find_cost, wqu.find_cost
print("=" * 60)
print("QUICK-UNION vs WEIGHTED QUICK-UNION")
print("=" * 60)
print(f"\n{'N':>8} {'QU Maliyet':>15} {'WQU Maliyet':>15} {'İyileşme':>12}")
print("-" * 60)
for n in [10, 50, 100, 500, 1000]:
qu_cost, wqu_cost = worst_case_test(n)
improvement = qu_cost / wqu_cost if wqu_cost > 0 else float('inf')
print(f"{n:>8} {qu_cost:>15,} {wqu_cost:>15,} {improvement:>11.1f}x")
print("\n" + "─" * 60)
print("💡 Analiz:")
print("─" * 60)
print("""
Quick-Union (QU): En kötü durumda zincir → O(N²) toplam maliyet
Weighted QU: Her zaman dengeli → O(N log N) toplam maliyet
N büyüdükçe fark DRAMATIK artıyor!
- N=1000: ~100x daha hızlı
- N=1,000,000: ~50,000x daha hızlı olur!
""")İki farklı yaklaşım var:
Her ikisi de O(log N) garanti eder. Size genelde daha kolay implement edilir.
class UnionByRank:
"""
Union by Rank Implementasyonu
Rank = ağacın tahmini yüksekliği
(Path compression olmadan gerçek yükseklik,
path compression ile üst sınır)
"""
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n # Başlangıçta hepsi 0 (tek düğüm)
self.n = n
def find(self, p):
while self.parent[p] != p:
p = self.parent[p]
return p
def union(self, p, q):
root_p = self.find(p)
root_q = self.find(q)
if root_p == root_q:
return
# Rank'ı düşük olanı yüksek olana bağla
if self.rank[root_p] < self.rank[root_q]:
self.parent[root_p] = root_q
elif self.rank[root_p] > self.rank[root_q]:
self.parent[root_q] = root_p
else:
# Eşit rank: birini diğerine bağla, rank artır
self.parent[root_q] = root_p
self.rank[root_p] += 1
# Demo
print("=" * 50)
print("UNION BY RANK DEMO")
print("=" * 50)
ubr = UnionByRank(8)
unions = [(0, 1), (2, 3), (0, 2), (4, 5), (6, 7), (4, 6), (0, 4)]
print("\nUnion işlemleri:")
for p, q in unions:
print(f"\nunion({p}, {q}):")
ubr.union(p, q)
print(f" parent[]: {ubr.parent}")
print(f" rank[]: {ubr.rank}")
# Ağaç yapısını göster
print("\n" + "─" * 50)
print("Final ağaç yapısı:")
def show_tree(parent, n):
root = [i for i in range(n) if parent[i] == i][0]
def get_children(node):
return [i for i in range(n) if parent[i] == node and i != node]
def print_tree(node, prefix="", is_last=True):
connector = "└── " if is_last else "├── "
print(prefix + connector + str(node))
children = get_children(node)
for i, child in enumerate(children):
is_last_child = (i == len(children) - 1)
new_prefix = prefix + (" " if is_last else "│ ")
print_tree(child, new_prefix, is_last_child)
print_tree(root, "", True)
show_tree(ubr.parent, 8)| Algoritma | init | find | union | M işlem |
|---|---|---|---|---|
| Quick-Find | O(N) | O(1) | O(N) | O(MN) |
| Quick-Union | O(N) | O(N)* | O(N)* | O(MN) |
| Weighted QU | O(N) | O(log N) | O(log N) | O(M log N) |
* En kötü durumda
Weighted Quick-Union ile O(N)'den O(log N)'e düştük.
N = 10⁹ için: 1,000,000,000 adım yerine sadece ~30 adım!
Peki daha hızlı yapabilir miyiz? Evet! Path Compression ile neredeyse O(1) yapabiliriz.
Bir sonraki bölüm: Path Compression ve Final Analiz! ⚡