A bináris keresési fák három fő műveletet támogatnak: elemek beillesztése, elemek törlése, valamint a keresés (annak ellenőrzése, hogy van-e kulcs).

SearchingEdit

egy adott kulcs bináris keresési fában történő keresése rekurzív vagy iteratív módon programozható.

a gyökércsomópont vizsgálatával kezdjük. Ha a fa null, akkor a keresett kulcs nem létezik a fában. Ellenkező esetben, ha a kulcs megegyezik a gyökér kulcsával, a keresés sikeres, majd visszaadjuk a csomópontot. Ha a kulcs kisebb, mint a gyökéré, akkor a bal oldali részfajtát keressük., Hasonlóképpen, ha a kulcs nagyobb, mint a gyökéré, akkor a megfelelő altípust keressük. Ezt a folyamatot addig ismételjük, amíg meg nem találjuk a kulcsot, vagy a fennmaradó részfa null. Ha a keresett kulcs nem található a null altípus elérése után, akkor a kulcs nincs jelen a fában. Ez egyszerűen kifejezve egy rekurzív algoritmus (végre Python):

ugyanaz Az algoritmus lehet végrehajtani iteratively:

ez a két példa nem támogatja ismétlődések, hogy számítanak a sorrendben kapcsolatban, hogy egy teljes megrendelést.

meg lehet jegyezni, hogy a rekurzív algoritmus a farok rekurzív., A tail call optimalizálást támogató nyelvben a rekurzív és iteratív példák egyenértékű programokhoz fognak össze.

mivel a legrosszabb esetben ennek az algoritmusnak a fa gyökerétől a gyökértől legtávolabbi levélig kell keresnie, a keresési művelet a fa magasságával arányos időt vesz igénybe (lásd a fa terminológiáját). Átlagosan bináris keresési fák csomópontok gombok O (log |csomópontok|) magasság. A legrosszabb esetben azonban a bináris keresőfák O (|csomópontok/) magassággal rendelkezhetnek, amikor a kiegyensúlyozatlan fa egy kapcsolt listához hasonlít (degenerált fa).,

keresés duplikátumokkal allowedEdit

Ha a rendelési kapcsolat csak egy teljes előrendelés, a funkcionalitás ésszerű kiterjesztése a következő: egyenlőség esetén is Keresés a levelekre. Ezáltal lehetővé teszi, hogy adja meg (vagy kemény-drót) egy irányba, ahol be egy másolatot, akár jobbra vagy balra az összes másolatok a fa eddig. Ha az irány vezetékes, mind a jobb, mind a bal választás támogatja a verem beillesztését duplikátum push műveletként, majd törölje pop műveletként.,: 155

egy ilyen keresési funkcióval ellátott bináris fafajta stabilvá válik.

InsertionEdit

a Beillesztés úgy kezdődik, ahogy a keresés megkezdődik; ha a kulcs nem egyenlő a gyökérével, akkor a bal vagy a jobb altípusokat keressük, mint korábban. Végül elérünk egy külső csomópontot, és az új kulcs-érték párt (itt “newNode” rekordként kódolva) jobb vagy bal gyermekként adjuk hozzá, a csomópont kulcsától függően., Más szóval, megvizsgáljuk a gyökeret, és rekurzívan beillesztjük az új csomópontot a bal részfajtába, ha a kulcs kisebb, mint a gyökéré, vagy a jobb részfajtát, ha a kulcs nagyobb vagy egyenlő a gyökérrel.

itt van, hogy egy tipikus bináris keresési fa beillesztése lehet végrehajtani egy bináris fa c++:

Alternatívaként, egy nem rekurzív változat lehet végrehajtani, mint ez., A pointer-to-pointer használatával nyomon követhetjük, hogy honnan jöttünk, így a kód elkerülheti annak az esetnek a kifejezett ellenőrzését és kezelését, amikor be kell illesztenie egy csomópontot a fa gyökeréhez:

a fenti pusztító eljárási változat módosítja a fát a helyén. Csak állandó halom helyet használ (az iteratív változat pedig állandó veremterületet is használ), de a fa korábbi verziója elvész., Alternatív megoldásként, mint a következő Python például rekonstruálni tudjuk az összes ősei a egészül ki node; utalást, hogy az eredeti fa gyökere továbbra is érvényes, hogy a fa állandó adatok szerkezete:

az A része, amely újjá használ O(log n) tér átlagos esetben O(n) a legrosszabb esetben.

