---
marp: true
theme: kurzus
paginate: true
footer: Adatszerkezetek · 6. hét · Halmaz
---

<!-- _class: cim -->
<!-- _paginate: false -->
<!-- _footer: "" -->

# Adatszerkezetek

## 6. hét – A halmaz adatszerkezet: ábrázolások és műveletek

Dr. Koczka Ferenc · Eszterházy Károly Egyetem · 2026

---

## Ismétlés

- **Tömb:** közvetlen elérés O(1), beszúrás/törlés O(n)
- **Bináris keresés** rendezett tömbön: O(log n)
- **Rendezések:** buborék, kiválasztásos, beszúrásos – O(n²)
- **Összefésülés** (3. hét, 5. feladat): két rendezett tömbből egy rendezett tömb, O(n + m)

### A mai óra kérdései

- Hogyan ábrázolhatunk egy matematikai halmazt a számítógépen?
- Melyik ábrázolásban milyen gyorsak a halmazműveletek?

<!--
Időterv: matematikai háttér 10' · logikai vektor 25' · rendezetlen ábrázolás 20' · rendezett ábrázolás 25' · beépített halmazok, összefoglalás 10'
-->

---

## Matematikai háttér

**Halmaz:** különböző elemek **rendezetlen** gyűjteménye.

- Minden elem **legfeljebb egyszer** szerepel: {1, 2, 2} = {1, 2}
- A sorrend **nem számít**: {1, 2} = {2, 1}
- Jelölések: x ∈ A (eleme) · |A| (elemszám) · ∅ (üres halmaz) · **U** (alaphalmaz, univerzum)

| Művelet | Jelölés | Jelentés |
|---|---|---|
| Eleme-e? | x ∈ A | x benne van-e A-ban |
| Részhalmaz | A ⊆ B | A minden eleme B-nek is eleme |
| Unió | A ∪ B | A **vagy** B elemei |
| Metszet | A ∩ B | A **és** B közös elemei |
| Különbség | A \ B | A azon elemei, amelyek **nincsenek** B-ben |

---

## Halmazműveletek szemléltetése

![w:1000](kepek/h06_venn.svg)

**Példa** – U = a hét napjai:
A = {H, Sze, Cs, Szo} (napok, amikor edzés van) · B = {K, Sze, Cs} (napok, amikor óra van)

A ∪ B = {H, K, Sze, Cs, Szo} · A ∩ B = {Sze, Cs} · A \ B = {H, Szo}

---

## A halmaz mint adatszerkezet

| Tulajdonság | Halmaz |
|---|---|
| Elemek | homogén |
| Kapcsolat az elemek között | **nincs** (nincs sorrend) |
| Méret | dinamikus (bővíthető, csökkenthető) |
| Ismétlődés | nincs |

**Ábrázolási lehetőségek** (mind tömbön alapul):

1. **Logikai vektor** (karakterisztikus vektor, bitvektor)
2. **Rendezetlen** tömb (sorozat)
3. **Rendezett** tömb (sorozat)
4. Hash tábla (11. hét), keresőfa (15. hét)

---

<!-- _class: fejezet -->

# Ábrázolás logikai vektorral

---

## Logikai vektor

Ha az **alaphalmaz kicsi és ismert** (U = {u₁, …, uₙ}), minden halmaz egy *n* hosszú logikai vektor: **A[i] = igaz ⇔ uᵢ ∈ A**

![w:1000](kepek/h06_logikai.svg)

---

<!-- _class: kicsi -->

## Logikai vektor – műveletek

<div class="ket-hasab">
<div>

<span class="cimke pszeudo">Pszeudokód</span>

```text
Függvény Eleme(A, i)          // O(1)
  Vissza: A[i]
Függvény vége

Eljárás Unió(A, B, C, n)       // O(n)
  Ciklus i ← 1-től n-ig
    C[i] ← A[i] vagy B[i]
  Ciklus vége
Eljárás vége

// Metszet: C[i] ← A[i] és B[i]
// Különbség: C[i] ← A[i] és nem B[i]

Függvény Része(A, B, n)        // A ⊆ B ?
  i ← 1
  Ciklus amíg i ≤ n és (nem A[i] vagy B[i])
    i ← i + 1
  Ciklus vége
  Vissza: i > n
Függvény vége
```

</div>
<div>

<span class="cimke java">Java</span>

```java
boolean[] in = new boolean[7];

BitVectorSet union(BitVectorSet o) {
    BitVectorSet r = new BitVectorSet();
    for (int i = 0; i < in.length; i++)
        r.in[i] = in[i] || o.in[i];
    return r;
}
```

