---
title: 'Kümeler ve Çok Kümeler'
source: 'https://academia.sh/tr/kurslar/veri-yapilari/kumeler'
course: 'Veri Yapıları'
language: tr
updated: '2026-08-17T18:07:51+00:00'
license: 'CC BY-SA 4.0'
---

# Kümeler ve Çok Kümeler

Üyelik odaklı soyut tip, karma ve sıralı gerçekleştirimler, bit kümeleri ve sayaçlı çok kümeler.

Karma tablosu bir anahtarı bir değere eşler. Bazı problemlerde değer yoktur; sorulan tek
soru **"bu eleman var mı"** olur. Yinelenenlerin ayıklanması, bir kimliğin listede olup
olmadığının sınanması, iki koleksiyonun ortak elemanlarının bulunması bu sınıftandır.

**Küme (set)**, üyelik odaklı soyut veri tipidir: her eleman ya vardır ya yoktur, sayısı
tutulmaz, sırası tanımlı değildir.

## Küme İşlemleri

| İşlem | Anlamı |
|---|---|
| `ekle` | Elemanı kümeye katar; zaten varsa değişiklik olmaz |
| `sil` | Elemanı çıkarır |
| `iceriyor_mu` | Üyelik sınaması |
| `birlesim` | İki kümenin tüm elemanları |
| `kesisim` | İkisinde birden bulunanlar |
| `fark` | Birincide olup ikincide olmayanlar |
| `alt_kume_mu` | Kapsama sınaması |

İlk üçü tekil elemanla, son dördü küme çiftiyle çalışır. Maliyetleri farklı düşünülür:
tekil işlemler eleman sayısından bağımsız olabilirken, küme işlemleri en az bir kümeyi
gezmek zorundadır.

## Gerçekleştirim Seçenekleri

**Karma kümesi**, değeri olmayan bir karma tablosudur. Tekil işlemler ortalama sabit
zamanlıdır; sıra korunmaz.

**Sıralı küme**, elemanları sıralı tutan bir yapıyla (dengeli ağaç veya atlama listesi)
kurulur. Tekil işlemler logaritmiktir; karşılığında elemanlar sıralı gezilebilir ve
aralık sorgusu yapılabilir — "değeri 10 ile 20 arasında olanlar" gibi.

Seçim ölçütü nettir: sıra veya aralık gerekmiyorsa karma kümesi, gerekiyorsa sıralı
küme.

## Bit Kümesi

Elemanlar $0$ ile $N-1$ arasındaki tam sayılarsa ve $N$ makul büyüklükteyse, üçüncü ve
çok daha verimli bir gerçekleştirim vardır: her eleman için tek bir bit.

**Bit kümesi (bitset)**, üyeliği bit düzeyinde tutar. Bilgisayarlar Nasıl Çalışır
kursundaki bit düzeyi işlemler burada doğrudan kullanılır.

```python
class BitKumesi:
    """0..N-1 aralığındaki tam sayıları bit düzeyinde tutar."""

    def __init__(self, evren: int) -> None:
        self.evren = evren
        self._bitler = 0                       # tek bir büyük tam sayı

    def ekle(self, deger: int) -> None:
        self._bitler |= 1 << deger             # ilgili biti kur

    def sil(self, deger: int) -> None:
        self._bitler &= ~(1 << deger)          # ilgili biti sıfırla

    def iceriyor_mu(self, deger: int) -> bool:
        return ((self._bitler >> deger) & 1) == 1

    def birlesim(self, digeri: "BitKumesi") -> "BitKumesi":
        sonuc = BitKumesi(self.evren)
        sonuc._bitler = self._bitler | digeri._bitler
        return sonuc

    def kesisim(self, digeri: "BitKumesi") -> "BitKumesi":
        sonuc = BitKumesi(self.evren)
        sonuc._bitler = self._bitler & digeri._bitler
        return sonuc

    def elemanlar(self) -> list[int]:
        return [i for i in range(self.evren) if self.iceriyor_mu(i)]

    def __len__(self) -> int:
        return bin(self._bitler).count("1")    # kurulu bit sayısı


a = BitKumesi(16)
b = BitKumesi(16)
for d in (1, 3, 5, 7):
    a.ekle(d)
for d in (3, 5, 9):
    b.ekle(d)

print(a.elemanlar(), b.elemanlar())            # [1, 3, 5, 7] [3, 5, 9]
print(a.kesisim(b).elemanlar())                # [3, 5]
print(a.birlesim(b).elemanlar())               # [1, 3, 5, 7, 9]
print(len(a), a.iceriyor_mu(7), a.iceriyor_mu(8))   # 4 True False
```

İki üstünlüğü vardır ve ikisi de büyüktür.

**Bellek.** Eleman başına bir bit kullanılır. Bir milyon elemanlık evren, 125 kilobayta
sığar; aynı kümeyi karma kümesiyle tutmak, eleman başına onlarca bayt ister.

**Küme işlemleri sözcük düzeyinde paraleldir.** İki bit kümesinin kesişimi, tek bir VE
işlemidir; işlemci 64 elemanı tek komutta işler. Karma kümesinde aynı işlem, elemanların
tek tek gezilmesini gerektirir.

Koşulu ise dardır: evren küçük ve yoğun olmalıdır. Elemanlar milyarlar arasında dağınık
birkaç değerse, bit kümesi bellek israfına döner. Bu durumda seyrek gösterimler veya
karma kümesi tercih edilir.