mindkét változatban ez a művelet a legrosszabb esetben a fa magasságával arányos időt igényel, ami az átlagos esetben O(log n) idő az összes fán, de o(n) idő a legrosszabb esetben.,

a beillesztés magyarázatának másik módja az, hogy egy új csomópont beillesztése a fába, annak kulcsát először összehasonlítják a gyökér kulcsával. Ha a kulcsa kisebb, mint a gyökéré, akkor összehasonlítják a gyökér bal gyermekének kulcsával. Ha a kulcsa nagyobb, akkor összehasonlítják a gyökér megfelelő gyermekével. Ez a folyamat folytatódik, amíg az új csomópontot össze nem hasonlítják egy levélcsomóponttal, majd ezt a csomópont jobb vagy bal gyermekeként adják hozzá, annak kulcsától függően: ha a kulcs kisebb, mint a levél kulcsa, akkor a levél bal gyermekeként kerül beillesztésre, különben a levél jobb gyermeke.,

a csomópontok bináris fába történő beillesztésének más módjai is vannak, de ez az egyetlen módja annak, hogy a csomópontokat a levelekre helyezzük, ugyanakkor megőrizzük a BST struktúrát.

DeletionEdit

Ha egy csomópontot eltávolít egy bináris keresési fáról, kötelező fenntartani a csomópontok sorrendjét. Sok lehetőség van erre. A T. Hibbard által 1962-ben javasolt következő módszer azonban garantálja, hogy a tárgy alfajainak magassága legfeljebb eggyel változik., Három lehetséges esetet kell figyelembe venni:

• gyermek nélküli csomópont törlése: egyszerűen távolítsa el a csomópontot a fáról.
• egy csomópont törlése egy gyermekkel: távolítsa el a csomópontot, majd cserélje ki a gyermekére.
• D csomópont törlése két gyermekkel: válassza ki a D sorrendben lévő elődjét vagy az e sorrendben lévő utódját (lásd az ábrát). Ha E-nek nincs gyermeke, távolítsa el az E-t az előző szülőjétől G. Ha E-nek gyermeke van F, akkor megfelelő gyermek, úgy, hogy az E-t az e szülőjénél cserélje ki.,

sorrendű elődjével minden esetben, amikor D a gyökér, tegye újra a csere csomópont gyökerét.

a két gyermekes csomópontokat nehezebb törölni., A csomópont rendbeli utódja a jobb oldali alfejezet bal-legtöbb gyermeke, a csomópont in-order elődje pedig a bal oldali alfejezet jobb-legtöbb gyermeke. Mindkét esetben ez a csomópont csak egy vagy egyáltalán nem lesz gyermek. Törölje azt a fenti két egyszerűbb eset egyikének megfelelően.

a kétgyermekes eset minden egyes esetére a sorrend szerinti utód vagy a sorrend szerinti Előd következetes használata kiegyensúlyozatlan fához vezethet, így egyes implementációk különböző időpontokban választják ki az egyiket vagy a másikat.,

futásidejű elemzés: bár ez a művelet nem mindig halad át a fán egy levélig, ez mindig lehetőség; így a legrosszabb esetben a fa magasságával arányos időt igényel. Nem igényel többet, még akkor sem, ha a csomópontnak két gyermeke van, mivel még mindig egyetlen utat követ, és nem látogat meg kétszer egyetlen csomópontot sem.,

TraversalEdit

Ha a bináris keresés fa jött létre, annak elemeit lehet letölteni a rendelés rekurzívan mozgás a bal részfa a gyökér csomópont, elérése a csomópont magát, akkor rekurzívan átkelés a jobb részfa a csomópont, továbbra is ez a minta minden egyes csomópont a fa, mint ez rekurzívan elérhető. Mint minden bináris fák, lehet, hogy végezzen egy előrendelés traversal vagy egy post-order traversal, de egyik sem valószínű, hogy hasznos bináris keresési fák., A bináris keresőfák sorrend szerinti keresztezése mindig a csomópontelemek (számok, karakterláncok vagy más hasonló elemek) rendezett listáját eredményezi.

a Python in-order traversal kódja az alábbiakban található. Visszahívást fog hívni (néhány funkció, amelyet a programozó fel kíván hívni a csomópont értékére, például a képernyőre történő nyomtatásra) a fa minden csomópontjára.