| Művelet | Lépésszám |
|---|---|
| eleme-e, bővítés, törlés | **O(1)** |
| unió, metszet, különbség | O(\|U\|) |
| részhalmaz | O(\|U\|) |
| elemszám | O(\|U\|) |

</div>
</div>

---

## Bitmaszk: egy bit = egy elem

Ha |U| ≤ 64, a teljes halmaz elfér **egyetlen egész számban**: az *i*-edik bit jelzi, hogy uᵢ ∈ A.

| Művelet | Java | Go | Példa (A = 0101101, B = 0001110) |
|---|---|---|---|
| unió | `a \| b` | `a \| b` | 0101111 |
| metszet | `a & b` | `a & b` | 0001100 |
| különbség | `a & ~b` | `a &^ b` | 0100001 |
| eleme-e (i) | `(a >> i & 1) == 1` | `a>>i&1 == 1` | |
| részhalmaz | `(a & ~b) == 0` | `a&^b == 0` | |
| elemszám | `Integer.bitCount(a)` | `bits.OnesCount(a)` | 4 |

<div class="doboz tipp">

Egy halmazművelet = **egyetlen processzorutasítás**. Alkalmazás: jogosultságok (olvasás/írás/futtatás), napok, beállítások.

</div>

---

## Logikai vektor – előnyök és korlátok

**Előnyök:**

- Leggyorsabb: eleme-e **O(1)**, a halmazműveletek bitmaszkkal egy lépésben
- Egyszerű megvalósítás

**Korlátok:**

- Az alaphalmaznak **kicsinek és előre ismertnek** kell lennie
- A tárigény |U|-val arányos, nem az elemek számával
  pl. egész számok halmaza 0 … 10⁹ között: 10⁹ bit ≈ **125 MB** – akkor is, ha csak 3 elem van benne!
- Az elemeket egy **sorszámmal** kell azonosítani (H → 0, K → 1, …)

---

<!-- _class: fejezet -->

# Ábrázolás rendezetlen tömbbel

---

## Rendezetlen tömb

Az elemeket egy tömbben tároljuk, **tetszőleges sorrendben**, ismétlődés nélkül.

A = `[8, 2, 11, 5]` · B = `[9, 5, 14, 3, 11]`

- **Eleme-e?** lineáris keresés – O(n)
- **Bővítés:** előbb meg kell nézni, benne van-e már (O(n)), utána a végére – O(1)
- **Törlés:** megkeressük (O(n)), és az **utolsó elemet tesszük a helyére** – nem kell tolni, hiszen a sorrend nem számít!

<div class="doboz">

A tárigény az elemek számával arányos – nincs szükség alaphalmazra, akármilyen elemet tárolhatunk.

</div>

---

<!-- _class: kicsi -->

## Rendezetlen tömb – műveletek

<div class="ket-hasab">
<div>

<span class="cimke pszeudo">Részhalmaz: A ⊆ B</span>

```text
Függvény Része(A, n, B, m)
  i ← 1
  Ciklus amíg i ≤ n és Eleme(B, m, A[i])
    i ← i + 1
  Ciklus vége
  Vissza: i > n
Függvény vége
```

<span class="cimke pszeudo">Metszet: A ∩ B</span>

```text
Eljárás Metszet(A, n, B, m, C, k)
  k ← 0
  Ciklus i ← 1-től n-ig
    Ha Eleme(B, m, A[i]) akkor
      k ← k + 1 ; C[k] ← A[i]
    Elágazás vége
  Ciklus vége
Eljárás vége
```

</div>
<div>

**Unió:** A minden eleme + B azon elemei, amelyek nincsenek A-ban
**Különbség:** A azon elemei, amelyek nincsenek B-ben

| Művelet | Lépésszám |
|---|---|
| eleme-e | O(n) |
| bővítés | O(n) |
| törlés | O(n) |
| részhalmaz | **O(n · m)** |
| unió, metszet, különbség | **O(n · m)** |

<div class="doboz figyelem">

Minden elemre lineáris keresés a másik halmazban → négyzetes!

</div>

</div>
</div>

---

<!-- _class: fejezet -->

# Ábrázolás rendezett tömbbel

---

## Rendezett tömb

Az elemeket **növekvő sorrendben** tároljuk, ismétlődés nélkül.

A = `[2, 5, 8, 11]` · B = `[3, 5, 9, 11, 14]`

- **Eleme-e?** **bináris keresés** – O(log n)
- **Bővítés / törlés:** a helyét bináris kereséssel megtaláljuk, de **tolni** kell – O(n)
- **Halmazműveletek:** a két rendezett tömb **összefésülése** – egyetlen közös bejárás

---

## Összefésülés: a halmazműveletek alapja

![w:1000](kepek/h06_osszefesules.svg)

---

<!-- _class: kicsi tomor -->

