Ugrás a tartalomhoz

tree data structure

A Wikiszótárból, a nyitott szótárból

Angol


Főnév

tree data structure (tsz. tree data structures)

  1. (informatika) A fa (tree) adatszerkezet egy olyan hierarchikus ADT, amely csúcsokból („node”) és ezek között húzódó élekből („edge”) áll, ahol:
  • Egy egyedülálló gyökér („root”) csúcs van,
  • Minden más csúcsnak pontosan egy szülője („parent”) van,
  • Egy csúcsnak tetszőleges számú gyereke („child”) lehet,
  • Nincsenek körök (azaz visszavezető élek): bármely csúcsból visszafelé követve a szülőket, előbb-utóbb a gyökérhez jutunk.


1. Fogalmak és terminológia

  1. Gyökér (root) A fa tetején álló csúcs, amit nem szülőként kötünk össze mással.
  2. Szülő, gyermek, testvér Ha van él u→v, akkor u a szülője, v a gyermeke; két azonos szülőjű csúcs testvér.
  3. Levél (leaf) Olyan csúcs, melynek nincs gyereke.
  4. Belső csúcs (internal node) Olyan csúcs, amelynek legalább egy gyereke van.
  5. Mélység (depth) Egy v csúcs mélysége a gyökerétől mért élek száma.
  6. Magasság (height) A fa magassága a gyökértől a legtávolabbi levélig tartó leghosszabb út hossza.
  7. Részfa (subtree) Egy v csúcsot és minden leszakadó utódját tartalmazó részgráf.
  8. Sorszám (degree) Egy csúcs gyermekszáma.


2. Alapvető műveletek (Tree ADT API)

Művelet Leírás
createRoot(v) Új, egyetlen v értékű csúccsal gyökér létrehozása.
addChild(u, v) Új v csúcs beszúrása u gyermekeként.
removeSubtree(v) Az v csúcs és az összes leszármazott törlése.
parent(v) → node* Visszaadja v szülőjét (null ha v a gyökér).
children(v) → List<node*> v közvetlen gyerekei.
isLeaf(v) → bool Igaz, ha v-nek nincs gyermeke.
depth(v) → int v mélysége.
height() → int A fa magassága.
size() → int Összes csúcs száma.
traverse(order, visit) Fa bejárása adott sorrendben, minden csúcson visit(v).


3. Fa típusok

  1. Általános (n-áris) fa Minden csúcsnak tetszőleges számú gyereke lehet.
  2. Bináris fa Minden csúcs legfeljebb két gyermeke van: egy bal és egy jobb.
    • Teljes bináris fa: minden szinten kivéve talán az utolsót, minden csúcsnak két gyereke van, az alsó szint balra feltöltött.
    • Pontosan kitöltött: mindegyik belső csúcsnak pontosan két gyereke van, és minden levél azonos mélységű.
  3. Bináris keresőfa (BST) Minden csúcs v-nél a bal al­fa értékei < v.key, a jobb al­fa értékei > v.key. Műveletek: search, insert, delete mind átlagosan O(h), ahol h a fa magassága.
  4. Kiegyensúlyozott fák Garantált h = O(log n), pl. AVL-fa, Red-Black fa, B-fa (külső memóriás, többágú fa adatbázisokhoz).
  5. Heap (kupac) Teljes bináris fa, ahol minden csúcs kulcsa ≥ (max-heap) vagy ≤ (min-heap) gyermeke(i) kulcsánál. → Prioritási sor implementációja.
  6. Trie (prefix‐fa) Karakterek (sztring-prefixek) eltárolására, minden él egy karaktert tárol, a gyökértől való út egy sztring.
  7. Segment fa, Fenwick (BIT) Intervallumokra, prefix‐összegekre optimalizált dinamikus fákat valósítanak meg, O(log n) frissítés és lekérdezés.


4. Belső reprezentációk

4.1. Csomópont‐pointeres (node‐pointer) megoldás

struct Node {
    T key;
    vector<Node*> children;   // általános fa
    Node *left, *right;       // bináris fa
    Node(T k): key(k), left(nullptr), right(nullptr){}
};
  • Dinamikus, könnyen bővíthető, de több memória overhead (pointerek).

4.2. Tömb alapú (array) reprezentáció

  • Teljes bináris fa: 1-től indexelt tömb, ha i a csúcs, akkor left = 2*i, right = 2*i+1.
  • Hatékony, de csak teljes vagy közel teljes fákhoz.

4.3. Parent‐pointer + children‐index

  • Egy tömb rekordjai tartalmazzák a szülő indexét és a gyermek listája (vagy első gyerek + testvér pointerek) indexeit — statikus univerzum-meg­közelítés.


5. Bejárási (Traversal) algoritmusok

  1. Előrend (Pre-order):

    visit(v)
for each child c of v: preorder(c)

  2. Középrend (In-order) (csak bináris fán értelmes):

    inorder(v.left)
visit(v)
inorder(v.right)

  3. Utórend (Post-order):

    for each child c: postorder(c)
visit(v)

  4. Szélességi bejárás (BFS): → Queue segítségével sorban szintenként.

Minden bejárás O(n + m) — m az élek száma, n a csúcsoké; egy fában m = n−1, így O(n).


6. Műveletek és komplexitások

Fa típus Insert Search Delete Memory
Bináris fa (avg) O(h) O(h) O(h) O(n)
BST (worst) O(n) O(n) O(n) O(n)
AVL / RB-fa O(log n) O(log n) O(log n) O(n) + bal.sz.
Heap O(log n) O(n) (search) O(log n) O(n)
Trie O(L) (L = key length) O(L) O(L) + cleanup O(Σ·L)
Segment fa O(log n) O(log n) — O(n)


7. Tipikus felhasználási minták

  • Hierarchiák: fájlrendszerek, szervezeti felépítés, DOM fa.
  • Keresés és rendezés: BST, B-fa adatbázis‐indexelés.
  • Prioritási sor: heap.
  • Sztringfeldolgozás: trie, suffix fa.
  • Intervallum‐lekérdezések: segment fa, Fenwick‐fa.
  • Gépi tanulás: döntési fák (decision trees).


8. Standard könyvtári támogatás

  • C++ STL
    • nincs beépített általános fa, de:
      • std::set / map (RB-fa)
      • std::priority_queue (heap)
      • std::tr1::unordered_map (hash)
  • Boost.Graph: általános gráf és fa implementációk, bejárások.
  • Java
    • TreeMap / TreeSet (fa‐alapú asszociatív konténer)
    • nincs általános fa, de PriorityQueue (heap), LinkedList (szekvencia)
  • Python
    • heapq modul (heap)
    • nincsenek beépített fa ADT‐k, de könyvtárak (anytree, treelib).


Összefoglalás

A tree ADT rugalmasságot és hierarchikus modellt kínál, számos speciális fa‐típus (bináris keresőfa, kiegyensúlyozott fa, kupac, trie, segment fa) pedig az adott feladatprofil — keresés, prioritás, intervallum‐lekérdezés, sztring‐prefixek — optimális megoldását teszi lehetővé. A belső reprezentáció (pointeres vs. tömb‐alapú) és az algoritmikus kiegyensúlyozás (AVL, Red-Black, B-fa) a teljesítmény kulcsa: mindig a feladatigényekhez érdemes igazítani a fa implementációját.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=tree_data_structure&oldid=3500287”