Summary of Bináris keresőfa

## Bevezetés a Bináris Keresőfákba A bináris keresőfa (Binary Search Tree, BST) a számítástechnika egyik alapvető adatszerkezete, amely hatékony módot biztosít rendezett adatok tárolására és kezelésére. Nevét onnan kapta, hogy minden csomópontnak legfeljebb két gyermeke lehet (**bináris**), és az adatok elrendezése lehetővé teszi a gyors keresést (**keresőfa**). A BST-k széles körben alkalmazhatók adatbázis-indexekben, szótárakban és más olyan rendszerekben, ahol az adatok gyors visszakeresése, beszúrása és törlése kulcsfontosságú. > **Gyökér (Root):** A fa legfelső csomópontja, ahonnan minden művelet indul. > **Levél (Leaf Node):** Azok a csomópontok, amelyeknek nincs gyermekük. ### A Bináris Keresőfa Tulajdonságai Egy bináris fa akkor minősül bináris keresőfának, ha minden csomópontjára igaz a következő tulajdonság: 1. A csomópont bal oldali részfájában található összes érték kisebb, mint a csomópont saját értéke. 2. A csomópont jobb oldali részfájában található összes érték nagyobb, mint a csomópont saját értéke. 3. Mind a bal, mind a jobb oldali részfa maga is bináris keresőfa. Ez a rendezési elv biztosítja, hogy az adatok mindig rendezett sorrendben legyenek tárolva, ami jelentősen felgyorsítja a keresési műveleteket. Did you know that a perfectly balanced binary search tree, where each node has approximately the same number of nodes in its left and right subtrees, offers the most efficient performance for search, insertion, and deletion operations? ### Műveletek Bináris Keresőfán A bináris keresőfák alapvető műveletei a keresés, a beszúrás és a törlés. Ezeknek a műveleteknek az időkomplexitása szorosan összefügg a fa magasságával, amit $h$-val jelölünk. A legtöbb művelet időkomplexitása $O(h)$, ami azt jelenti, hogy a művelet végrehajtásához szükséges lépések száma arányos a fa magasságával. > **Időkomplexitás:** Egy algoritmus futásidejének mértéke a bemenet méretének függvényében. Az $O(h)$ jelölés azt mutatja, hogy a művelet végrehajtásához szükséges idő arányos a fa magasságával. #### Keresés (Search) Egy adott érték keresése a bináris keresőfában egy egyszerű, rekurzív vagy iteratív eljárással történik: 1. Kezdjük a gyökérnél. 2. Ha a keresett érték megegyezik az aktuális csomópont értékével, akkor az értéket megtaláltuk. 3. Ha a keresett érték kisebb, mint az aktuális csomópont értéke, akkor folytassuk a keresést a bal oldali részfában. 4. Ha a keresett érték nagyobb, mint az aktuális csomópont értéke, akkor folytassuk a keresést a jobb oldali részfában. 5. Ha elérünk egy üres részfát (null mutatót), és az értéket még nem találtuk meg, akkor az érték nincs a fában. Ez az eljárás minden lépésben kizárja a fa egyik felét, hasonlóan a bináris kereséshez egy rendezett tömbben. A legrosszabb esetben a keresés a fa magasságával arányos számú lépést igényel, azaz időkomplexitása $O(h)$. **Példa keresésre:** Keresés a $7$ értékre egy adott fában. ```text 8 / \ 3 10 / \ \ 1 6 14 / \ 4 7 ``` * Kezdjük a $8$-nál. $7 < 8$, menjünk balra (a $3$-hoz). * A $3$-nál vagyunk. $7 > 3$, menjünk jobbra (a $6$-hoz). * A $6$-nál vagyunk. $7 > 6$, menjünk jobbra (a $7$-hez). * A $7$-nél vagyunk. Az érték megegyezik. Megtaláltuk! #### Beszúrás (Insertion) Új érték beszúrása a bináris keresőfába a kereséshez hasonló logikát követ, de a keresés addig folytatódik, amíg el nem érünk egy üres helyet, ahová az új csomópontot beilleszthetjük: 1. Kezdjük a gyökérnél. 2. Ha a fa üres, az új érték lesz a gyökér. 3. Ha az új érték kisebb, mint az aktuális csomópont értéke, akkor lépjünk a bal oldali gyermekhez. Ha a bal oldali gyermek üres, szúrjuk be ide az új csomópontot. Ellenkező esetben folytassuk a bal oldali gyermeknél. 4. Ha az új érték nagyobb, mint az aktuális csomópont értéke, akkor lépjünk a jobb oldali gyermekhez. Ha a jobb oldali gyermek üres, szúrjuk be ide az új csomópontot. Ellenkező esetben folytassuk a jobb oldali gyermeknél. 5. Ha az új érték megegyezik egy m