## Unió összefésüléssel

<div class="ket-hasab">
<div>

<span class="cimke pszeudo">Pszeudokód</span>

```text
Eljárás Unió(A, n, B, m, C, k)
  i ← 1 ; j ← 1 ; k ← 0
  Ciklus amíg i ≤ n és j ≤ m
    k ← k + 1
    Ha A[i] < B[j] akkor
      C[k] ← A[i] ; i ← i + 1
    különben ha A[i] > B[j] akkor
      C[k] ← B[j] ; j ← j + 1
    különben                 // egyenlők
      C[k] ← A[i] ; i ← i + 1 ; j ← j + 1
    Elágazás vége
  Ciklus vége
  Ciklus amíg i ≤ n            // A maradéka
    k ← k + 1 ; C[k] ← A[i] ; i ← i + 1
  Ciklus vége
  Ciklus amíg j ≤ m            // B maradéka
    k ← k + 1 ; C[k] ← B[j] ; j ← j + 1
  Ciklus vége
Eljárás vége
```

</div>
<div>

<span class="cimke java">Java</span>

```java
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length) {
    if (a[i] < b[j])      c[k++] = a[i++];
    else if (a[i] > b[j]) c[k++] = b[j++];
    else { c[k++] = a[i++]; j++; }
}
while (i < a.length) c[k++] = a[i++];
while (j < b.length) c[k++] = b[j++];
```

**Metszet:** csak az egyenlő ágban írunk C-be, a maradékot nem másoljuk.
**Különbség:** csak az `A[i] < B[j]` ágban írunk, és A maradékát másoljuk.

</div>
</div>

---

## Részhalmaz összefésüléssel

```text
Függvény Része(A, n, B, m)            // A ⊆ B ?
  i ← 1 ; j ← 1
  Ciklus amíg i ≤ n és j ≤ m és A[i] ≥ B[j]
    Ha A[i] = B[j] akkor i ← i + 1
    j ← j + 1
  Ciklus vége
  Vissza: i > n
Függvény vége
```

- Ha `A[i] < B[j]`, akkor A[i] **biztosan nincs** B-ben (B további elemei még nagyobbak) → nem részhalmaz
- Lépésszám: **O(n + m)**

---

## Az ábrázolások összehasonlítása

| Művelet | Logikai vektor | Rendezetlen tömb | Rendezett tömb |
|---|---|---|---|
| eleme-e | **O(1)** | O(n) | O(log n) |
| bővítés, törlés | **O(1)** | O(n) | O(n) |
| részhalmaz | O(\|U\|) | O(n · m) | **O(n + m)** |
| unió, metszet, különbség | O(\|U\|) | O(n · m) | **O(n + m)** |
| tárigény | \|U\| bit | n elem | n elem |
| feltétel | kicsi, ismert U | – | rendezhető elemek |

<div class="doboz">

Nincs „legjobb” ábrázolás: a választás az **alaphalmaz méretétől** és a **leggyakoribb műveletektől** függ.

</div>

---

<!-- _class: kicsi -->

## Beépített halmazok

<div class="ket-hasab">
<div>

<span class="cimke java">Java</span>

```java
Set<String> a = new HashSet<>();  // O(1) átl.
a.add("Wuhan");
a.contains("Wuhan");    // true
a.remove("Wuhan");

Set<String> u = new HashSet<>(a);
u.addAll(b);            // unió
u.retainAll(b);         // metszet
u.removeAll(b);         // különbség

TreeSet<Integer> t = new TreeSet<>(); // O(log n)
t.first(); t.last();    // rendezett!
```

</div>
<div>

<span class="cimke go">Go – nincs set típus, map-pel</span>

```go
type Set map[string]struct{}

s := Set{}
s["Wuhan"] = struct{}{}      // bővítés
_, ok := s["Wuhan"]          // eleme-e
delete(s, "Wuhan")           // törlés

// gyakori rövidítés:
seen := map[int]bool{}
if !seen[x] {
    seen[x] = true
}
```

</div>
</div>

`HashSet` és Go `map`: **hash tábla** (11. hét) · `TreeSet`: **kiegyensúlyozott keresőfa** (15. hét)

---

## Összefoglalás

- **Halmaz:** különböző elemek rendezetlen gyűjteménye; műveletek: ∈, ⊆, ∪, ∩, \
- **Logikai vektor / bitmaszk:** kicsi, ismert alaphalmaz esetén a leggyorsabb – O(1), O(|U|)
- **Rendezetlen tömb:** egyszerű, de a halmazműveletek O(n · m)
- **Rendezett tömb:** bináris keresés O(log n), **összefésüléssel** a halmazműveletek O(n + m)
- Beépített: Java `HashSet` / `TreeSet`, Go `map[T]struct{}`

