Mi az a bináris keresőfa?

A bináris keresőfa egyike azon különféle adatstruktúráknak, amelyek segítenek az adatok rendszerezésében és rendezésében. Ez egy hatékony módja az adatok hierarchiában történő tárolásának, és nagyon rugalmas.

Ebben a cikkben közelebbről megvizsgáljuk, hogyan működik – a tulajdonságaival és alkalmazásaival együtt.

Mi az a bináris keresőfa?

A bináris keresőfa egy csomópontokból álló adatstruktúra – hasonlóan a csatolt listákhoz. Kétféle csomópont lehet: szülő és gyermek. A gyökércsomópont a struktúra kezdőpontja, amely két gyermekcsomópontra ágazik, amelyeket bal és jobb csomópontnak neveznek.

Minden csomópontra csak a szülője hivatkozhat, és a fa csomópontjain az iránytól függően tudunk bejárni. A bináris keresőfának három fő tulajdonsága van:

1. A bal oldali csomópont kisebb, mint a szülője.
2. A jobb oldali csomópont nagyobb, mint a szülője.
3. A bal és jobb oldali részfának bináris keresőfának kell lennie.

A tökéletes bináris keresési fa akkor érhető el, ha minden szint ki van töltve, és minden csomópontnak van egy bal és jobb oldali gyermekcsomópontja.

Összefüggő: Adattudományi könyvtárak Pythonhoz, amelyet minden adatkutatónak használnia kell

A bináris keresőfa alapvető műveletei

Most, hogy jobban megértette, mi az a bináris keresőfa, az alábbiakban megtekinthetjük alapvető műveleteit.

1. Keresési művelet

A keresés lehetővé teszi, hogy megkeressünk egy adott értéket a fában. Kétféle keresést használhatunk: szélesség-első keresés (BFS) és mélység-első keresés (DFS). A szélesség-első keresés egy keresési algoritmus, amely a gyökércsomópontnál kezdődik, és vízszintesen halad, oldalról a másikra, amíg meg nem találják a célt. A keresés során minden csomópontot egyszer felkeresnek.

A mélységben végzett keresés ezzel szemben függőlegesen halad át a fán – a gyökércsomóponttól kezdve, és egy ágon lefelé halad. Ha a cél megtalálható, a művelet véget ér. De ha nem, akkor megkeresi a többi csomópontot.

2. Beszúrás művelet

A beszúrási művelet a keresési műveletet használja annak meghatározására, hogy az új csomópontot hol kell beszúrni. A folyamat a gyökércsomóponttól indul, és a keresés a cél eléréséig kezdődik. A beillesztésnél három esetet kell figyelembe venni.

• 1. eset: Ha nem létezik csomópont. A beillesztendő csomópont lesz a gyökércsomópont.

• 2. eset: Nincsenek gyerekek. Ebben az esetben a csomópont összehasonlításra kerül a gyökércsomóponttal. Ha nagyobb, megfelelő gyermek lesz belőle; különben a bal gyerek lesz belőle.

• 3. eset: Amikor a gyökér és gyermekei jelen vannak. Az új csomópontot a rendszer összehasonlítja az útvonalon lévő összes csomóponttal, hogy meghatározza, melyik csomópontot keresi fel legközelebb. Ha a csomópont nagyobb, mint a gyökércsomópont, akkor lefelé halad a jobb oldali alfán, vagy a bal oldalon. Hasonlóképpen, minden szinten összehasonlítást végeznek annak meghatározására, hogy jobbra vagy balra fog-e menni, amíg meg nem érkezik a rendeltetési helyére.

3. Művelet törlése

A törlési művelet egy adott csomópont eltávolítására szolgál a fán belül. A törlés trükkösnek számít, mivel egy csomópont eltávolítása után a fát ennek megfelelően újra kell rendezni. Három fő esetet kell figyelembe venni:

• 1. eset: Levélcsomópont törlése. A levél csomópont olyan csomópont, ahol nincsenek gyermekek. Ezt a legkönnyebb eltávolítani, mivel nincs hatással egyetlen másik csomópontra sem; egyszerűen áthaladunk a fán, amíg el nem érjük, és töröljük.

