Próbáljon meg egy egyszerű magyarázatot találni a bináris keresőfa (BST) mibenlétére, és valószínűleg csalódni fog. Honnan tudjam? Mert megpróbáltam, de nem sikerült.
A legtöbb, amivel találkoztam, bonyolultabb volt, mint amit kerestem. Sok cikk még a beillesztések, leletek, faegyensúlyok stb. algoritmikus bonyolultságáról is részletesen foglalkozik. Ez a cikk nem az. A nulláról kezdem, és elhagyom a nyelveket és az algoritmusokat.
Ehelyett a következőkre összpontosítunk:
- Micsoda fa
- Mitől lesz egy fa bináris fa
- Hogyan tárolódnak az adatok egy fában
- Mitől lesz egy bináris fa BST?
- Hogyan lehet értékeket keresni és beilleszteni egy BST-be
- Miért hasznosak a BST-k?
Micsoda fa
Beszéljünk a természetről. A vadon élő fa csak egy nagy fadarab (egy ág, amelyet általában törzsnek neveznek). Azon a nagy fadarabon lehetnek kisebb fadarabok, amelyek leváltak róla (ágak). Azoknak az ágaknak lehetnek levelei.
Hasonlóképpen, az adatokban lévő fa csak egy törzs, amelyet gyökérnek nevezünk. Az ágait részfáknak (mivel ezeknek az ágaknak lehetnek következő ágai is) vagy csomópontoknak nevezzük.
Ha egy részfának nincsenek gyermekei (nem ágazik le magáról), akkor levélnek nevezzük.
Mitől lesz egy fa bináris fa
Ha egyszer a fák köré hajtja a fejét, a bináris fákat egy kicsit könnyebb megérteni. A bináris fa csak egy olyan fa, amelynek csomópontjaiban (a körökben) legfeljebb 2 részfa (vagy gyermek) található.
A fenti példa gyökércsomópontja 3 részfával rendelkezik (egy gyermekekkel és kettő anélkül), tehát ez a példa nem bináris fa.
Hogyan tárolódnak az adatok egy fában
A legfontosabb tudnivaló a fa adatstruktúrájáról, hogy a fa minden csomópontjához tartozik egy érték. Egyetlen csomópont sem lehet üres. Ha egy csomópontnak nincs értéke, akkor egyszerűen nem létezik.
Az alábbiakban egy példa arra, hogy mit értek ezen.
Mitől lesz egy bináris fa BST?
Talán észrevett valami különlegeset a fenti fán. Minden csomópontnak két gyermeke van. Bal és jobb. De minden csomópont bal gyermeke kisebb, mint a csomópont értéke, és minden jobb oldali gyermek nagyobb. Ez az, ami egy bináris fát bináris keresőfává tesz.
Hogyan keressünk értékeket a BST-ben
Ahogy a név is sugallja, a bináris keresési fa gyakori használata az érték keresése. Nézzünk egy példát:
Hogyan lehet értékeket beszúrni egy BST-be
Az is hasznos, ha dolgokat adhat hozzá egy fához. Ez valójában nagyon egyszerű, és nagyon hasonlít a kereséshez. A gyökérnél kezded. Ha a beszúrni kívánt érték kisebb, lépjen balra. Ha több, menjen jobbra.
Egy figyelmeztetés az, hogy soha ne írjon be olyan értéket, amely már létezik. A BTS-nek nem lehet duplikált értéke, mert egy érték nem nagyobb vagy kisebb önmagánál! Ennek elkerülése érdekében az út minden lépésében ellenőrizze, hogy a beszúrni kívánt érték nem egyezik-e meg az éppen megtekintett csomóponttal. Ha igen, csak dobjon egy hibát, vagy ne csináljon semmit. A te döntésed!
Miért hasznosak a BST-k?
Mindez a keresési és beszúrási műveletek sebességén múlik. Anélkül, hogy belemenne a matematikába, csak tudja, hogy a beszúrások és keresések sebessége átlagosannagyon gyors.
A keresések és a beillesztések csak a szerkezet elemeinek egy kis részét érintik (amit pirossal kiemeltem). Ez azt jelenti, hogy kevesebb az összehasonlítás, és kevesebb a munka.
Következtetés
A bináris keresési fák egy nagyon erős (de nem tökéletes) adatstruktúra, amelyet a programozói eszköz sávban tartalmazhat. Ha jól csinálja, a nagy mennyiségű rendezett adat kezelése könnyebbé és gyorsabbá válik.
Ha szeretne egy klassz animációt az itt említett műveletek működéséről, nézze meg "ezt". További és mélyebb olvasmányokért tekintse meg ezt a részt.
Remélem, hogy ez a cikk hasznos volt az Ön számára. Ha igen, tudasd velem néhány tapsolással, kommenteléssel vagy a Twitteren!
