Ü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. A
binary 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)
- (informatika, mesterséges intelligencia) bináris fa
Egy bináris fa (binary tree) olyan adatszerkezet, 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, útvonalkeresé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
- Általános bináris fa – Nincs megszorítás a csomópontok elhelyezkedésére.
- 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.
- Tömör bináris fa (full, proper) – Minden csomópontnak vagy pontosan két gyermeke van, vagy egyáltalán nincs.
- 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.
- 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).
- 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ő kulcssorrend
- 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
- Rendezés: BST-be építés + inorder bejárás →
átlagosan.
- Szótárak, asszociatív tömbök (map): kulcs–érték párok logaritmikus keresése.
- Prioritásos kódolás (Huffman-fa) – súlyozott bináris fa.
- Kifejezés-fák: aritmetikai kifejezések parse-fája, fordítókban AST.
- 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ó.