A Traversal o(n) időt igényel, mivel minden csomópontot meg kell látogatnia. Ez az algoritmus O(n) is, így aszimptotikusan optimális.

A Traversal iteratív módon is végrehajtható. Bizonyos alkalmazásokhoz, például, a nagyobb egyenlő keresés, a közelítő keresés, az egylépéses (iteratív) keresztirányú művelet nagyon hasznos lehet. Ezt természetesen a visszahívási konstrukció nélkül hajtják végre, és a legrosszabb esetben O(1) – T, O(log n) – t vesz igénybe.

VerificationEdit

néha már van egy bináris fánk, és meg kell határoznunk, hogy ez egy BST. Ez a probléma egy egyszerű rekurzív megoldás.,

a BST tulajdonságnak-a jobb oldali részfa minden csomópontjának nagyobbnak kell lennie, mint az aktuális csomópontnak, és a bal részfa minden csomópontjának kisebbnek kell lennie, mint az aktuális csomópontnak—a kulcsa annak megállapításához, hogy egy fa BST-e vagy sem. A mohó algoritmus—egyszerűen áthalad a fa, minden csomópont ellenőrizze, hogy a csomópontot tartalmaz egy érték nagyobb, mint az érték a bal gyermeke kisebb, mint az érték a jobb gyerek—nem működik minden esetben., Vegye figyelembe a következő fát:

 20 / \ 10 30 / \ 5 40

a fenti fán minden csomópont megfelel annak a feltételnek, hogy a csomópont nagyobb értéket tartalmaz, mint a bal gyermeke, és kisebb, mint a jobb gyermeke, és mégis nem BST: az 5 érték a 20-at tartalmazó csomópont jobb részfaja, amely a BST tulajdonság megsértése.

ahelyett, hogy kizárólag egy csomópont és gyermekei értékein alapuló döntést hoznánk, szükségünk van a szülőtől származó információkra is., A fenti fa esetében, ha emlékeznénk a 20 értéket tartalmazó csomópontra, azt látnánk, hogy az 5-ös értékű csomópont megsérti a BST ingatlanszerződést.,

Tehát a feltétellel, ellenőrizni kell, hogy minden csomópont:

• ha a csomópont a bal gyermek, a szülő, akkor kisebbnek kell lennie (vagy egyenlő), a szülő pedig add le az értéket a szülő, hogy a jobb részfa, hogy győződjön meg arról sem, hogy a csomópontok, hogy részfa nagyobb, mint a szülő
• ha a csomópont az a gyermek, a szülő, akkor kell, hogy legyen nagyobb, mint a szülő pedig add le az értéket a szülő, hogy a bal részfa, hogy győződjön meg arról sem, hogy a csomópontok, hogy részfa kisebb, mint a szülő.,

egy rekurzív megoldás a C++ – ban ezt tovább magyarázhatja:

node->key+1 és node->key-1 csak a BST különálló elemeinek engedélyezésére szolgál.

Ha azt akarjuk, hogy ugyanazok az elemek is jelen legyenek, akkor mindkét helyen csak node->key használható.

a kezdeti hívás erre a funkcióra lehet valami ilyesmi:

if (isBST(root, INT_MIN, INT_MAX)) { puts("This is a BST.");} else { puts("This is NOT a BST!");}

lényegében egy érvényes tartományt hozunk létre (kezdve), és minden egyes csomópontra zsugorítjuk, miközben rekurzív módon lemegyünk.,

amint arra a #Traversal szakaszban rámutattunk, egy bináris keresőfák sorrendjében történő áthaladása visszaadja a rendezett csomópontokat. Így csak az utolsó meglátogatott csomópontot kell megtartanunk a fa áthaladása közben, és ellenőriznünk kell, hogy a kulcs kisebb (vagy kisebb/egyenlő, ha másolatokat kell engedélyezni a fában) az aktuális kulcshoz képest.

Párhuzamos algorithmsEdit

Ott is párhuzamos algoritmusok a bináris keresőfák, beleértve beszúrása/törlése több elem, szerkezet tömb, szűrő bizonyos predicator, lelapul, hogy egy tömb, összevonása/substracting/metsző két fa, stb., Ezek az algoritmusok join-alapú fa algoritmusok segítségével valósíthatók meg, amelyek több kiegyensúlyozó rendszer (például AVL fa, vörös-fekete fa, súlyegyensúlyozott fa és treap) segítségével is egyensúlyban tudják tartani a fát .