binary tree

Üdvözlöm, Ön a binary tree szó jelentését keresi. A DICTIOUS-ban nem csak a binary tree szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a binary tree szót egyes és többes számban mondani. Minden, amit a binary tree szóról tudni kell, itt található. A binary tree szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. Abinary tree és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.

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
Beszúrás ha ismerjük a helyet;
ha keresni kell
Törlés helyi módosítások;
kereséssel
Bejárás (traversal)

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 → á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 , 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 .
  • 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ó.