Bit kümeleri, veritabanı dizinlerinde satır kümelerini birleştirmek, çizge
algoritmalarında ziyaret edilmiş düğümleri işaretlemek ve izin kümelerini tutmak için
yaygın kullanılır.

## Çok Küme

Küme, bir elemanın var olup olmadığını söyler; **kaç kez** var olduğunu söylemez. Sayı
gerektiğinde **çok küme (multiset)** kullanılır: her elemanla birlikte bir sayaç tutulur.

```python
def frekans(olcumler: list[int]) -> dict[int, int]:
    """Her değerin kaç kez geçtiğini sayar."""
    sayac: dict[int, int] = {}
    for olcum in olcumler:
        sayac[olcum] = sayac.get(olcum, 0) + 1
    return sayac


olcumler = [12, 18, 7, 12, 25, 12, 18]
print(frekans(olcumler))                       # {12: 3, 18: 2, 7: 1, 25: 1}
print(max(frekans(olcumler).items(), key=lambda c: c[1]))   # (12, 3)
```

Çok küme, aslında değeri sayı olan bir eşlemedir; ayrı bir yapı olarak anılmasının
nedeni, küme işlemlerinin sayaçlarla tanımlanmasıdır: birleşimde sayaçların en büyüğü,
kesişimde en küçüğü alınır.

Tipik kullanımı sayım problemleridir: sözcük frekansları, en sık geçen değerler, örneklem
dağılımları. Veri analitiği müfredatındaki frekans çözümlemeleri bu yapının üzerine
kurulur.

## Küme mi Liste mi

Yaygın bir başarım hatası, üyelik sınamasının liste üzerinde yapılmasıdır. Liste araması
doğrusaldır; aynı sınama küme üzerinde ortalama sabittir.

```python
kimlikler = list(range(100_000))
kume = set(kimlikler)

# Liste üzerinde üyelik: her sorgu tüm listeyi tarayabilir.
print(99_999 in kimlikler)      # True — en kötü durumda 100.000 karşılaştırma
# Küme üzerinde üyelik: karma ile tek adım.
print(99_999 in kume)           # True — kova hesabı ve birkaç karşılaştırma
```

Fark, sınama sayısıyla çarpılır: bir liste içinde $m$ sorgu yapmak $O(n \cdot m)$,
kümede $O(m)$'dir. Bir döngü içinde yapılan üyelik sınaması bu nedenle standart bir
gözden geçirme noktasıdır.

Kümeye dönüştürmenin de bir maliyeti vardır — tüm elemanların eklenmesi $O(n)$. Tek bir
sorgu için dönüştürmek anlamsızdır; sorgu sayısı arttıkça dönüşüm kendini öder.

## Küme İşlemlerinin Maliyeti

İki kümenin kesişimi hesaplanırken küçük kümenin gezilip büyük kümede üyelik sınanması,
tersinden yapmaktan ucuzdur:

$$
O(\min(\lvert A\rvert, \lvert B\rvert)) \quad \text{yerine} \quad O(\lvert A\rvert)
$$

Bu ayrıntı, büyük veri kümeleriyle çalışırken belirgin fark yaratır ve kütüphane
gerçekleştirimlerinin çoğu bunu kendiliğinden yapar.

Sıralı kümelerde ise farklı bir yol vardır: iki sıralı diziyi birleştirir gibi tek
geçişte ilerlemek, $O(\lvert A\rvert + \lvert B\rvert)$ maliyetle tüm küme işlemlerini verir ve ek bellek
gerektirmez.

## Maliyet Tablosu

| Yapı | Üyelik | Ekleme | Kesişim | Sıra |
|---|---|---|---|---|
| Karma kümesi | $O(1)$ ortalama | $O(1)$ ortalama | $O(\min(\lvert A\rvert, \lvert B\rvert))$ | Yok |
| Sıralı küme | $O(\log n)$ | $O(\log n)$ | $O(\lvert A\rvert + \lvert B\rvert)$ | Var |
| Bit kümesi | $O(1)$ | $O(1)$ | $O(N / w)$* | Değere göre |

\* $w$, işlemcinin sözcük genişliği; $N$ evren büyüklüğü.

## Özet

- Küme, üyelik odaklı soyut tiptir; eleman ya vardır ya yoktur, sayısı ve sırası
  tutulmaz.
- Karma kümesi tekil işlemleri ortalama sabit zamanda yapar ama sıra korumaz; sıralı
  küme logaritmik maliyetle sıra ve aralık sorgusu sağlar.
- Bit kümesi, küçük ve yoğun tam sayı evrenlerinde eleman başına tek bit kullanır ve
  küme işlemlerini sözcük düzeyinde paralel yapar.
- Çok küme, elemanla birlikte sayaç tutar; sayım problemlerinin doğal yapısıdır.
- İki küme kesiştirilirken küçük olanın gezilmesi, maliyeti küçük kümenin boyutuna
  indirir.

## Sonraki Adım

Buraya kadar kümeler bağımsız düşünüldü. Bazı problemlerde ise sorulan soru farklıdır:
"bu iki eleman aynı grupta mı?" ve gruplar zamanla birleşiyor. Sonraki ders, bu soruyu
neredeyse sabit zamanda yanıtlayan ayrık küme yapısını ele alacak.