**Következő hét:** a verem (stack) – LIFO elv, tömbös megvalósítás, postfix kifejezések kiértékelése.

---

## Ellenőrző kérdések

1. Az univerzum U = {1, 2, …, 8}. Írd fel logikai vektorként: A = {2, 3, 5, 7}, B = {1, 2, 3, 4}! Számold ki: A ∪ B, A ∩ B, A \ B!
2. Igaz vagy hamis: rendezetlen tömbös ábrázolásnál a metszet lépésszáma O(n + m).
3. Végezd el papíron az összefésülést: A = [1, 4, 6, 9], B = [2, 4, 9, 10]! Add meg A ∪ B, A ∩ B és A \ B értékét!
4. Miért nem célszerű logikai vektorral ábrázolni a hallgatói azonosítók (8 jegyű számok) halmazát?
5. Bitmaszkokkal: `a = 0b1010`, `b = 0b0110`. Mennyi `a & b`, `a | b`, `a & ~b`?

<!--
Megoldás:
1. A = 01101010, B = 11110000 (1..8 sorrendben) → A∪B = 11111010 = {1,2,3,4,5,7}, A∩B = 01100000 = {2,3}, A\B = 00001010 = {5,7}
2. H – O(n·m) (minden elemre lineáris keresés)
3. A∪B = [1,2,4,6,9,10], A∩B = [4,9], A\B = [1,6]
4. Az univerzum 10^8 elemű → 10^8 bit ≈ 12,5 MB minden halmazhoz, miközben csak néhány tucat elem van benne.
5. a&b = 0010, a|b = 1110, a&~b = 1000
-->

---

<!-- _class: fejezet -->
<!-- _footer: "" -->

# Gyakorlat

---

<!-- _class: gyak -->

## Bemutató programok

| Program | Java | Go | Mit mutat? |
|---|---|---|---|
| Logikai vektor | `BitVectorSet.java` | `h06/bitvectorset` | napok halmaza, bitmaszk-műveletek |
| Rendezetlen | `UnorderedSet.java` | `h06/unorderedset` | O(n · m) műveletek, törlés az utolsóval |
| Rendezett | `SortedSet.java` | `h06/sortedset` | bináris keresés, összefésülés |
| Beépített | `BuiltinSets.java` | `h06/builtin` | `HashSet`, `TreeSet`, Go `map` |

---

<!-- _class: gyak -->

## Feladatok

1. **Ismétlődések törlése:** készíts egy tömbből halmazt rendezéssel! (`[4,1,4,2,1] → [1,2,4]`)
2. **Szimmetrikus differencia:** A △ B = (A \ B) ∪ (B \ A) – rendezett tömbökön, egyetlen összefésüléssel!
3. **Diszjunktak-e?** Döntsd el O(n + m) lépésben, hogy két rendezett halmaznak nincs közös eleme!
4. **Hatványhalmaz:** írd ki egy *n* elemű halmaz összes részhalmazát bitmaszkokkal! Hány van?
5. **Különböző betűk:** hány különböző angol betű szerepel egy szövegben? (logikai vektor)
6. **Pangramma:** szerepel-e egy mondatban az angol ábécé összes betűje?
7. **Közös barátok:** két barátlista metszete beépített halmaz (map) segítségével.

Megoldások: `Exercises06.java`, `h06/exercises`

---

<!-- _class: gyak -->

## Házi feladat

1. Valósíts meg egy `SortedSet` osztályt `add(x)` és `remove(x)` műveletekkel, amely mindig rendezett marad! (Tipp: bináris kereséssel keresd a helyet.)
2. **Multihalmaz** (zsák): egy elem többször is szerepelhet. Hogyan ábrázolnád logikai vektor helyett? Valósítsd meg az uniót és a metszetet (a darabszámok maximuma, illetve minimuma)!
3. Három rendezett halmaz metszetét számold ki **egyetlen** közös bejárással!
4. Egy 1 és 100 000 közötti számokból álló, 1 000 000 elemű tömbben hány **különböző** szám van? Oldd meg logikai vektorral, és hasonlítsd össze a rendezéses megoldással!

<!--
Megoldás-vázlat:
1. add: lowerBound (2. hét F4) + eltolás jobbra, ha még nincs benne; remove: bináris keresés + eltolás balra.
2. Számlálóvektor: C[i] = az i-edik elem darabszáma; unió: max(A[i], B[i]); metszet: min(A[i], B[i]).
3. Három index; ha mind egyenlő → eredmény, mindhárom lép; különben a legkisebbhez tartozó index lép.
4. boolean[100001]; egy bejárás O(n + |U|); rendezéssel O(n log n).
-->