İçeriğe geç

Path compression

Ders 2 / 4 · 5 dk

Path compression

Adım 1/10

Bir zincir: 0, 1'i gösterir, 1 de 2'yi, 4'e kadar. Her find hepsini baştan yürümek zorunda.

Fikir

Union işlemleri uzun bir zincir kurabilir; sonra her find o zinciri baştan dolaşır. Oysa ilk dolaşma cevabı çoktan öğrenmişti.

O yüzden aynı yol üzerinden ikinci bir geçiş yap ve her düğümü (node) doğrudan köke yönlendir. Bir kez bedelini ödediğin yol, ondan sonra onu kullanan herkes için düz kalır.

Gerçek hayattan örnek

Seni yardım edebilecek tek kişiye ulaştırmadan önce üç departmandan geçiren bir telefon menüsü düşün. İkinci seferde doğrudan o kişinin numarasını ararsın. Kimse rotayı yeniden çıkarmaz, çünkü rota not etmeye değerdi.

Kod

Sıra sende

Bu kod ne yazdırır?

parent = [1, 2, 2]
def find(x):
  root = x
  while parent[root] != root:
      root = parent[root]
  while parent[x] != root:
      parent[x], x = root, parent[x]
  return root
find(0)
print(parent)

Mini quiz

1 / 3

Path compression ne zaman olur?