binary tree

Angol

Főnév

binary tree (tsz. binary trees)

1. (informatika, mesterséges intelligencia) bináris fa

---

Egy bináris fa (binary tree) olyan adat­szerkezet, melyben minden csomópontnak legfeljebb két gyermeke lehet – ezek általában bal és jobb gyermekként értelmezettek. A bináris fák rendkívül sokoldalúan alkalmazhatók rendezett adattárolásra, gyors keresésre, kifejezések reprezentálására, útvonal­keresésre, és még számtalan algoritmus alapelemeként szolgálnak.

---

1. Alapfogalmak és szerkezet

• Csomópont (node): az adatot (kulcsot) és két mutatót (bal/jobb gyermekre).
• Gyökér (root): a fa legfelső csomópontja, szüle nincs.
• Levél (leaf): olyan csomópont, amelynek nincs gyermeke.
• Belső csomópont: legalább egy gyermeke van.
• Szülő–gyermek kapcsolat: ha A bal vagy jobb mutatója B-re mutat, akkor A a szülő, B a gyerek.

---

2. Bináris fa típusai

1. Általános bináris fa – Nincs megszorítás a csomópontok elhelyezkedésére.
2. Teljes bináris fa (complete) – Minden szinten (kivéve talán az utolsó) maximális számú csomópont van, és az utolsó szinten balról jobbra töltött.
3. Tömör bináris fa (full, proper) – Minden csomópontnak vagy pontosan két gyermeke van, vagy egyáltalán nincs.
4. Telített bináris fa (perfect) – Minden belső csomópontnak két gyermeke van, és az összes levél ugyanazon a mélységen van.
5. Magasan kiegyensúlyozott fa (balanced) – A bal és jobb részfa magasságának különbsége minden csomópontnál legfeljebb 1 (AVL fa) vagy logaritmikus korlátok (Red–Black fa).
6. Keresőfa (Binary Search Tree, BST) – Minden csomópont kulcsa nagyobb, mint a bal részfa minden kulcsa, és kisebb, mint a jobb részfa minden kulcsa. Gyors keresést, beszúrást, törlést tesz lehetővé.

---

3. Műveletek és komplexitások

Művelet	Általános fa	Kiegyensúlyozott BST
Keresés	${\textstyle O(n)}$	${\textstyle O(\log n)}$
Beszúrás	${\textstyle O(1)}$ ha ismerjük a helyet; ${\textstyle O(n)}$ ha keresni kell	${\textstyle O(\log n)}$
Törlés	${\textstyle O(1)}$ helyi módosítások; ${\textstyle O(n)}$ kereséssel	${\textstyle O(\log n)}$
Bejárás (traversal)	${\textstyle O(n)}$	${\textstyle O(n)}$

3.1 Bejárások (Traversal)

• Preorder (gyökér–bal–jobb)
• Inorder (bal–gyökér–jobb) → BST-ben növekvő kulcs­sorrend
• Postorder (bal–jobb–gyökér)
• Szint szerinti (level-order) → sorban BFS

---

4. Implementáció

Általános csomópont szerkezet C-szerűen:

typedef struct Node {
    int key;
    struct Node *left;
    struct Node *right;
} Node;

4.1 Beszúrás BST-be (rekurzív)

Node* insert(Node* root, int key) {
    if (root == NULL) {
        Node* node = malloc(sizeof(Node));
        node->key = key;
        node->left = node->right = NULL;
        return node;
    }
    if (key < root->key)
        root->left  = insert(root->left, key);
    else if (key > root->key)
        root->right = insert(root->right, key);
    // duplikált kulcsokat elvetjük vagy számláljuk
    return root;
}

---

5. Alkalmazások

1. Rendezés: BST-be építés + inorder bejárás → ${\textstyle O(n\log n)}$ átlagosan.
2. Szótárak, asszociatív tömbök (map): kulcs–érték párok logaritmikus keresése.
3. Prioritásos kódolás (Huffman-fa) – súlyozott bináris fa.
4. Kifejezés-fák: aritmetikai kifejezések parse-fája, fordítókban AST.
5. Számítógépes grafika: BSP-fák (Binary Space Partition) 3D rendereléshez.

---

6. Egyensúlyozás

• AVL-fa: a magasságkülönbség minden csomópontnál ${\textstyle \leq 1}$, rotációkkal tartjuk.
• Red–Black fa: minden él színes (fekete vagy vörös), színezési szabályokkal biztosítja, hogy a fa hossza ${\textstyle O(\log n)}$.
• Treap: véletlen priorítás a kiegyensúlyozáshoz.

---

7. Összefoglalás

A bináris fa az algoritmusok és adatszerkezetek egyik legfontosabb építőköve. Megtámogatja a gyors keresést, dinamikus beszúrást és törlést, változatos kiegyensúlyozó technikákkal pedig garantáltan logaritmikus magasságot ér el. Alkalmazása több ezer célszoftverben, algoritmusban és rendszerben megtalálható.

További információk

• binary tree - Szótár.net (en-hu)
• binary tree - Sztaki (en-hu)
• binary tree - Merriam–Webster
• binary tree - Cambridge
• binary tree - WordNet
• binary tree - Яндекс (en-ru)
• binary tree - Google (en-hu)
• binary tree - Wikidata
• binary tree - Wikipédia (angol)