• 2. eset: Csomópont törlése egy gyermekkel. Az egy csomóponttal rendelkező szülő törlése azt eredményezi, hogy a gyermek elfoglalja a pozícióját, és az összes következő csomópont egy szinttel feljebb kerül. Az alfák szerkezetében nem lesz változás.

• 3. eset: Két gyermekes csomópont törlése. Amikor el kell távolítanunk egy csomópontot két gyermekkel, először meg kell találnunk egy következő csomópontot, amely el tudja foglalni a helyét. Két csomópont helyettesítheti az eltávolított csomópontot, a sorrendi utódját vagy elődjét. A sorrendi utód a jobb oldali részfa bal szélső gyermeke, a sorrend elődje pedig a bal oldali részfa jobb szélső gyermeke. Az utód/előd tartalmát átmásoljuk a csomópontba, és töröljük a soron kívüli utód/előd tartalmát.

Összefüggő: Hogyan építsünk fel adatstruktúrákat JavaScript ES6 osztályokkal

Hogyan lehet bejárni a bináris keresőfát

A bejárás az a folyamat, amelyen keresztül a bináris keresőfában navigálunk. Ez egy adott elem megkeresésére vagy a fa körvonalának kinyomtatására szolgál. Mindig a gyökércsomópontból indulunk ki, és követnünk kell az éleket, hogy eljussunk a többi csomóponthoz. Minden csomópontot alfának kell tekinteni, és a folyamatot addig kell ismételni, amíg az összes csomópontot meg nem látogatják.

• Rendelésen belüli bejárás: A sorrendben történő bejárás a térképet növekvő sorrendben állítja elő. Ezzel a módszerrel a bal oldali részfától indulunk, és folytatjuk a gyökér és a jobb oldali részfát.

• Előrendelési bejárás: Ennél a módszernél először a gyökércsomópontot keresik fel, ezt követi a bal oldali részfa és a jobb oldali részfa.

• Rendelés utáni bejárás: Ez a bejárás magában foglalja a gyökércsomópont utolsó látogatását. A bal oldali részfából indulunk ki, majd a jobb oldali részfából, majd a gyökércsomópontból.

Valós alkalmazások

Tehát hogyan használjuk a bináris keresési fa algoritmusokat? Amint sejthető, rendkívül hatékonyak a keresésben és a válogatásban. A bináris fák legnagyobb erőssége a szervezett felépítésük. Lehetővé teszi a keresést figyelemre méltó sebességgel, azáltal, hogy menetenként felére csökkenti az elemezni kívánt adatmennyiséget.

A bináris keresőfák lehetővé teszik számunkra, hogy hatékonyan karbantartsunk egy dinamikusan változó adatkészletet szervezett formában. Azoknál az alkalmazásoknál, amelyekhez gyakran vannak beillesztve és eltávolítva adatok, nagyon hasznosak. A videojáték-motorok bináris térpartícióként ismert fákon alapuló algoritmust használnak az objektumok rendezett megjelenítéséhez. A Microsoft Excel és a legtöbb táblázatkezelő szoftver bináris fákat használ alapvető adatszerkezetként.

Meglepődhet, ha megtudja, hogy a Morse-kód bináris keresőfát használ az adatok kódolására. Egy másik kiemelkedő ok, amiért a bináris keresőfák olyan hasznosak, a többféle változatuk. Rugalmasságuk számos változat létrehozásához vezetett mindenféle probléma megoldására. Megfelelő használat esetén a bináris keresőfák nagy előnyt jelentenek.

Bináris keresőfák: A tökéletes kiindulópont

A mérnök szakértelmének felmérésének egyik fő módja az adatszerkezetek ismerete és alkalmazása. Az adatstruktúrák hasznosak, és segíthetnek egy hatékonyabb rendszer létrehozásában. A bináris keresőfák nagyszerű bevezetést nyújtanak az adatstruktúrákba minden kezdő fejlesztő számára.

15 JavaScript-tömb módszer, amelyet ma el kell sajátítania

Meg akarja érteni a JavaScript tömböket, de nem tud megbirkózni velük? Útmutatásért tekintse meg JavaScript-tömb példáinkat.

Olvassa el a következőt

A szerzőről